Document Open Access Logo

Parameterized Complexity of Fair Vertex Evaluation Problems

Authors Dušan Knop , Tomáš Masařík , Tomáš Toufar

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.33.pdf
  • Filesize: 0.56 MB
  • 16 pages

Document Identifiers

Author Details

Dušan Knop
  • Algorithmics and Computational Complexity, Faculty IV, TU Berlin
  • Department of Theoretical Computer Science, Faculty of Information Technology,\and Czech Technical University in Prague, Prague, Czech Republic
Tomáš Masařík
  • Department of Applied Mathematics, Charles University, Prague, Czech Republic\and Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland
Tomáš Toufar
  • Computer Science Institute, Charles University, Prague, Czech Republic

Funding

  • Knop, Dušan: Supported by DFG under project "MaMu", NI 369/19 and partly supported by the OP VVV MEYS funded project CZ.02.1.01/0.0/0.0/16 019/0000765 “Research Center for Informatics”.
  • Masařík, Tomáš: Author was supported by SVV - 2017 - 260452 and by GAUK 1514217 of Charles University and by the CE-ITI grant project P202/12/G061 of GA ČR.

Cite As Get BibTex

Dušan Knop, Tomáš Masařík, and Tomáš Toufar. Parameterized Complexity of Fair Vertex Evaluation Problems. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.33

Abstract

A prototypical graph problem is centered around a graph-theoretic property for a set of vertices and a solution to it is a set of vertices for which the desired property holds. The task is to decide whether, in the given graph, there exists a solution of a certain quality, where we use size as a quality measure. In this work, we are changing the measure to the fair measure (cf. Lin and Sahni [Li-Shin Lin and Sartaj Sahni, 1989]). The fair measure of a set of vertices S is (at most) k if the number of neighbors in the set S of any vertex (in the input graph) does not exceed k. One possible way to study graph problems is by defining the property in a certain logic. For a given objective, an evaluation problem is to find a set (of vertices) that simultaneously minimizes the assumed measure and satisfies an appropriate formula. More formally, we study the {MSO} Fair Vertex Evaluation, where the graph-theoretic property is described by an {MSO} formula.
In the presented paper we show that there is an FPT algorithm for the {MSO} Fair Vertex Evaluation problem for formulas with one free variable parameterized by the twin cover number of the input graph and the size of the formula. One may define an extended variant of {MSO} Fair Vertex Evaluation for formulas with l free variables; here we measure a maximum number of neighbors in each of the l sets. However, such variant is {W[1]}-hard for parameter l even on graphs with twin cover one.
Furthermore, we study the Fair Vertex Cover (Fair VC) problem. Fair VC is among the simplest problems with respect to the demanded property (i.e., the rest forms an edgeless graph). On the negative side, Fair VC is {W[1]}-hard when parameterized by both treedepth and feedback vertex set of the input graph. On the positive side, we provide an FPT algorithm for the parameter modular width.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Logic
  • Theory of computation → Graph algorithms analysis
Keywords
  • Fair objective
  • metatheorem
  • fair vertex cover
  • twin cover
  • modular width

Metrics

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

Related Versions

References

  1. Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy Problems for Tree-Decomposable Graphs. Journal of Algorithms, 12(2):308-340, June 1991. URL: https://doi.org/10.1016/0196-6774(91)90006-k.
  2. Jianer Chen, Benny Chor, Michael R. Fellows, Xiuzhen Huang, David Juedes, Iyad A. Kanj, and Ge Xia. Tight lower bounds for certain parameterized NP-hard problems. Information and Computation, 201(2):216-231, 2005. URL: https://doi.org/10.1016/j.ic.2005.05.001.
  3. Morgan Chopin, André Nichterlein, Rolf Niedermeier, and Mathias Weller. Constant Thresholds Can Make Target Set Selection Tractable. Theory Comput. Syst., 55(1):61-83, 2014. URL: https://doi.org/10.1007/s00224-013-9499-3.
  4. Bruno Courcelle. The Monadic Second-order Logic of Graphs. I. Recognizable Sets of Finite Graphs. Information and Computation, 85(1):12-75, March 1990. URL: https://doi.org/10.1016/0890-5401(90)90043-h.
  5. Bruno Courcelle and Mohamed Mosbah. Monadic Second-Order Evaluations on Tree-Decomposable Graphs. Theor. Comput. Sci., 109(1&2):49-82, 1993. URL: https://doi.org/10.1016/0304-3975(93)90064-z.
  6. Lenore J. Cowen, Robert Cowen, and Douglas R. Woodall. Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency. Journal of Graph Theory, 10(2):187-195, 1986. URL: https://doi.org/10.1002/jgt.3190100207.
  7. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  8. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  9. Markus Frick and Martin Grohe. The complexity of first-order and monadic second-order logic revisited. Annals of Pure and Applied Logic, 130(1):3-31, 2004. Papers presented at the 2002 IEEE Symposium on Logic in Computer Science (LICS). URL: https://doi.org/10.1016/j.apal.2004.01.007.
  10. Jakub Gajarský and Petr Hliněný. Kernelizing MSO Properties of Trees of Fixed Height, and Some Consequences. Logical Methods in Computer Science, Volume 11, Issue 1, April 2015. URL: https://doi.org/10.2168/LMCS-11(1:19)2015.
  11. Jakub Gajarský, Petr Hliněný, Jan Obdržálek, Daniel Lokshtanov, and M. S. Ramanujan. A New Perspective on FO Model Checking of Dense Graph Classes. In Martin Grohe, Eric Koskinen, and Natarajan Shankar, editors, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, New York, NY, USA, July 5-8, 2016, pages 176-184. ACM, 2016. URL: https://doi.org/10.1145/2933575.2935314.
  12. Robert Ganian. Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics. In Dániel Marx and Peter Rossmanith, editors, Parameterized and Exact Computation - 6th International Symposium IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers, volume 7112 of Lecture Notes in Computer Science, pages 259-271. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-28050-4_21.
  13. Robert Ganian. Improving Vertex Cover as a Graph Parameter. Discrete Mathematics & Theoretical Computer Science, 17(2):77-100, 2015. URL: http://dmtcs.episciences.org/2136.
  14. Robert Ganian, Petr Hliněný, Jaroslav Nešetřil, Jan Obdržálek, and Patrice Ossona de Mendez. Shrub-depth: Capturing Height of Dense Graphs. Logical Methods in Computer Science, 15(1), 2019. URL: https://lmcs.episciences.org/5149.
  15. Robert Ganian and Jan Obdržálek. Expanding the Expressive Power of Monadic Second-Order Logic on Restricted Graph Classes. In Thierry Lecroq and Laurent Mouchard, editors, Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers, volume 8288 of Lecture Notes in Computer Science, pages 164-177. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-45278-9_15.
  16. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding First-Order Properties of Nowhere Dense Graphs. J. ACM, 64(3):17:1-17:32, 2017. URL: https://doi.org/10.1145/3051095.
  17. Frédéric Havet, Ross J. Kang, and Jean-Sébastien Sereni. Improper coloring of unit disk graphs. Networks, 54(3):150-164, 2009. URL: https://doi.org/10.1002/net.20318.
  18. Klaus Jansen, Stefan Kratsch, Dániel Marx, and Ildikó Schlotter. Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci., 79(1):39-49, 2013. URL: https://doi.org/10.1016/j.jcss.2012.04.004.
  19. Ross J. Kang, Tobias Müller, and Jean-Sébastien Sereni. Improper colouring of (random) unit disk graphs. Discrete Mathematics, 308(8):1438-1454, 2008. Third European Conference on Combinatorics. URL: https://doi.org/10.1016/j.disc.2007.07.070.
  20. Dušan Knop, Martin Koutecký, Tomáš Masařík, and Tomáš Toufar. Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity. In Hans L. Bodlaender and Gerhard J. Woeginger, editors, Graph-Theoretic Concepts in Computer Science: 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers, pages 344-357, Cham, 2017. Springer International Publishing. URL: https://doi.org/10.1007/978-3-319-68705-6_26.
  21. Petr Kolman, Bernard Lidický, and Jean-Sébastien Sereni. Fair Edge Deletion Problems on TreeDecomposable Graphs and Improper Colorings, 2010. URL: http://orion.math.iastate.edu/lidicky/pub/kls10.pdf.
  22. Petr Kolman, Bernard Lidický, and Jean-Sébastien Sereni. On Fair Edge Deletion Problems, 2009. URL: https://kam.mff.cuni.cz/~kolman/papers/kls09.pdf.
  23. Juha Kontinen and Hannu Niemistö. Extensions of MSO and the monadic counting hierarchy. Information and Computation, 209(1):1-19, 2011. URL: https://doi.org/10.1016/j.ic.2010.09.002.
  24. Michael Lampis. Algorithmic Meta-theorems for Restrictions of Treewidth. Algorithmica, 64(1):19-37, 2012. URL: https://doi.org/10.1007/s00453-011-9554-x.
  25. Michael Lampis. Model Checking Lower Bounds for Simple Graphs. Logical Methods in Computer Science, 10(1):1-21, 2014. URL: https://doi.org/10.2168/LMCS-10(1:18)2014.
  26. Leonid Libkin. Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2004. Google Scholar
  27. Li-Shin Lin and Sartaj Sahni. Fair Edge Deletion Problems. IEEE Trans. Comput., 38(5):756-761, 1989. URL: https://doi.org/10.1109/12.24280.
  28. Tomáš Masařík and Tomáš Toufar. Parameterized Complexity of Fair Deletion Problems. In T.V. Gopal, Gerhard Jäger, and Silvia Steila, editors, Theory and Applications of Models of Computation: 14th Annual Conference, TAMC 2017, Bern, Switzerland, April 20-22, 2017, Proceedings, pages 628-642, Cham, 2017. Springer International Publishing. URL: https://doi.org/10.1007/978-3-319-55911-7_45.
  29. Tomáš Masařík and Tomáš Toufar. Parameterized complexity of fair deletion problems. Discrete Applied Mathematics, 2019. URL: https://doi.org/10.1016/j.dam.2019.06.001.
  30. Jiří Matoušek and Jaroslav Nešetřil. Invitation to Discrete Mathematics (2. ed.). Oxford University Press, 2009. Google Scholar
  31. Jaroslav Nešetřil and Patrice Ossona De Mendez. Sparsity: graphs, structures, and algorithms, volume 28. Springer Science & Business Media, 2012. URL: https://doi.org/10.1007/978-3-642-27875-4.
  32. Timm Oertel, Christian Wagner, and Robert Weismantel. Integer convex minimization by mixed integer linear optimization. Operations Research Letters, 42(6):424-428, 2014. URL: https://doi.org/10.1016/j.orl.2014.07.005.
  33. Michał Pilipczuk. Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach. In Filip Murlak and Piotr Sankowski, editors, Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011. Proceedings, volume 6907 of Lecture Notes in Computer Science, pages 520-531. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-22993-0_47.
  34. Detlef Seese. Linear Time Computable Problems and First-Order Descriptions. Mathematical Structures in Computer Science, 6(6):505-526, 1996. Google Scholar
  35. Stefan Szeider. Monadic second order logic on graphs with local cardinality constraints. ACM Trans. Comput. Log, 12(2):1-21, 2011. URL: https://doi.org/10.1145/1877714.1877718.
  36. Marc Tedder, Dereck G. Corneil, Michel Habib, and Christophe Paul. Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations. In ICALP 2008, pages 634-645, 2008. URL: https://doi.org/10.1007/978-3-540-70575-8_52.
  37. Mihalis Yannakakis. Edge-Deletion Problems. SIAM J. Comput., 10(2):297-309, 1981. URL: https://doi.org/10.1137/0210021.
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