Document Open Access Logo

Hitting Weighted Even Cycles in Planar Graphs

Authors Alexander Göke, Jochen Koenemann, Matthias Mnich , Hao Sun

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.25.pdf
  • Filesize: 1.1 MB
  • 23 pages

Document Identifiers

Author Details

Alexander Göke
  • Hamburg University of Technology, Institute for Algorithms and Complexity, Germany
Jochen Koenemann
  • University of Waterloo, Canada
Matthias Mnich
  • Hamburg University of Technology, Institute for Algorithms and Complexity, Germany
Hao Sun
  • University of Waterloo, Canada

Funding

  • Koenemann, Jochen: Research funded by the NSERC Discovery Grant program.
  • Sun, Hao: Research funded by the NSERC Discovery Grant program.

Cite AsGet BibTex

Alexander Göke, Jochen Koenemann, Matthias Mnich, and Hao Sun. Hitting Weighted Even Cycles in Planar Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 25:1-25:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.25

Abstract

A classical branch of graph algorithms is graph transversals, where one seeks a minimum-weight subset of nodes in a node-weighted graph G which intersects all copies of subgraphs F from a fixed family F. Many such graph transversal problems have been shown to admit polynomial-time approximation schemes (PTAS) for planar input graphs G, using a variety of techniques like the shifting technique (Baker, J. ACM 1994), bidimensionality (Fomin et al., SODA 2011), or connectivity domination (Cohen-Addad et al., STOC 2016). These techniques do not seem to apply to graph transversals with parity constraints, which have recently received significant attention, but for which no PTASs are known. In the even-cycle transversal (ECT) problem, the goal is to find a minimum-weight hitting set for the set of even cycles in an undirected graph. For ECT, Fiorini et al. (IPCO 2010) showed that the integrality gap of the standard covering LP relaxation is Θ(log n), and that adding sparsity inequalities reduces the integrality gap to 10. Our main result is a primal-dual algorithm that yields a 47/7 ≈ 6.71-approximation for ECT on node-weighted planar graphs, and an integrality gap of the same value for the standard LP relaxation on node-weighted planar graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
Keywords
  • Even cycles
  • planar graphs
  • integrality gap

Metrics

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

Related Versions

References

  1. Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev. O(√log n) approximation algorithms for min uncut, min 2CNF deletion, and directed cut problems. In Proc. STOC 2005, pages 573-581, 2005. Google Scholar
  2. Vineet Bafna, Piotr Berman, and Toshihiro Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math., 12:289-297, 1999. Google Scholar
  3. Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs. J. ACM, 41(1):153-180, 1994. Google Scholar
  4. Mohammadhossein Bateni, Mohammadtaghi Hajiaghayi, and Dániel Marx. Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. J. ACM, 58(5), 2011. Google Scholar
  5. Ann Becker and Dan Geiger. Optimization of Pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artif. Intelligence, 83(1):167-188, 1996. Google Scholar
  6. Piotr Berman and Grigory Yaroslavtsev. Primal-dual approximation algorithms for node-weighted network design in planar graphs. In Proc. APPROX 2012, volume 7408 of Lecture Notes Comput. Sci., pages 50-60, 2012. Google Scholar
  7. Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, and David Meierfrankenfeld. Approximating connectivity domination in weighted bounded-genus graphs. In Proc. STOC 2016, pages 584-597, 2016. Google Scholar
  8. Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Bidimensional parameters and local treewidth. SIAM J. Discrete Math., 18(3):501-511, 2004. Google Scholar
  9. Erik D. Demaine, Mohammadtaghi Hajiaghayi, and Philip N. Klein. Node-weighted Steiner tree and group Steiner tree in planar graphs. ACM Trans. Algorithms, 10(3), 2014. Google Scholar
  10. Yevgeniy Y. Dorfman and Galina Orlova. Finding the maximal cut in a graph. Engineering Cybernetics, 10(3), 1972. Google Scholar
  11. Samuel Fiorini, Gwenaël Joret, and Ugo Pietropaoli. Hitting diamonds and growing cacti. In Proc. IPCO 2010, volume 6080 of Lecture Notes Comput. Sci., pages 191-204, 2010. Google Scholar
  12. Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Bidimensionality and EPTAS. In Proc. SODA 2011, pages 748-759, 2011. Google Scholar
  13. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Bidimensionality and kernels. In Proc. SODA 2010, pages 503-510, 2010. Google Scholar
  14. Michel X. Goemans and David P. Williamson. Primal-dual approximation algorithms for feedback problems in planar graphs. Combinatorica, 18(1):37-59, 1998. Google Scholar
  15. Alexander Göke, Jochen Koenemann, Matthias Mnich, and Hao Sun. Hitting weighted even cycles in planar graphs, 2021. URL: http://arxiv.org/abs/2107.04763.
  16. Frank Hadlock. Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput., 4(3), 1975. Google Scholar
  17. Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85-103, 1972. Google Scholar
  18. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2 - ε. J. Comput. Syst. Sci., 74(3):335-349, 2008. Google Scholar
  19. Daniel Lokshtanov and MS Ramanujan. Parameterized tractability of multiway cut with parity constraints. In Proc. ICALP 2012, volume 7391 of Lecture Notes Comput. Sci., pages 750-761, 2012. Google Scholar
  20. Daniel Lokshtanov, MS Ramanujan, Saket Saurab, and Meirav Zehavi. Parameterized complexity and approximability of directed odd cycle transversal. In Proc. SODA 2020, pages 2181-2200, 2020. Google Scholar
  21. Pranabendu Misra, Venkatesh Raman, MS Ramanujan, and Saket Saurabh. Parameterized algorithms for even cycle transversal. In Proc. WG 2012, volume 7551 of Lecture Notes Comput. Sci., pages 172-183, 2012. Google Scholar
  22. Carsten Moldenhauer. Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs. Inf. Comput., 222:748-759, July 2011. Google Scholar
  23. Martin Nägele and Rico Zenklusen. A new contraction technique with applications to congruency-constrained cuts. Math. Prog., 183:455-481, 2020. 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