Document Open Access Logo

On Quasipolynomial Multicut-Mimicking Networks and Kernelization of Multiway Cut Problems

Author Magnus Wahlström

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.101.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Magnus Wahlström
  • Department of Computer Science, Royal Holloway, University of London, UK

Cite AsGet BibTex

Magnus Wahlström. On Quasipolynomial Multicut-Mimicking Networks and Kernelization of Multiway Cut Problems. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 101:1-101:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.101

Abstract

We show the existence of an exact mimicking network of k^O(log k) edges for minimum multicuts over a set of terminals in an undirected graph, where k is the total capacity of the terminals. Furthermore, if Small Set Expansion has an approximation algorithm with a ratio slightly better than Θ(log n), then a mimicking network of quasipolynomial size can be computed in polynomial time. As a consequence of the latter, several problems would have quasipolynomial kernels, including Edge Multiway Cut, Group Feedback Edge Set for an arbitrary group, 0-Extension for integer-weighted metrics, and Edge Multicut parameterized by the solution and the number of cut requests. The result works via a combination of the matroid-based irrelevant edge approach used in the kernel for s-Multiway Cut with a recursive decomposition and sparsification of the graph along sparse cuts. The main technical contribution is a matroid-based marking procedure that we can show will mark all non-irrelevant edges, assuming that the graph is sufficiently densely connected. The only part of the result that is not currently constructive and polynomial-time computable is the detection of such sparse cuts. This is the first progress on the kernelization of Multiway Cut problems since the kernel for s-Multiway Cut for constant value of s (Kratsch and Wahlström, FOCS 2012).

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Multiway Cut
  • Kernelization
  • Small Set Expansion
  • Mimicking Networks

Metrics

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

Related Versions

References

  1. Alexandr Andoni, Anupam Gupta, and Robert Krauthgamer. Towards 1 + ε-approximate flow sparsifiers. In SODA, pages 279-293. SIAM, 2014. Google Scholar
  2. Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, and Roy Schwartz. Min-max graph partitioning and small set expansion. SIAM J. Comput., 43(2):872-904, 2014. Google Scholar
  3. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. J. Comput. Syst. Sci., 75(8):423-434, 2009. URL: https://doi.org/10.1016/j.jcss.2009.04.001.
  4. Julia Chuzhoy. On vertex sparsifiers with Steiner nodes. In STOC, pages 673-688. ACM, 2012. 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. Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, and Mihalis Yannakakis. The complexity of multiterminal cuts. SIAM J. Comput., 23(4):864-894, 1994. Google Scholar
  7. Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, and Kunal Talwar. Vertex sparsifiers: New results from old techniques. SIAM J. Comput., 43(4):1239-1262, 2014. Google Scholar
  8. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM, 63(4):29:1-29:60, 2016. URL: https://doi.org/10.1145/2886094.
  9. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2019. URL: https://doi.org/10.1017/9781107415157.
  10. Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci., 77(1):91-106, 2011. URL: https://doi.org/10.1016/j.jcss.2010.06.007.
  11. 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.
  12. Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, and Prabhakar Ragde. Characterizing multiterminal flow networks and computing flows in networks of small treewidth. J. Comput. Syst. Sci., 57(3):366-375, 1998. Google Scholar
  13. Eva-Maria C. Hols and Stefan Kratsch. A randomized polynomial kernel for subset feedback vertex set. Theory Comput. Syst., 62(1):63-92, 2018. URL: https://doi.org/10.1007/s00224-017-9805-6.
  14. Nikolai Karpov, Marcin Pilipczuk, and Anna Zych-Pawlewicz. An exponential lower bound for cut sparsifiers in planar graphs. Algorithmica, 81(10):4029-4042, 2019. Google Scholar
  15. Arindam Khan and Prasad Raghavendra. On mimicking networks representing minimum terminal cuts. Inf. Process. Lett., 114(7):365-371, 2014. Google Scholar
  16. Stefan Kratsch. A randomized polynomial kernelization for vertex cover with a smaller parameter. SIAM J. Discrete Math., 32(3):1806-1839, 2018. URL: https://doi.org/10.1137/16M1104585.
  17. Stefan Kratsch and Magnus Wahlström. Representative sets and irrelevant vertices: New tools for kernelization. In FOCS, pages 450-459, 2012. URL: https://doi.org/10.1109/FOCS.2012.46.
  18. Stefan Kratsch and Magnus Wahlström. Compression via matroids: A randomized polynomial kernel for odd cycle transversal. ACM Trans. Algorithms, 10(4):20:1-20:15, 2014. Google Scholar
  19. Robert Krauthgamer and Havana Inbal Rika. Refined vertex sparsifiers of planar graphs. SIAM J. Discrete Math., 34(1):101-129, 2020. Google Scholar
  20. Robert Krauthgamer and Inbal Rika. Mimicking networks and succinct representations of terminal cuts. In SODA, pages 1789-1799. SIAM, 2013. Google Scholar
  21. Frank Thomson Leighton and Ankur Moitra. Extensions and limits to vertex sparsification. In STOC, pages 47-56. ACM, 2010. Google Scholar
  22. Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, and Saket Saurabh. Deterministic truncation of linear matroids. ACM Trans. Algorithms, 14(2):14:1-14:20, 2018. Google Scholar
  23. László Lovász. Flats in matroids and geometric graphs. In Proc. Sixth British Combinatorial Conf., Combinatorial Surveys, pages 45-86, 1977. Google Scholar
  24. Dániel Marx. Parameterized graph separation problems. Theor. Comput. Sci., 351(3):394-406, 2006. URL: https://doi.org/10.1016/j.tcs.2005.10.007.
  25. Dániel Marx. A parameterized view on matroid optimization problems. Theor. Comput. Sci., 410(44):4471-4479, 2009. URL: https://doi.org/10.1016/j.tcs.2009.07.027.
  26. Ankur Moitra. Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In FOCS, pages 3-12. IEEE Computer Society, 2009. Google Scholar
  27. G. Nemhauser and L. Trotter. Vertex packing: structural properties and algorithms. Mathematical Programming, 8:232-248, 1975. URL: https://doi.org/10.1007/BF01580444.
  28. James Oxley. Matroid Theory. Oxford University Press, 2011. Google Scholar
  29. Harald Räcke. Minimizing congestion in general networks. In FOCS, pages 43-52. IEEE Computer Society, 2002. URL: https://doi.org/10.1109/SFCS.2002.1181881.
  30. Harald Räcke. Optimal hierarchical decompositions for congestion minimization in networks. In STOC, pages 255-264. ACM, 2008. Google Scholar
  31. Prasad Raghavendra and David Steurer. Graph expansion and the unique games conjecture. In STOC, pages 755-764. ACM, 2010. Google Scholar
  32. Felix Reidl and Magnus Wahlström. Parameterized algorithms for zero extension and metric labelling problems. In ICALP, volume 107 of LIPIcs, pages 94:1-94:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. 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 Imprint Privacy Contact