Document Open Access Logo

On Existential MSO and its Relation to ETH

Authors Robert Ganian, Ronald de Haan, Iyad Kanj, Stefan Szeider

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.42.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Robert Ganian
Ronald de Haan
Iyad Kanj
Stefan Szeider

Cite AsGet BibTex

Robert Ganian, Ronald de Haan, Iyad Kanj, and Stefan Szeider. On Existential MSO and its Relation to ETH. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.MFCS.2016.42

Abstract

Impagliazzo et al. proposed a framework, based on the logic fragment defining the complexity class SNP, to identify problems that are equivalent to k-CNF-Sat modulo subexponential-time reducibility (serf-reducibility). The subexponential-time solvability of any of these problems implies the failure of the Exponential Time Hypothesis (ETH). In this paper, we extend the framework of Impagliazzo et al., and identify a larger set of problems that are equivalent to k-CNF-Sat modulo serf-reducibility. We propose a complexity class, referred to as Linear Monadic NP, that consists of all problems expressible in existential monadic second order logic whose expressions have a linear measure in terms of a complexity parameter, which is usually the universe size of the problem. This research direction can be traced back to Fagin's celebrated theorem stating that NP coincides with the class of problems expressible in existential second order logic. Monadic NP, a well-studied class in the literature, is the restriction of the aforementioned logic fragment to existential monadic second order logic. The proposed class Linear Monadic NP is then the restriction of Monadic NP to problems whose expressions have linear measure in the complexity parameter. We show that Linear Monadic NP includes many natural complete problems such as the satisfiability of linear-size circuits, dominating set, independent dominating set, and perfect code. Therefore, for any of these problems, its subexponential-time solvability is equivalent to the failure of ETH. We prove, using logic games, that the aforementioned problems are inexpressible in the monadic fragment of SNP, and hence, are not captured by the framework of Impagliazzo et al. Finally, we show that Feedback Vertex Set is inexpressible in existential monadic second order logic, and hence is not in Linear Monadic NP, and investigate the existence of certain reductions between Feedback Vertex Set (and variants of it) and 3-CNF-Sat.
Keywords
  • exponential time hypothesis (ETH)
  • monadic second order logic
  • subexponential time complexity
  • serf-reducibility
  • logic games

Metrics

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

References

  1. Miklós Ajtai and Ronald Fagin. Reachability is harder for directed than for undirected finite graphs. J. Symb. Log., 55(1):113-150, 1990. Google Scholar
  2. Miklós Ajtai, Ronald Fagin, and Larry J. Stockmeyer. The closure of monadic NP. J. Comput. Syst. Sci., 60(3):660-716, 2000. Google Scholar
  3. Sanjeev Arora and Ronald Fagin. On winning strategies in Ehrenfeucht-Fraïssé games. Theor. Comput. Sci., 174(1-2):97-121, 1997. Google Scholar
  4. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. A duality between clause width and clause density for SAT. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic, pages 252-260. IEEE Computer Society, 2006. Google Scholar
  5. Karthekeyan Chandrasekaran, Richard M. Karp, Erick Moreno-Centeno, and Santosh Vempala. Algorithms for implicit hitting set problems. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 614-629. SIAM, 2011. Google Scholar
  6. Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David Juedes, Iyad Kanj, and Ge Xia. Tight lower bounds for certain parameterized NP-hard problems. Information and Computation, 201(2):216-231, 2005. Google Scholar
  7. Jianer Chen, Xiuzhen Huang, Iyad Kanj, and Ge Xia. Strong computational lower bounds via parameterized complexity. J. of Computer and System Sciences, 72(8):1346-1367, 2006. Google Scholar
  8. Jianer Chen, Iyad Kanj, and Ge Xia. On parameterized exponential time complexity. Theoretical Computer Science, 410(27-29):2641-2648, 2009. Google Scholar
  9. Margaret B. Cozzens and Laura L. Kelleher. Dominating cliques in graphs. Discrete Mathematics, 86(1-3):101-116, 1990. Google Scholar
  10. Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, and Arkadiusz Socala. Tight bounds for graph homomorphism and subgraph isomorphism. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1643-1649, 2016. Google Scholar
  11. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  12. Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan, and Uwe Schöning. A deterministic (2-2/(k+1))ⁿ algorithm for k-SAT based on local search. Theoretical Computer Science, 289(1):69-83, 2002. Google Scholar
  13. 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. Google Scholar
  14. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer Verlag, New York, 1999. Google Scholar
  15. Ronald Fagin. Generalized first-order spectra, and polynomial. time recognizable sets. SIAM-AMS Proceedings, 7:43-73, 1974. Google Scholar
  16. Ronald Fagin, Larry J. Stockmeyer, and Moshe Y. Vardi. On monadic NP vs. monadic co-NP. Information and Computation, 120(1):78-92, 1995. Google Scholar
  17. Jörg Flum and Martin Grohe. Parameterized Complexity Theory, volume XIV of Texts in Theoretical Computer Science. An EATCS Series. Springer Verlag, Berlin, 2006. Google Scholar
  18. Fedor V. Fomin, Serge Gaspers, Artem V. Pyatkin, and Igor Razgon. On the minimum feedback vertex set problem: Exact and enumeration algorithms. Algorithmica, 52(2):293-307, 2008. Google Scholar
  19. Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Springer Verlag, 2010. Google Scholar
  20. Michael R. Garey and David R. Johnson. Computers and Intractability. W. H. Freeman and Company, New York, San Francisco, 1979. Google Scholar
  21. Adriana Hansberg, Dirk Meierling, and Lutz Volkmann. Distance domination and distance irredundance in graphs. Electr. J. Comb., 14(1), 2007. Google Scholar
  22. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  23. David Janin and Jerzy Marcinkowski. A toolkit for first order extensions of monadic games. In Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer, volume 2010 of Lecture Notes in Computer Science, pages 353-364. Springer, 2001. Google Scholar
  24. Iyad Kanj and Stefan Szeider. Parameterized and subexponential-time complexity of satisfiability problems and applications. Theoretical Computer Science, 607:282-295, 2015. Google Scholar
  25. Martin Kreidler and Detlef Seese. Monadic NP and graph minors. In Proceedings of the 12th International Workshop on Computer Science Logic, volume 1584 of Lecture Notes in Computer Science, pages 126-141. Springer, 1998. Google Scholar
  26. Leonid Libkin. Elements of Finite Model Theory. Springer Verlag, 2004. Google Scholar
  27. Daniel Lokshtanov. Personal communication, 2015. Google Scholar
  28. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential time hypothesis. Bulletin of the European Association for Theoretical Computer Science, 105:41-72, 2011. Google Scholar
  29. Dániel Marx. Can you beat treewidth? Theory of Computing, 6:85-112, 2010. Google Scholar
  30. Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. J. of Computer and System Sciences, 43(3):425-440, 1991. Google Scholar
  31. Elena Pezzoli. Computational complexity of ehrenfeucht-fraïssé games on finite structures. In Computer Science Logic, 12th International Workshop, CSL '98, Annual Conference of the EACSL, Brno, Czech Republic, August 24-28, 1998, Proceedings, pages 159-170, 1998. Google Scholar
  32. Sheung-Hung Poon, William Chung-Kung Yen, and Chin-Ting Ung. Domatic partition on several classes of graphs. In Combinatorial Optimization and Applications - 6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012. Proceedings, pages 245-256, 2012. 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