nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Fixed-Parameter Tractability of Counting Small Minimum (S, T)-Cuts

verfasst von : Pierre Bergé, Benjamin Mouscadet, Arpad Rimmel, Joanna Tomasik

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

The parameterized complexity of counting minimum cuts stands as a natural question because Ball and Provan showed its #P-completeness. For any undirected graph \(G=(V,E)\) and two disjoint sets of its vertices S, T, we design a fixed-parameter tractable algorithm which counts minimum edge (S, T)-cuts parameterized by their size p. Our algorithm operates on a transformed graph instance. This transformation, called drainage, reveals a collection of at most \(n=\left| V \right| \) successive minimum (S, T)-cuts \(Z_i\). We prove that any minimum (S, T)-cut X contains edges of at least one cut \(Z_i\). This observation, together with Menger’s theorem, allows us to build the algorithm counting all minimum (S, T)-cuts with running time \(2^{O(p^2)}n^{O(1)}\). Initially dedicated to counting minimum cuts, it can be modified to obtain an FPT sampling of minimum edge (S, T)-cuts.

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 Local Approximation of the Maximum Cut in Regular Graphs

Nächstes Kapitel Fast Breadth-First Search in Still Less Space

The proofs in Sects. 3 and 4 are withdrawn due to the restriction on the number of pages. The full version can be found here: https://arxiv.org/abs/1907.02353.

Arvind, V., Raman, V.: Approximation algorithms for some parameterized counting problems. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol. 2518, pp. 453–464. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-36136-7_40CrossRefMATH

Ball, M.O., Colbourn, C.J., Provan, J.S.: Network reliability. In: Handbooks in Operations Research and Management Science, vol. 7, pp. 673–762. Elsevier (1995)

Ball, M.O., Provan, J.S.: Calculating bounds on reachability and connectedness in stochastic networks. Networks 13(2), 253–278 (1983)MathSciNetCrossRef

Ball, M.O., Provan, J.S.: Computing network reliability in time polynomial in the number of cuts. Oper. Res. 32(3), 516–526 (1984)MathSciNetCrossRef

Bezáková, I., Chambers, E.W., Fox, K.: Integrating and sampling cuts in bounded treewidth graphs. In: Letzter, G., et al. (eds.) Advances in the Mathematical Sciences. AWMS, vol. 6, pp. 401–415. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-34139-2_20CrossRefMATH

Bezáková, I., Friedlander, A.J.: Counting and sampling minimum (S, T)-cuts in weighted planar graphs in polynomial time. Theoret. Comput. Sci. 417, 2–11 (2012)MathSciNetCrossRef

Bousquet, N., Daligault, J., Thomassé, S.: Multicut is FPT. In: Proceedings of STOC, pp. 459–468 (2011)

Boykov, Y., Veksler, O.: Graph cuts in vision and graphics: theories and applications. In: Paragios, N., Chen, Y., Faugeras, O. (eds.) Handbook of Mathematical Models in Computer Vision, pp. 79–96. Springer, Boston (2006). https://doi.org/10.1007/0-387-28831-7_5CrossRef

Chambers, E.W., Fox, K., Nayyeri, A.: Counting and sampling minimum cuts in genus \(g\) graphs. In: Proceedings of SoCG, pp. 249–258 (2013)

10.

Chandran, L.S., Ram, L.S.: On the number of minimum cuts in a graph. In: Proceedings of COCOON, pp. 220–229 (2002)

11.

Chen, J., Liu, Y., Lu, S.: An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica 55(1), 1–13 (2009)MathSciNetCrossRef

12.

Chitnis, R.H., Hajiaghayi, M., Marx, D.: Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. SIAM J. Comput. 42(4), 1674–1696 (2013)MathSciNetCrossRef

13.

Curticapean, R.: Counting problems in parameterized complexity. In: Proceedings of IPEC, pp. 1–18 (2018)

14.

Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Minimum bisection is fixed parameter tractable. In: Proceedings of STOC, pp. 323–332 (2014)

15.

Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999). https://doi.org/10.1007/978-1-4612-0515-9CrossRefMATH

16.

Flum, J., Grohe, M.: The parameterized complexity of counting problems. SIAM J. Comput. 33(4), 892–922 (2004)MathSciNetCrossRef

17.

Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8, 399–404 (1956)MathSciNetCrossRef

18.

Guillemot, S., Sikora, F.: Finding and counting vertex-colored subtrees. Algorithmica 65(4), 828–844 (2013)MathSciNetCrossRef

19.

Krom, M.R.: The decision problem for a class of firstorder formulas in which all disjunctions are binary. Math. Logic Q. 13(12), 15–20 (1967)MathSciNetCrossRef

20.

Marx, D.: Parameterized graph separation problems. Theoret. Comput. Sci. 351(3), 394–406 (2006)MathSciNetCrossRef

21.

Marx, D., O’Sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms 9(4), 30:1–30:35 (2013)MathSciNetCrossRef

22.

Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. In: Proceedings of STOC, pp. 469–478 (2011)

23.

Menger, K.: Zur allgemeinen Kurventheorie. Fundamenta Mathematicæ 10(1), 96–115 (1927)CrossRef

24.

Nagamochi, H., Sun, Z., Ibaraki, T.: Counting the number of minimum cuts in undirected multigraphs. IEEE Trans. Reliab. 40, 610–614 (1991)CrossRef

25.

Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. OUP, Oxford (2006)CrossRef

26.

Provan, J.S., Ball, M.O.: The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput. 12(4), 777–788 (1983)MathSciNetCrossRef

27.

Valiant, L.G.: The complexity of counting the permanent. Theoret. Comput. Sci. 8, 189–201 (1979)MathSciNetCrossRef

28.

Williams, V.V., Williams, R.: Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput. 42(3), 831–854 (2013)MathSciNetCrossRef

Titel: Fixed-Parameter Tractability of Counting Small Minimum (S, T)-Cuts
verfasst von: Pierre Bergé
Benjamin Mouscadet
Arpad Rimmel
Joanna Tomasik
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_7

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"

Premium Partner