Document Open Access Logo

A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs

Authors Bart M. P. Jansen, Marcin Pilipczuk, Erik Jan van Leeuwen

PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.39.pdf
  • Filesize: 0.58 MB
  • 18 pages

Document Identifiers

Author Details

Bart M. P. Jansen
  • Eindhoven University of Technology
Marcin Pilipczuk
  • Institute of Informatics, University of Warsaw
Erik Jan van Leeuwen
  • Department of Information & Computing Sciences, Utrecht University

Funding

  • Jansen, Bart M. P.: Supported by NWO Gravitation grant "Networks".
  • Pilipczuk, Marcin: Supported by the "Recent trends in kernelization: theory and experimental evaluation" project, carried out within the Homing programme of the Foundation for Polish Science co-financed by the European Union under the European Regional Development Fund.

Cite AsGet BibTex

Bart M. P. Jansen, Marcin Pilipczuk, and Erik Jan van Leeuwen. A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 39:1-39:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.STACS.2019.39

Abstract

We show that Odd Cycle Transversal and Vertex Multiway Cut admit deterministic polynomial kernels when restricted to planar graphs and parameterized by the solution size. This answers a question of Saurabh. On the way to these results, we provide an efficient sparsification routine in the flavor of the sparsification routine used for the Steiner Tree problem in planar graphs (FOCS 2014). It differs from the previous work because it preserves the existence of low-cost subgraphs that are not necessarily Steiner trees in the original plane graph, but structures that turn into (supergraphs of) Steiner trees after adding all edges between pairs of vertices that lie on a common face. We also show connections between Vertex Multiway Cut and the Vertex Planarization problem, where the existence of a polynomial kernel remains an important open problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • planar graphs
  • kernelization
  • odd cycle transversal
  • multiway cut

Metrics

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

Related Versions

References

  1. 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: http://dx.doi.org/10.1016/j.jcss.2009.04.001.
  2. Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci., 412(35):4570-4578, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2011.04.039.
  3. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  4. Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. On multiway cut parameterized above lower bounds. TOCT, 5(1):3:1-3:11, 2013. URL: http://dx.doi.org/10.1145/2462896.2462899.
  5. Holger Dell and Dieter van Melkebeek. Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses. J. ACM, 61(4):23:1-23:27, 2014. URL: http://dx.doi.org/10.1145/2629620.
  6. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: http://dx.doi.org/10.1007/978-1-4471-5559-1.
  7. Andrew Drucker. New Limits to Classical and Quantum Instance Compression. SIAM J. Comput., 44(5):1443-1479, 2015. URL: http://dx.doi.org/10.1137/130927115.
  8. Samuel Fiorini, Nadia Hardy, Bruce Reed, and Adrian Vetta. Planar graph bipartization in linear time. Discrete Applied Mathematics, 156:1175-1180, 2008. URL: http://dx.doi.org/10.1016/j.dam.2007.08.013.
  9. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 470-479. IEEE Computer Society, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.62.
  10. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Bidimensionality and Kernels. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 503-510. SIAM, 2010. URL: http://dx.doi.org/10.1137/1.9781611973075.43.
  11. Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci., 77(1):91-106, 2011. URL: http://dx.doi.org/10.1016/j.jcss.2010.06.007.
  12. Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Multiway cuts in node weighted graphs. J. Algorithms, 50(1):49-61, 2004. URL: http://dx.doi.org/10.1016/S0196-6774(03)00111-1.
  13. Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. Uniform Kernelization Complexity of Hitting Forbidden Minors. ACM Trans. Algorithms, 13(3):35:1-35:35, 2017. URL: http://dx.doi.org/10.1145/3029051.
  14. Sylvain Guillemot. FPT algorithms for path-transversal and cycle-transversal problems. Discrete Optimization, 8(1):61-71, 2011. URL: http://dx.doi.org/10.1016/j.disopt.2010.05.003.
  15. F. Hadlock. Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing, 4:221-225, 1975. URL: http://dx.doi.org/10.1137/0204019.
  16. Bart M. P. Jansen. Polynomial Kernels for Hard Problems on Disk Graphs. In Proc. 12th SWAT, volume 6139, pages 310-321. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-13731-0_30.
  17. Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. A Near-Optimal Planarization Algorithm. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1802-1811. SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.130.
  18. Bart M. P. Jansen, Marcin Pilipczuk, and Erik Jan van Leeuwen. A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs. CoRR, abs/1810.01136, 2018. URL: http://arxiv.org/abs/1810.01136.
  19. Ken-ichi Kawarabayashi. Planarity Allowing Few Error Vertices in Linear Time. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 639-648. IEEE Computer Society, 2009. URL: http://dx.doi.org/10.1109/FOCS.2009.45.
  20. Stefan Kratsch and Magnus Wahlström. Representative Sets and Irrelevant Vertices: New Tools for Kernelization. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 450-459. IEEE Computer Society, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.46.
  21. 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. URL: http://dx.doi.org/10.1145/2635810.
  22. Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Kernelization - Preprocessing with a Guarantee. In Hans L. Bodlaender, Rod Downey, Fedor V. Fomin, and Dániel Marx, editors, The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, volume 7370 of Lecture Notes in Computer Science, pages 129-161. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-30891-8_10.
  23. Dániel Marx and Ildikó Schlotter. Obtaining a Planar Graph by Vertex Deletion. Algorithmica, 62(3-4):807-822, 2012. URL: http://dx.doi.org/10.1007/s00453-010-9484-z.
  24. Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs. CoRR, abs/1306.6593, 2013. URL: http://arxiv.org/abs/1306.6593.
  25. Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs. ACM Trans. Algorithms, 14(4):53:1-53:73, 2018. URL: http://dx.doi.org/10.1145/3239560.
  26. Igor Razgon. Large Isolating Cuts Shrink the Multiway Cut. CoRR, abs/1104.5361, 2011. URL: http://arxiv.org/abs/1104.5361.
  27. Saket Saurabh. Open problems from Recent Advances in Parameterized Complexity school, 2017. https://rapctelaviv.weebly.com/uploads 0 3 future.pdf. Google Scholar
  28. Ondřej Suchý. Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices. Algorithmica, 79:189-210, 2017. URL: http://dx.doi.org/10.1007/s00453-016-0249-1.
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