Document Open Access Logo

The Complexity of Packing Edge-Disjoint Paths

Authors Jan Dreier , Janosch Fuchs , Tim A. Hartmann , Philipp Kuinke , Peter Rossmanith , Bjoern Tauer, Hung-Lung Wang

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2019.10.pdf
  • Filesize: 0.77 MB
  • 16 pages

Document Identifiers

Author Details

Jan Dreier
  • Dept. of Computer Science, RWTH Aachen University, Germany
Janosch Fuchs
  • Dept. of Computer Science, RWTH Aachen University, Germany
Tim A. Hartmann
  • Dept. of Computer Science, RWTH Aachen University, Germany
Philipp Kuinke
  • Dept. of Computer Science, RWTH Aachen University, Germany
Peter Rossmanith
  • Dept. of Computer Science, RWTH Aachen University, Germany
Bjoern Tauer
  • Dept. of Computer Science, RWTH Aachen University, Germany
Hung-Lung Wang
  • Computer Science and Information Engineering, National Taiwan Normal University, Taiwan

Cite As Get BibTex

Jan Dreier, Janosch Fuchs, Tim A. Hartmann, Philipp Kuinke, Peter Rossmanith, Bjoern Tauer, and Hung-Lung Wang. The Complexity of Packing Edge-Disjoint Paths. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.IPEC.2019.10

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • parameterized complexity
  • embedding
  • packing
  • covering
  • Hamiltonian path
  • unary binpacking
  • path-perfect graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, July 1995. URL: https://doi.org/10.1145/210332.210337.
  2. S. Rao Arikati and C. Pandu Rangan. Linear Algorithm for Optimal Path Cover Problem on Interval Graphs. Inf. Process. Lett., 35(3):149-153, July 1990. URL: https://doi.org/10.1016/0020-0190(90)90064-5.
  3. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets Möbius: Fast subset convolution. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 67-74, 2007. URL: https://doi.org/10.1145/1250790.1250801.
  4. Maurizio A. Bonuccelli and Daniel P. Bovet. Minimum Node Disjoint Path Covering for Circular-Arc Graphs. Inf. Process. Lett., 8(4):159-161, 1979. URL: https://doi.org/10.1016/0020-0190(79)90011-5.
  5. Weiting Cao and Peter Hamburger. Solution of fink & straight conjecture on path-perfect complete bipartite graphs. Journal of Graph Theory, 55(2):91-111, 2007. Google Scholar
  6. Gerard J. Chang and David Kuo. The L(2,1)-Labeling Problem on Graphs. SIAM Journal on Discrete Mathematics, 9(2):309-316, 1996. URL: https://epubs.siam.org/doi/ref/10.1137/S0895480193245339.
  7. Gerard Cornuéjols, David Hartvigsen, and W Pulleyblank. Packing subgraphs in a graph. Operations Research Letters, 1(4):139-143, 1982. Google Scholar
  8. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer Publishing Company, Incorporated, 1st edition, 2015. Google Scholar
  9. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999. URL: https://doi.org/10.1007/978-1-4612-0515-9.
  10. Henning Fernau and Daniel Raible. A parameterized perspective on packing paths of length two. In International Conference on Combinatorial Optimization and Applications, pages 54-63. Springer, 2008. Google Scholar
  11. John Frederick Fink and H. Joseph Straight. A note on path-perfect graphs. Discrete Mathematics, 33(1):95-98, 1981. Google Scholar
  12. S. E. Goodman, Stephen T. Hedetniemi, and Peter J. Slater. Advances on the Hamiltonian Completion Problem. J. ACM, 22(3):352-360, 1975. URL: https://doi.org/10.1145/321892.321897.
  13. Peter Hamburger and Weiting Cao. Edge Disjoint Paths of Increasing Order in Complete Bipartite Graphs. Electronic Notes in Discrete Mathematics, 22:61-67, 2005. Google Scholar
  14. Heather Hulett, Todd G. Will, and Gerhard J. Woeginger. Multigraph realizations of degree sequences: Maximization is easy, minimization is hard. Operations Research Letters, 36(5):594-596, 2008. URL: https://doi.org/10.1016/j.orl.2008.05.004.
  15. Klaus Jansen, Stefan Kratsch, Dániel Marx, and Ildikó Schlotter. Bin packing with fixed number of bins revisited. Journal of Computer and System Sciences, 79(1):39-49, 2013. Google Scholar
  16. David G. Kirkpatrick and Pavol Hell. On the Completeness of a Generalized Matching Problem. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, pages 240-245, 1978. URL: https://doi.org/10.1145/800133.804353.
  17. Hoàng-Oanh Le, Van Bang Le, and Haiko Müller. Splitting a graph into disjoint induced paths or cycles. Discrete Applied Mathematics, 131(1):199-212, 2003. URL: https://doi.org/10.1016/S0166-218X(02)00425-0.
  18. Jayadev Misra and Robert Endre Tarjan. Optimal Chain Partitions of Trees. Inf. Process. Lett., 4(1):24-26, 1975. URL: https://doi.org/10.1016/0020-0190(75)90057-5.
  19. Jerome Monnot and Sophie Toulouse. The path partition problem and related problems in bipartite graphs. Operations Research Letters, 35(5):677-684, 2007. URL: https://doi.org/10.1016/j.orl.2006.12.004.
  20. Sarah Pantel. Graph packing problems. Master’s thesis, Simon Fraser University, Canada, 1999. Google Scholar
  21. R. Srikant, Ravi Sundaram, Karan Sher Singh, and C. Pandu Rangan. Optimal Path Cover Problem on Block Graphs and Bipartite Permutation Graphs. Theor. Comput. Sci., 115(2):351-357, 1993. URL: https://doi.org/10.1016/0304-3975(93)90123-B.
  22. George Steiner. On the k-path partition of graphs. Theoretical Computer Science, 290(3):2147-2155, 2003. URL: https://doi.org/10.1016/S0304-3975(02)00577-7.
  23. H. Joseph Straight. Partitions of the vertex set or edge set of a graph. dissertation, Western Michigan University, 1977. Google Scholar
  24. H. Joseph Straight. Packing trees of different size into the complete graph. Annals of the New York Academy of Sciences, 328(1):190-192, 1979. Google Scholar
  25. Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith. Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution. In Proc. of the 17th Annual European Symposium on Algorithms (ESA), number 5757 in Lecture Notes in Computer Science, pages 566-577. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-04128-0_51.
  26. Jing-Ho Yan and Gerard J. Chang. The path-partition problem in block graphs. Information Processing Letters, 52(6):317-322, 1994. URL: https://doi.org/10.1016/0020-0190(94)00158-8.
  27. Jing-Ho Yan, Gerard J. Chang, Sandra Mitchell Hedetniemi, and Stephen T. Hedetniemi. k-Path Partitions in Trees. Discrete Applied Mathematics, 78(1-3):227-233, 1997. URL: https://doi.org/10.1016/S0166-218X(97)00012-7.
  28. H. P. Yap. Packing of graphs-a survey. In Annals of Discrete Mathematics, volume 38, pages 395-404. Elsevier, 1988. Google Scholar
  29. Shmuel Zaks and Chung Laung Liu. Decomposition of graphs into trees. Technical Report 860, Department of Computer Science, University of Illinois at Urbana-Champaign, 1977. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact