Document Open Access Logo

Efficient Enumerations for Minimal Multicuts and Multiway Cuts

Authors Kazuhiro Kurita , Yasuaki Kobayashi

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.60.pdf
  • Filesize: 1.09 MB
  • 14 pages

Document Identifiers

Author Details

Kazuhiro Kurita
  • National Institute of Informatics, Tokyo, Japan
Yasuaki Kobayashi
  • Kyoto University, Japan

Funding

  • Kurita, Kazuhiro: JSPS KAKENHI Grant Number JP19J10761.
  • Kobayashi, Yasuaki: JSPS KAKENHI Grant Numbers JP20K19742 and JP20H00595.

Cite AsGet BibTex

Kazuhiro Kurita and Yasuaki Kobayashi. Efficient Enumerations for Minimal Multicuts and Multiway Cuts. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.60

Abstract

Let G = (V, E) be an undirected graph and let B ⊆ V × V be a set of terminal pairs. A node/edge multicut is a subset of vertices/edges of G whose removal destroys all the paths between every terminal pair in B. The problem of computing a minimum node/edge multicut is NP-hard and extensively studied from several viewpoints. In this paper, we study the problem of enumerating all minimal node multicuts. We give an incremental polynomial delay enumeration algorithm for minimal node multicuts, which extends an enumeration algorithm due to Khachiyan et al. (Algorithmica, 2008) for minimal edge multicuts. Important special cases of node/edge multicuts are node/edge multiway cuts, where the set of terminal pairs contains every pair of vertices in some subset T ⊆ V, that is, B = T × T. We improve the running time bound for this special case: We devise a polynomial delay and exponential space enumeration algorithm for minimal node multiway cuts and a polynomial delay and space enumeration algorithm for minimal edge multiway cuts.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Multicuts
  • Multiway cuts
  • Enumeration algorithms

Metrics

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

Related Versions

References

  1. S. Arora, D. Karger, and M. Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems. Journal of Computer and System Sciences, 58(1):193-210, 1999. URL: https://doi.org/10.1006/jcss.1998.1605.
  2. D. Avis and K. Fukuda. Reverse search for enumeration. Discrete Applied Mathematics, 65(1):21-46, 1996. URL: https://doi.org/10.1016/0166-218X(95)00026-N.
  3. M. Bateni, M. Hajiaghayi, P. N. Klein, and C. Mathieu. A polynomial-time approximation scheme for planar multiway cut. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’12, page 639–655, USA, 2012. Society for Industrial and Applied Mathematics. Google Scholar
  4. Vincent Bouchitté and Ioan Todinca. Treewidth and minimum fill-in: Grouping the minimal separators. SIAM J. Comput., 31(1):212–232, 2002. URL: https://doi.org/10.1137/S0097539799359683.
  5. Karl Bringmann, Danny Hermelin, Matthias Mnich, and Erik Jan [van Leeuwen]. Parameterized complexity dichotomy for Steiner Multicut. Journal of Computer and System Sciences, 82(6):1020-1043, 2016. Google Scholar
  6. D. Z. Chen and X. Wu. Efficient algorithms for k-terminal cuts on planar graphs. Algorithmica, 38(2):299-316, February 2004. URL: https://doi.org/10.1007/s00453-003-1061-2.
  7. Sara Cohen, Benny Kimelfeld, and Yehoshua Sagiv. Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties. J. Comput. Syst. Sci., 74(7):1147-1159, 2008. URL: https://doi.org/10.1016/j.jcss.2008.04.003.
  8. Alessio Conte and Takeaki Uno. New polynomial delay bounds for maximal subgraph enumeration by proximity search. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1179-1190, 2019. URL: https://doi.org/10.1145/3313276.3316402.
  9. G. Cǎlinescu, H. Karloff, and Y. Rabani. An improved approximation algorithm for multiway cut. Journal of Computer and System Sciences, 60(3):564-574, 2000. URL: https://doi.org/10.1006/jcss.1999.1687.
  10. M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk. On multiway cut parameterized above lower bounds. ACM Trans. Comput. Theory, 5(1), 2013. URL: https://doi.org/10.1145/2462896.2462899.
  11. E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis. The complexity of multiterminal cuts. SIAM J. Comput., 23(4):864–894, 1994. URL: https://doi.org/10.1137/S0097539792225297.
  12. R. Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  13. Jixing Feng, Xin Li, Eduardo L. Pasiliao, and John M. Shea. Jammer placement to partition wireless network. In 2014 IEEE GLOBECOM Workshops, Austin, TX, USA, December 8-12, 2014, pages 1487-1492, 2014. URL: https://doi.org/10.1109/GLOCOMW.2014.7063644.
  14. L. Fireman, E. Petrank, and A. Zaks. New algorithms for simd alignment. In Compiler Construction, pages 1-15, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. Google Scholar
  15. Fedor V. Fomin, Ioan Todinca, and Yngve Villanger. Large induced subgraphs via triangulations and CMSO. SIAM J. Comput., 44(1):54-87, 2015. Google Scholar
  16. Michael L. Fredman and Leonid Khachiyan. On the complexity of dualization of monotone disjunctive normal forms. J. Algorithms, 21(3):618-628, 1996. URL: https://doi.org/10.1006/jagm.1996.0062.
  17. Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Approximate max-flow min-(multi)cut theorems and their applications. SIAM J. Comput., 25(2):235-251, 1996. URL: https://doi.org/10.1137/S0097539793243016.
  18. 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. URL: https://doi.org/10.1007/BF02523685.
  19. Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57). North-Holland Publishing Co., NLD, 2004. Google Scholar
  20. S. Guillemot. Fpt algorithms for path-transversal and cycle-transversal problems. Discrete Optimization, 8(1):61-71, 2011. URL: https://doi.org/10.1016/j.disopt.2010.05.003.
  21. Jiong Guo, Falk Hüffner, Erhan Kenar, Rolf Niedermeier, and Johannes Uhlmann. Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs. Eur. J. Oper. Res., 186(2):542-553, 2008. URL: https://doi.org/10.1016/j.ejor.2007.02.014.
  22. David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. On generating all maximal independent sets. Inf. Process. Lett., 27(3):119-123, 1988. URL: https://doi.org/10.1016/0020-0190(88)90065-8.
  23. J. H. Kappes, M. Speth, B. Andres, G. Reinelt, and C. Schnörr. Globally optimal image partitioning by multicuts. In Proceedings of the 8th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition, EMMCVPR’11, page 31–44, Berlin, Heidelberg, 2011. Springer-Verlag. Google Scholar
  24. D. R. Karger, P. Klein, C. Stein, M. Thorup, and N. E. Young. Rounding algorithms for a geometric embedding of minimum multiway cut. Math. Oper. Res., 29(3):436–461, 2004. URL: https://doi.org/10.1287/moor.1030.0086.
  25. L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, and K. Makino. Generating cut conjunctions in graphs and related problems. Algorithmica, 51(3):239–263, 2008. Google Scholar
  26. Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled M. Elbassioni, Vladimir Gurvich, and Kazuhisa Makino. Enumerating spanning and connected subsets in graphs and matroids. In Algorithms - ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006, Proceedings, pages 444-455, 2006. URL: https://doi.org/10.1007/11841036_41.
  27. P. N. Klein and D. Marx. Solving planar k-terminal cut in O(n^c√k) time. In Proceedings of the 39th International Colloquium Conference on Automata, Languages, and Programming - Volume Part I, ICALP'12, page 569–580, Berlin, Heidelberg, 2012. Springer-Verlag. URL: https://doi.org/10.1007/978-3-642-31594-7_48.
  28. T. Kloks and D. Kratsch. Listing all minimal separators of a graph. SIAM J. Comput., 27(3):605–613, June 1998. Google Scholar
  29. Kazuhiro Kurita and Yasuaki Kobayashi. Efficient enumerations for minimal multicuts and multiway cuts. CoRR, abs/2006.16222, 2020. URL: http://arxiv.org/abs/2006.16222.
  30. D. Marx. Parameterized graph separation problems. Theor. Comput. Sci., 351(3):394–406, 2006. URL: https://doi.org/10.1016/j.tcs.2005.10.007.
  31. D. Marx. A tight lower bound for planar multiway cut with fixed number of terminals. In Proceedings of the 39th International Colloquium Conference on Automata, Languages, and Programming - Volume Part I, ICALP’12, page 677–688, Berlin, Heidelberg, 2012. Springer-Verlag. URL: https://doi.org/10.1007/978-3-642-31594-7_57.
  32. Dániel Marx and Igor Razgon. Fixed-parameter tractability of multicut parameterized by the size of the cutset. SIAM J. Comput., 43(2):355-388, 2014. URL: https://doi.org/10.1137/110855247.
  33. J. S. Provan and D. R. Shier. A paradigm for listing (s, t)-cuts in graphs. Algorithmica, 15(4):351–372, 1996. URL: https://doi.org/10.1007/BF01961544.
  34. Benno Schwikowski and Ewald Speckenmeyer. On enumerating all minimal solutions of feedback problems. Discret. Appl. Math., 117(1-3):253-265, 2002. URL: https://doi.org/10.1016/S0166-218X(00)00339-5.
  35. H. Shen and W. Liang. Efficient enumeration of all minimal separators in a graph. Theoretical Computer Science, 180(1):169-180, 1997. Google Scholar
  36. H. S. Stone. Multiprocessor scheduling with the aid of network flow algorithms. IEEE Trans. Softw. Eng., 3(1):85–93, 1977. URL: https://doi.org/10.1109/TSE.1977.233840.
  37. K. Takata. Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph. Discrete Applied Mathematics, 158(15):1660-1667, 2010. Google Scholar
  38. S. Tsukiyama, I. Shirakawa, H. Ozaki, and H. Ariyoshi. An algorithm to enumerate all cutsets of a graph in linear time per cutset. J. ACM, 27(4):619–632, 1980. URL: https://doi.org/10.1145/322217.322220.
  39. T. Uno. Two general methods to reduce delay and change of enumeration algorithms. Technical report, National Institute of Informatics Technical Report E, 2003. Google Scholar
  40. M. Xiao. Simple and improved parameterized algorithms for multiterminal cuts. Theor. Comp. Sys., 46(4):723–736, 2010. URL: https://doi.org/10.1007/s00224-009-9215-5.
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 Imprint Privacy Contact