We introduce and study the complexity of Path Packing. Given a graph G and a list of paths, the task is to embed the paths edge-disjoint in G. This generalizes the well known Hamiltonian-Path problem. Since Hamiltonian Path is efficiently solvable for graphs of small treewidth, we study how this result translates to the much more general Path Packing. On the positive side, we give an FPT-algorithm on trees for the number of paths as parameter. Further, we give an XP-algorithm with the combined parameters maximal degree, number of connected components and number of nodes of degree at least three. Surprisingly the latter is an almost tight result by runtime and parameterization. We show an ETH lower bound almost matching our runtime. Moreover, if two of the three values are constant and one is unbounded the problem becomes NP-hard. Further, we study restrictions to the given list of paths. On the positive side, we present an FPT-algorithm parameterized by the sum of the lengths of the paths. Packing paths of length two is polynomial time solvable, while packing paths of length three is NP-hard. Finally, even the spacial case Exact Path Packing where the paths have to cover every edge in G exactly once is already NP-hard for two paths on 4-regular graphs.


    Access

    Download


    Export, share and cite



    Title :

    The Complexity of Packing Edge-Disjoint Paths


    Contributors:

    Publication date :

    2019-01-01



    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    004 / 629




    Finding Edge-disjoint Paths in Networks: An Ant Colony Optimization Algorithm

    Blesa, M. J. / Blum, C. | British Library Online Contents | 2007


    Robustly disjoint paths with segment routing

    Aubry, François / Vissicchio, Stefano / Bonaventure, Olivier et al. | BASE | 2018

    Free access

    On Routing Disjoint Paths in Bounded Treewidth Graphs

    Ene, Alina / Mnich, Matthias / Pilipczuk, Marcin et al. | BASE | 2016

    Free access


    Models and Complexity of Multibin Packing Problems

    Lemaire, P. / Finke, G. / Brauner, N. | British Library Online Contents | 2006