nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

The Power of Cut-Based Parameters for Computing Edge Disjoint Paths

verfasst von : Robert Ganian, Sebastian Ordyniak

Erschienen in: Graph-Theoretic Concepts in Computer Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper revisits 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 aim is to identify structural properties (parameters) of graphs which allow the efficient solution of EDP without restricting the placement of terminals in P in any way. In this setting, EDP is known to remain NP-hard even on extremely restricted graph classes, such as graphs with a vertex cover of size 3.

We present three results which use edge-separator based parameters to chart new islands of tractability in the complexity landscape of EDP. Our first and main result utilizes the fairly recent structural parameter treecut width (a parameter with fundamental ties to graph immersions and graph cuts): we obtain a polynomial-time algorithm for EDP on every graph class of bounded treecut width. Our second result shows that EDP parameterized by treecut width is unlikely to be fixed-parameter tractable. Our final, third result is a polynomial kernel for EDP parameterized by the size of a minimum feedback edge set in the graph.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Travelling on Graphs with Small Highway Dimension

Nächstes Kapitel Geometric Representations of Dichotomous Ordinal Data

Chekuri, C., Khanna, S., Bruce Shepherd, F.: An O(sqrt(n)) approximation and integrality gap for disjoint paths and unsplittable flow. Theory Comput. 2(7), 137–146 (2006)MathSciNetCrossRef

Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125–150 (2000)MathSciNetCrossRef

Cygan, M., et al.: Parameterized Algorithms. Springer, Heidelberg (2015)CrossRef

Cygan, M., et al.: Parameterized Algorithms. Springer, Berlin (2014)

Diestel, R.: Graph Theory, 4th edn. Springer, Heidelberg (2010)CrossRef

Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Heidelberg (2013)CrossRef

Ene, A., Mnich, M., Pilipczuk, M., Risteski, A.: On routing disjoint paths in bounded treewidth graphs. In: Proceedings of the SWAT 2016. LIPIcs, vol. 53, pp. 15:1–15:15. Schloss Dagstuhl (2016)

Fleszar, K., Mnich, M., Spoerhase, J.: New algorithms for maximum disjoint paths based on tree-likeness. In: Proceedings of the ESA 2016, pp. 42:1–42:17 (2016)

Ganian, R., Kim, E.J., Szeider, S.: Algorithmic applications of tree-cut width. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9235, pp. 348–360. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48054-0_29CrossRefMATH

10.

Ganian, R., Klute, F., Ordyniak, S.: On structural parameterizations of the bounded-degree vertex deletion problem. In: Proceedings of the STACS 2018, pp. 33:1–33:14 (2018)

11.

Ganian, R., Ordyniak, S., Sridharan, R.: On structural parameterizations of the edge disjoint paths problem. In Proceedings of the ISAAC 2017. LIPIcs, vol. 92, pp. 36:1–36:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017)

12.

Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3–20 (1997)MathSciNetCrossRef

13.

Karp, R.M.: On the computational complexity of combinatorial problems. Networks 5(1), 45–68 (1975)CrossRef

14.

Kawarabayashi, K., Kobayashi, Y., Kreutzer, S.: An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem. In: Proceedings of the STOC 2014, pp. 70–78. ACM (2014)

15.

Kim, E., Oum, S., Paul, C., Sau, I., Thilikos, D.M.: An FPT 2-approximation for tree-cut decomposition. In: Sanità, L., Skutella, M. (eds.) WAOA 2015. LNCS, vol. 9499, pp. 35–46. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-28684-6_4CrossRefMATH

16.

Kolliopoulos, S.G., Stein, C.: Approximating disjoint-path problems using packing integer programs. Math. Program. 99(1), 63–87 (2004)MathSciNetCrossRef

17.

Marx, D., Wollan, P.: Immersions in highly edge connected graphs. SIAM J. Discret. Math. 28(1), 503–520 (2014)MathSciNetCrossRef

18.

Nishizeki, T., Vygen, J., Zhou, X.: The edge-disjoint paths problem is NP-complete for series-parallel graphs. Discret. Appl. Math. 115(1–3), 177–186 (2001)MathSciNetCrossRef

19.

Robertson, N., Seymour, P.D.: Graph minors XIII. The disjoint paths problem. J. Comb. Theory Ser. B 63(1), 65–110 (1995)MathSciNetCrossRef

20.

Robertson, N., Seymour, P.D.: Graph minors. XVIII. tree-decompositions and well-quasi-ordering. J. Comb. Theory Ser. B 89(1), 77–108 (2003)MathSciNetCrossRef

21.

Scheffler, P.: Practical linear time algorithm for disjoint paths in graphs with bounded tree-width. In: Technical report TR 396/1994. FU Berlin, Fachbereich 3 Mathematik (1994)

22.

Wollan, P.: The structure of graphs not admitting a fixed immersion. J. Comb. Theory Ser. B 110, 47–66 (2015)MathSciNetCrossRef

23.

Zhou, X., Tamura, S., Nishizeki, T.: Finding edge-disjoint paths in partial k-trees. Algorithmica 26(1), 3–30 (2000)MathSciNetCrossRef

Titel: The Power of Cut-Based Parameters for Computing Edge Disjoint Paths
verfasst von: Robert Ganian
Sebastian Ordyniak
Verlag: Springer International Publishing
Buch: Graph-Theoretic Concepts in Computer Science
Print ISBN: 978-3-030-30785-1

Electronic ISBN: 978-3-030-30786-8

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-30786-8_15

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"