Document Open Access Logo

(In)approximability of Maximum Minimal FVS

Authors Louis Dublois, Tesshu Hanaka , Mehdi Khosravian Ghadikolaei, Michael Lampis , Nikolaos Melissinos

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2020.3.pdf
  • Filesize: 1.67 MB
  • 14 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Approximation Algorithms
  • ETH
  • Inapproximability

Metrics

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

Abstract

We study the approximability of the NP-complete Maximum Minimal Feedback Vertex Set problem. Informally, this natural problem seems to lie in an intermediate space between two more well-studied problems of this type: Maximum Minimal Vertex Cover, for which the best achievable approximation ratio is √n, and Upper Dominating Set, which does not admit any n^{1-ε} approximation. We confirm and quantify this intuition by showing the first non-trivial polynomial time approximation for Max Min FVS with a ratio of O(n^{2/3}), as well as a matching hardness of approximation bound of n^{2/3-ε}, improving the previous known hardness of n^{1/2-ε}. Along the way, we also obtain an O(Δ)-approximation and show that this is asymptotically best possible, and we improve the bound for which the problem is NP-hard from Δ ≥ 9 to Δ ≥ 6. 
Having settled the problem’s approximability in polynomial time, we move to the context of super-polynomial time. We devise a generalization of our approximation algorithm which, for any desired approximation ratio r, produces an r-approximate solution in time n^O(n/r^{3/2}). This time-approximation trade-off is essentially tight: we show that under the ETH, for any ratio r and ε > 0, no algorithm can r-approximate this problem in time n^{O((n/r^{3/2})^{1-ε})}, hence we precisely characterize the approximability of the problem for the whole spectrum between polynomial and sub-exponential time, up to an arbitrarily small constant in the second exponent.

Cite As Get BibTex

Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, and Nikolaos Melissinos. (In)approximability of Maximum Minimal FVS. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ISAAC.2020.3

Author Details

Louis Dublois
  • Université Paris-Dauphine, PSL Research University, CNRS, UMR 7243, LAMSADE, Paris, France
Tesshu Hanaka
  • Chuo University, Tokyo, Japan
Mehdi Khosravian Ghadikolaei
  • Université Paris-Dauphine, PSL Research University, CNRS, UMR 7243, LAMSADE, Paris, France
Michael Lampis
  • Université Paris-Dauphine, PSL Research University, CNRS, UMR 7243, LAMSADE, Paris, France
Nikolaos Melissinos
  • Université Paris-Dauphine, PSL Research University, CNRS, UMR 7243, LAMSADE, Paris, France

Funding

This work is partially supported by PRC CNRS JSPS project PARAGA and by JSPS KAKENHI Grant Number JP19K21537.

References

  1. Hassan AbouEisha, Shahid Hussain, Vadim V. Lozin, Jérôme Monnot, Bernard Ries, and Viktor Zamaraev. Upper domination: Towards a dichotomy through boundary properties. Algorithmica, 80(10):2799-2817, 2018. URL: https://doi.org/10.1007/s00453-017-0346-9.
  2. Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, and Florian Sikora. Grundy coloring & friends, half-graphs, bicliques. In STACS, volume 154 of LIPIcs, pages 58:1-58:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.58.
  3. Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, and Steven Skiena. The lazy bureaucrat scheduling problem. Inf. Comput., 184(1):129-146, 2003. URL: https://doi.org/10.1016/S0890-5401(03)00060-9.
  4. Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, and Jesper Nederlof. New tools and connections for exponential-time approximation. Algorithmica, 81(10):3993-4009, 2019. URL: https://doi.org/10.1007/s00453-018-0512-8.
  5. Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Kim-Manuel Klein, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, and Vangelis Th. Paschos. The many facets of upper domination. Theoretical Computer Science, 717:2-25, 2018. URL: https://doi.org/10.1016/j.tcs.2017.05.042.
  6. Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Yota Otachi. Grundy distinguishes treewidth from pathwidth. CoRR, abs/2008.07425, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.14.
  7. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput., 243:86-111, 2015. URL: https://doi.org/10.1016/j.ic.2014.12.008.
  8. Édouard Bonnet, Michael Lampis, and Vangelis Th. Paschos. Time-approximation trade-offs for inapproximable problems. Journal of Computer and System Sciences, 92:171-180, 2018. URL: https://doi.org/10.1016/j.jcss.2017.09.009.
  9. Nicolas Boria, Federico Della Croce, and Vangelis Th. Paschos. On the max min vertex cover problem. Discrete Applied Mathematics, 196:62-71, 2015. URL: https://doi.org/10.1016/j.dam.2014.06.001.
  10. Nicolas Bourgeois, Bruno Escoffier, and Vangelis Th. Paschos. Approximation of min coloring by moderately exponential algorithms. Inf. Process. Lett., 109(16):950-954, 2009. URL: https://doi.org/10.1016/j.ipl.2009.05.002.
  11. Arman Boyaci and Jérôme Monnot. Weighted upper domination number. Electron. Notes Discret. Math., 62:171-176, 2017. URL: https://doi.org/10.1016/j.endm.2017.10.030.
  12. Parinya Chalermsook, Bundit Laekhanukit, and Danupon Nanongkai. Independent set, induced matching, and pricing: Connections and tight (subexponential time) approximation hardnesses. In FOCS, pages 370-379. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/FOCS.2013.47.
  13. Grant A. Cheston, Gerd Fricke, Stephen T. Hedetniemi, and David Pokrass Jacobs. On the computational complexity of upper fractional domination. Discret. Appl. Math., 27(3):195-207, 1990. URL: https://doi.org/10.1016/0166-218X(90)90065-K.
  14. Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst., 33(2):125-150, 2000. URL: https://doi.org/10.1007/s002249910009.
  15. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer International Publishing, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  16. Marek Cygan, Lukasz Kowalik, and Mateusz Wykurz. Exponential-time approximation of weighted set cover. Inf. Process. Lett., 109(16):957-961, 2009. URL: https://doi.org/10.1016/j.ipl.2009.05.003.
  17. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In FOCS, pages 150-159. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/FOCS.2011.23.
  18. Marek Cygan and Marcin Pilipczuk. Exact and approximate bandwidth. Theor. Comput. Sci., 411(40-42):3701-3713, 2010. URL: https://doi.org/10.1016/j.tcs.2010.06.018.
  19. Marc Demange. A note on the approximation of a minimum-weight maximal independent set. Computational Optimization and Applications, 14(1):157-169, 1999. URL: https://doi.org/10.1023/A:1008765214400.
  20. Bruno Escoffier, Vangelis Th. Paschos, and Emeric Tourniaire. Approximating MAX SAT by moderately exponential and parameterized algorithms. Theor. Comput. Sci., 560:147-157, 2014. URL: https://doi.org/10.1016/j.tcs.2014.10.039.
  21. Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, and Yusuke Kobayashi. Parameterized Algorithms for Maximum Cut with Connectivity Constraints. In IPEC 2019, pages 13:1-13:15, 2019. URL: https://doi.org/10.4230/LIPIcs.IPEC.2019.13.
  22. Dimitris Fotakis, Michael Lampis, and Vangelis Th. Paschos. Sub-exponential approximation schemes for csps: From dense to almost sparse. In STACS, volume 47 of LIPIcs, pages 37:1-37:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.STACS.2016.37.
  23. Fabio Furini, Ivana Ljubic, and Markus Sinnl. An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem. European Journal of Operational Research, 262(2):438-448, 2017. URL: https://doi.org/10.1016/j.ejor.2017.03.061.
  24. Laurent Gourvès, Jérôme Monnot, and Aris Pagourtzis. The lazy bureaucrat problem with common arrivals and deadlines: Approximation and mechanism design. In FCT, volume 8070 of Lecture Notes in Computer Science, pages 171-182. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40164-0_18.
  25. Tesshu Hanaka, Hans L. Bodlaender, Tom C. van der Zanden, and Hirotaka Ono. On the maximum weight minimal separator. Theoretical Computer Science, 796:294-308, 2019. URL: https://doi.org/10.1016/j.tcs.2019.09.025.
  26. Ararat Harutyunyan, Mehdi Khosravian Ghadikolaei, Nikolaos Melissinos, Jérôme Monnot, and Aris Pagourtzis. On the complexity of the upper r-tolerant edge cover problem. In Luís Soares Barbosa and Mohammad Ali Abam, editors, Topics in Theoretical Computer Science - Third IFIP WG 1.8 International Conference, TTCS 2020, Tehran, Iran, July 1-2, 2020, Proceedings, volume 12281 of Lecture Notes in Computer Science, pages 32-47. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-57852-7_3.
  27. Johan Håstad. Clique is hard to approximate within n^1-ε. Acta Math, 182:105-142, 1999. Google Scholar
  28. Michael A. Henning and Dinabandhu Pradhan. Algorithmic aspects of upper paired-domination in graphs. Theor. Comput. Sci., 804:98-114, 2020. URL: https://doi.org/10.1016/j.tcs.2019.10.045.
  29. Ken Iwaide and Hiroshi Nagamochi. An improved algorithm for parameterized edge dominating set problem. J. Graph Algorithms Appl., 20(1):23-58, 2016. URL: https://doi.org/10.7155/jgaa.00383.
  30. Michael S. Jacobson and Kenneth Peters. Chordal graphs and upper irredundance, upper domination and independence. Discret. Math., 86(1-3):59-69, 1990. URL: https://doi.org/10.1016/0012-365X(90)90349-M.
  31. Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Improved (in-)approximability bounds for d-scattered set. In WAOA, volume 11926 of Lecture Notes in Computer Science, pages 202-216. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-39479-0_14.
  32. Kaveh Khoshkhah, Mehdi Khosravian Ghadikolaei, Jérôme Monnot, and Florian Sikora. Weighted upper edge cover: Complexity and approximability. J. Graph Algorithms Appl., 24(2):65-88, 2020. URL: https://doi.org/10.7155/jgaa.00519.
  33. Sounaka Mishra and Kripasindhu Sikdar. On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem. RAIRO Theor. Informatics Appl., 35(3):287-309, 2001. URL: https://doi.org/10.1051/ita:2001121.
  34. Meirav Zehavi. Maximum minimal vertex cover parameterized by vertex cover. SIAM Journal on Discrete Mathematics, 31(4):2440-2456, 2017. URL: https://doi.org/10.1137/16M109017X.
  35. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3(1):103-128, 2007. URL: https://doi.org/10.4086/toc.2007.v003a006.
  36. Igor E. Zvervich and Vadim E. Zverovich. An induced subgraph characterization of domination perfect graphs. Journal of Graph Theory, 20(3):375-395, 1995. URL: https://doi.org/10.1002/jgt.3190200313.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact