Document Open Access Logo

A Constant-Factor Approximation for Weighted Bond Cover

Authors Eun Jung Kim, Euiwoong Lee, Dimitrios M. Thilikos

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.7.pdf
  • Filesize: 0.8 MB
  • 14 pages

Document Identifiers

Author Details

Eun Jung Kim
  • Université Paris-Dauphine, PSL University, CNRS, LAMSADE, 75016, Paris, France
Euiwoong Lee
  • University of Michigan, Ann Arbor, MI, USA
Dimitrios M. Thilikos
  • LIRMM, Univ. Montpellier, CNRS, Montpellier, France

Funding

  • Kim, Eun Jung: Supported by the ANR projects ASSK (ANR-18-CE40-0025-01) and ESIGMA (ANR-17-CE23-0010) from French National Research Agency.
  • Thilikos, Dimitrios M.: Supported by the ANR projects DEMOGRAPH (ANR-16-CE40-0028), ESIGMA (ANR-17-CE23-0010), and the French-German Collaboration ANR/DFG Project UTMA (ANR-20-CE92-0027).

Cite As Get BibTex

Eun Jung Kim, Euiwoong Lee, and Dimitrios M. Thilikos. A Constant-Factor Approximation for Weighted Bond Cover. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.7

Abstract

The Weighted ℱ-Vertex Deletion for a class ℱ of graphs asks, weighted graph G, for a minimum weight vertex set S such that G-S ∈ ℱ. The case when ℱ is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for Weighted ℱ-Vertex Deletion. Only three cases of minor-closed ℱ are known to admit constant-factor approximations, namely Vertex Cover, Feedback Vertex Set and Diamond Hitting Set. We study the problem for the class ℱ of θ_c-minor-free graphs, under the equivalent setting of the Weighted c-Bond Cover problem, and present a constant-factor approximation algorithm using the primal-dual method. For this, we leverage a structure theorem implicit in [Joret et al., SIDMA'14] which states the following: any graph G containing a θ_c-minor-model either contains a large two-terminal protrusion, or contains a constant-size θ_c-minor-model, or a collection of pairwise disjoint constant-sized connected sets that can be contracted simultaneously to yield a dense graph. In the first case, we tame the graph by replacing the protrusion with a special-purpose weighted gadget. For the second and third case, we provide a weighting scheme which guarantees a local approximation ratio. Besides making an important step in the quest of (dis)proving a constant-factor approximation for Weighted ℱ-Vertex Deletion, our result may be useful as a template for algorithms for other minor-closed families.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Approximation algorithms
  • Mathematics of computing → Combinatorial algorithms
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Graph algorithms analysis
Keywords
  • Constant-factor approximation algorithms
  • Primal-dual method
  • Bonds in graphs
  • Graph minors
  • Graph modification problems

Metrics

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

Related Versions

References

  1. Akanksha Agrawal, Sudeshna Kolay, Daniel Lokshtanov, and Saket Saurabh. A faster FPT algorithm and a smaller kernel for block graph vertex deletion. In LATIN 2016: theoretical informatics, volume 9644 of Lecture Notes in Comput. Sci., pages 1-13. Springer, Berlin, 2016. URL: https://doi.org/10.1007/978-3-662-49529-2_1.
  2. Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Polylogarithmic approximation algorithms for weighted-ℱ-deletion problems. In Approximation, randomization, and combinatorial optimization. Algorithms and techniques, volume 116 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 1, 15. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018. Google Scholar
  3. Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Feedback vertex set inspired kernel for chordal vertex deletion. ACM Trans. Algorithms, 15(1):Art. 11, 28, 2019. URL: https://doi.org/10.1145/3284356.
  4. Akanksha Agrawal, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Interval vertex deletion admits a polynomial kernel. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1711-1730. SIAM, Philadelphia, PA, 2019. URL: https://doi.org/10.1137/1.9781611975482.103.
  5. Jungho Ahn, Eduard Eiben, O-joung Kwon, and Sang-il Oum. A polynomial kernel for 3-leaf power deletion. In 45th International Symposium on Mathematical Foundations of Computer Science, volume 170 of LIPIcs. Leibniz Int. Proc. Inform., pages 5:1-5:14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020. Google Scholar
  6. Jungho Ahn, Eun Jung Kim, and Euiwoong Lee. Towards constant-factor approximation for chordal / distance-hereditary vertex deletion. In Yixin Cao, Siu-Wing Cheng, and Minming Li, editors, 31st International Symposium on Algorithms and Computation, ISAAC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 181 of LIPIcs, pages 62:1-62:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2020.62.
  7. Vineet Bafna, Piotr Berman, and Toshihiro Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discret. Math., 12(3):289-297, 1999. URL: https://doi.org/10.1137/S0895480196305124.
  8. Nikhil Bansal, Daniel Reichman, and Seeun William Umboh. LP-based robust algorithms for noisy minor-free and bounded treewidth graphs. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1964-1979. SIAM, Philadelphia, PA, 2017. URL: https://doi.org/10.1137/1.9781611974782.128.
  9. Reuven Bar-Yehuda, Keren Bendel, Ari Freund, and Dror Rawitz. Local ratio: A unified framework for approximation algorithms. in memoriam: Shimon even 1935-2004. ACM Computing Surveys (CSUR), 36(4):422-463, 2004. Google Scholar
  10. Reuven Bar-Yehuda and Simon Even. A local-ratio theorem for approximating the weighted vertex cover problem. In G. Ausiello and M. Lucertini, editors, Analysis and Design of Algorithms for Combinatorial Problems, volume 109 of North-Holland Mathematics Studies, pages 27-45. North-Holland, 1985. URL: https://doi.org/10.1016/S0304-0208(08)73101-3.
  11. Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 951-970. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.57.
  12. Ann Becker and Dan Geiger. Optimization of pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artificial Intelligence, 83(1):167-188, 1996. URL: https://doi.org/10.1016/0004-3702(95)00004-6.
  13. Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. (meta) kernelization. J. ACM, 63(5):44:1-44:69, 2016. URL: https://doi.org/10.1145/2973749.
  14. Yixin Cao. Linear recognition of almost interval graphs. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1096-1115. ACM, New York, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch77.
  15. Robert D. Carr, Lisa Fleischer, Vitus J. Leung, and Cynthia A. Phillips. Strengthening integrality gaps for capacitated network design and covering problems. In David B. Shmoys, editor, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 9-11, 2000, San Francisco, CA, USA, pages 106-115. ACM/SIAM, 2000. URL: http://dl.acm.org/citation.cfm?id=338219.338241.
  16. Fabián A. Chudak, Michel X. Goemans, Dorit S. Hochbaum, and David P. Williamson. A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Res. Lett., 22(4-5):111-118, 1998. URL: https://doi.org/10.1016/S0167-6377(98)00021-2.
  17. Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, and Yusuke Kobayashi. Parameterized algorithms for maximum cut with connectivity constraints. In Bart M. P. Jansen and Jan Arne Telle, editors, 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 11-13, 2019, Munich, Germany, volume 148 of LIPIcs, pages 13:1-13:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.IPEC.2019.13.
  18. Samuel Fiorini, Gwenaël Joret, and Ugo Pietropaoli. Hitting diamonds and growing cacti. In Integer Programming and Combinatorial Optimization - IPCO 2010, volume 6080 of Lecture Notes in Comput. Sci., pages 191-204. Springer, Berlin, 2010. URL: https://doi.org/10.1007/978-3-642-13036-6_15.
  19. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, and Saket Saurabh. Hitting forbidden minors: Approximation and kernelization. SIAM J. Discret. Math., 30(1):383-410, 2016. URL: https://doi.org/10.1137/140997889.
  20. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar F-Deletion: approximation, kernelization and optimal FPT algorithms. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science - FOCS 2012, pages 470-479. IEEE Computer Soc., Los Alamitos, CA, 2012. Google Scholar
  21. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Hitting topological minors is FPT. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1317-1326. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384318.
  22. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Approximation schemes via width/weight trade-offs on minor-free graphs. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2299-2318. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.141.
  23. Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, and Michał Włodarczyk. Losing treewidth by separating subsets. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1731-1749. SIAM, Philadelphia, PA, 2019. URL: https://doi.org/10.1137/1.9781611975482.104.
  24. 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. URL: https://doi.org/10.1006/jcss.1998.1592.
  25. David J. Haglin and Shankar M. Venkatesan. Approximation and intractability results for the maximum cut problem and its variants. IEEE Trans. Computers, 40(1):110-113, 1991. URL: https://doi.org/10.1109/12.67327.
  26. Ken ichi Kawarabayashi, Yusuke Kobayashi, and Bruce Reed. The disjoint paths problem in quadratic time. Journal of Combinatorial Theory, Series B, 102(2):424-435, 2012. URL: https://doi.org/10.1016/j.jctb.2011.07.004.
  27. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  28. Bart M. P. Jansen and Marcin Pilipczuk. Approximation and kernelization for chordal vertex deletion. SIAM J. Discrete Math., 32(3):2258-2301, 2018. URL: https://doi.org/10.1137/17M112035X.
  29. Gwenaël Joret, Christophe Paul, Ignasi Sau, Saket Saurabh, and Stéphan Thomassé. Hitting and harvesting pumpkins. SIAM J. Discret. Math., 28(3):1363-1390, 2014. URL: https://doi.org/10.1137/120883736.
  30. Ken-ichi Kawarabayashi and Anastasios Sidiropoulos. Polylogarithmic approximation for minimum planarization (almost). In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 779-788. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.77.
  31. Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Trans. Algorithms, 12(2):21:1-21:41, 2016. URL: https://doi.org/10.1145/2797140.
  32. Eun Jung Kim, Euiwoong Lee, and Dimitrios M. Thilikos. A constant-factor approximation for weighted bond cover, 2021. URL: http://arxiv.org/abs/2105.00857.
  33. Stefan Kratsch and Magnus Wahlström. Compression via matroids: a randomized polynomial kernel for odd cycle transversal. ACM Trans. Algorithms, 10(4):Art. 20, 15, 2014. URL: https://doi.org/10.1145/2635810.
  34. Robert Krauthgamer and Inbal Rika. Mimicking networks and succinct representations of terminal cuts. In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1789-1799. SIAM, 2013. URL: https://doi.org/10.1137/1.9781611973105.128.
  35. John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is NP-complete. J. Comput. System Sci., 20(2):219-230, 1980. ACM-SIGACT Symposium on the Theory of Computing (San Diego, Calif., 1978). Google Scholar
  36. Stratis Limnios, Christophe Paul, Joanny Perret, and Dimitrios M. Thilikos. Edge degeneracy: Algorithmic and structural results. Theor. Comput. Sci., 839:164-175, 2020. URL: https://doi.org/10.1016/j.tcs.2020.06.006.
  37. Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, and Saket Saurabh. A (2 + ε)-factor approximation algorithm for split vertex deletion. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 80:1-80:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.80.
  38. Anand Louis, Prasad Raghavendra, and Santosh Vempala. The complexity of approximating vertex expansion. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 360-369. IEEE, 2013. Google Scholar
  39. Carsten Lund and Mihalis Yannakakis. The approximation of maximum subgraph problems. In Andrzej Lingas, Rolf G. Karlsson, and Svante Carlsson, editors, Automata, Languages and Programming, 20nd International Colloquium, ICALP93, Lund, Sweden, July 5-9, 1993, Proceedings, volume 700 of Lecture Notes in Computer Science, pages 40-51. Springer, 1993. URL: https://doi.org/10.1007/3-540-56939-1_60.
  40. George L. Nemhauser and Leslie E. Trotter Jr. Properties of vertex packing and independence system polyhedra. Math. Program., 6(1):48-61, 1974. URL: https://doi.org/10.1007/BF01580222.
  41. Bruce Reed, Kaleigh Smith, and Adrian Vetta. Finding odd cycle transversals. Oper. Res. Lett., 32(4):299-301, 2004. URL: https://doi.org/10.1016/j.orl.2003.10.009.
  42. Neil Robertson and Paul D. Seymour. Graph minors. V. excluding a planar graph. J. Comb. Theory, Ser. B, 41(1):92-114, 1986. URL: https://doi.org/10.1016/0095-8956(86)90030-4.
  43. Neil Robertson and Paul D. Seymour. Graph minors. XX. Wagner’s conjecture. J. Comb. Theory, Ser. B, 92(2):325-357, 2004. URL: https://doi.org/10.1016/j.jctb.2004.08.001.
  44. Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. An fpt-algorithm for recognizing k-apices of minor-closed graph classes. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 95:1-95:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.95.
  45. Wouter Cames van Batenburg, Tony Huynh, Gwenaël Joret, and Jean-Florent Raymond. A tight erdős-pósa function for planar minors. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1485-1500. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.90.
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 About DROPS Imprint Privacy Contact