Document Open Access Logo

On Structural Parameterizations of the Edge Disjoint Paths Problem

Authors Robert Ganian, Sebastian Ordyniak, Ramanujan Sridharan

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.36.pdf
  • Filesize: 0.5 MB
  • 13 pages

Document Identifiers

Author Details

Robert Ganian
Sebastian Ordyniak
Ramanujan Sridharan

Cite As Get BibTex

Robert Ganian, Sebastian Ordyniak, and Ramanujan Sridharan. On Structural Parameterizations of the Edge Disjoint Paths Problem. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 36:1-36:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.36

Abstract

In this paper we revisit the classical Edge Disjoint Paths (EDP) problem, where one is given an undirected graph G and a set of terminal pairs P and asks whether G contains a set of pairwise edge-disjoint paths connecting every terminal pair in P. Our focus lies on structural parameterizations for the problem that allow for efficient (polynomial-time or fpt) algorithms. As our first result, we answer an open question stated in Fleszar, Mnich, and Spoerhase (2016), by showing that the problem can be solved in polynomial time if the input graph has a feedback vertex set of size one. We also show that EDP parameterized by the treewidth and the maximum degree of the input graph is fixed-parameter tractable.

Having developed two novel algorithms for EDP using  structural restrictions on the input graph, we then turn our attention towards the augmented graph, i.e., the graph obtained from the input graph after adding one edge between every terminal pair. In constrast to the input graph, where EDP is known to remain NP-hard even for treewidth two, a result by Zhou et al. (2000) shows that EDP can be solved in non-uniform polynomial time if the augmented graph has constant treewidth; we note that the possible improvement of this result to an fpt-algorithm has remained open since then. We show that this is highly unlikely by establishing the W[1]-hardness of the problem  parameterized by the treewidth (and even feedback vertex set) of the augmented graph. Finally,  we develop an fpt-algorithm for EDP by exploiting a novel structural  parameter of the augmented graph.

Subject Classification

Keywords
  • edge disjoint path problem
  • feedback vertex set
  • treewidth
  • fracture number
  • parameterized complexity

Metrics

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

References

  1. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305-1317, 1996. Google Scholar
  2. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A c^k n 5-approximation algorithm for treewidth. SIAM J. Comput., 45(2):317-378, 2016. Google Scholar
  3. Hans L. Bodlaender and Ton Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21(2):358-402, 1996. Google Scholar
  4. Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd. An O(sqrt(n)) approximation and integrality gap for disjoint paths and unsplittable flow. Theory of Computing, 2(7):137-146, 2006. Google Scholar
  5. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  6. Reinhard Diestel. Graph Theory. Springer-Verlag, Heidelberg, 4th edition, 2010. Google Scholar
  7. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  8. Pavel Dvorák, Eduard Eiben, Robert Ganian, Dusan Knop, and Sebastian Ordyniak. Solving integer linear programs with a small number of global variables and constraints. In IJCAI 2017, pages 607-613, 2017. Google Scholar
  9. Alina Ene, Matthias Mnich, Marcin Pilipczuk, and Andrej Risteski. On routing disjoint paths in bounded treewidth graphs. In Proc. SWAT 2016, volume 53 of LIPIcs, pages 15:1-15:15. Schloss Dagstuhl, 2016. Google Scholar
  10. Krzysztof Fleszar, Matthias Mnich, and Joachim Spoerhase. New algorithms for maximum disjoint paths based on tree-likeness. In Proc. ESA 2016, pages 42:1-42:17, 2016. Google Scholar
  11. Jörg Flum and Martin Grohe. Parameterized Complexity Theory, volume XIV of Texts in Theoretical Computer Science. An EATCS Series. Springer Verlag, Berlin, 2006. Google Scholar
  12. Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18(1):3-20, 1997. Google Scholar
  13. Georg Gottlob and Stephanie Tien Lee. A logical approach to multicut problems. Inf. Process. Lett., 103(4):136-141, 2007. Google Scholar
  14. Richard M Karp. On the computational complexity of combinatorial problems. Networks, 5(1):45-68, 1975. Google Scholar
  15. Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Stephan Kreutzer. An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem. In Proc. STOC 2014, pages 70-78. ACM, 2014. Google Scholar
  16. T. Kloks. Treewidth: Computations and Approximations. Springer Verlag, Berlin, 1994. Google Scholar
  17. Stavros G. Kolliopoulos and Clifford Stein. Approximating disjoint-path problems using packing integer programs. Math. Program., 99(1):63-87, 2004. Google Scholar
  18. H. W. Lenstra and Jr. Integer programming with a fixed number of variables. MATH. OPER. RES, 8(4):538-548, 1983. Google Scholar
  19. Takao Nishizeki, Jens Vygen, and Xiao Zhou. The edge-disjoint paths problem is NP-complete for series-parallel graphs. Discrete Applied Mathematics, 115(1-3):177-186, 2001. Google Scholar
  20. Neil Robertson and Paul D. Seymour. Graph minors XIII. The disjoint paths problem. J. Comb. Theory, Ser. B, 63(1):65-110, 1995. Google Scholar
  21. Jens Vygen. Np-completeness of some edge-disjoint paths problems. Discrete Applied Mathematics, 61(1):83-90, 1995. Google Scholar
  22. Xiao Zhou, Syurei Tamura, and Takao Nishizeki. Finding edge-disjoint paths in partial k-trees. Algorithmica, 26(1):3-30, 2000. 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