Document Open Access Logo

Hard Problems on Random Graphs

Authors Jan Dreier , Henri Lotze , Peter Rossmanith

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.40.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Jan Dreier
  • Department of Computer Science, RWTH Aachen University, Germany
Henri Lotze
  • Department of Computer Science, RWTH Aachen University, Germany
Peter Rossmanith
  • Department of Computer Science, RWTH Aachen University, Germany

Funding

Grant DFG-927/15-1 from the German Science Foundation (DFG).

Acknowledgements

We thank the refeeres of ICALP for their very helpful comments that helped to improve the readability of the paper.

Cite AsGet BibTex

Jan Dreier, Henri Lotze, and Peter Rossmanith. Hard Problems on Random Graphs. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.40

Abstract

Many graph properties are expressible in first order logic. Whether a graph contains a clique or a dominating set of size k are two examples. For the solution size as its parameter the first one is W[1]-complete and the second one W[2]-complete meaning that both of them are hard problems in the worst-case. If we look at both problem from the aspect of average-case complexity, the picture changes. Clique can be solved in expected FPT time on uniformly distributed graphs of size n, while this is not clear for Dominating Set. We show that it is indeed unlikely that Dominating Set can be solved efficiently on random graphs: If yes, then every first-order expressible graph property can be solved in expected FPT time, too. Furthermore, this remains true when we consider random graphs with an arbitrary constant edge probability. We identify a very simple problem on random matrices that is equally hard to solve on average: Given a square boolean matrix, are there k rows whose logical AND is the zero vector? The related Even Set problem on the other hand turns out to be efficiently solvable on random instances, while it is known to be hard in the worst-case.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Complexity theory and logic
Keywords
  • random graphs
  • average-case complexity
  • first-order model checking

Metrics

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

References

  1. Shai Ben-David, Benny Chor, Oded Goldreich, and Michael Luby. On the theory of average case complexity. J. Comput. Syst. Sci., 44(2):193-219, 1992. URL: https://doi.org/10.1016/0022-0000(92)90019-F.
  2. Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, and Dániel Marx. Parameterized intractability of even set and shortest vector problem. CoRR, abs/1909.01986, 2019. URL: http://arxiv.org/abs/1909.01986.
  3. Ralph Christian Bottesch. On W[1]-hardness as evidence for intractability. In Igor Potapov, Paul G. Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, volume 117 of LIPIcs, pages 73:1-73:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.73.
  4. Amin Coja-Oghlan and Anusch Taraz. Colouring random graphs in expected polynomial time. In Helmut Alt and Michel Habib, editors, STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27 - March 1, 2003, Proceedings, volume 2607 of Lecture Notes in Computer Science, pages 487-498. Springer, 2003. URL: https://doi.org/10.1007/3-540-36494-3_43.
  5. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  6. Rodney G. Downey and Michael R. Fellows. Fixed-parameter intractability. In Proceedings of the Seventh Annual Structure in Complexity Theory Conference, Boston, Massachusetts, USA, June 22-25, 1992, pages 36-49. IEEE Computer Society, 1992. URL: https://doi.org/10.1109/SCT.1992.215379.
  7. Rodney G. Downey and Michael R. Fellows. Fixed parameter tractability and completeness. In Klaus Ambos-Spies, Steven Homer, and Uwe Schöning, editors, Complexity Theory: Current Research, Dagstuhl Workshop, February 2-8, 1992, pages 191-225. Cambridge University Press, 1992. Google Scholar
  8. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999. URL: https://doi.org/10.1007/978-1-4612-0515-9.
  9. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  10. Jan Dreier and Peter Rossmanith. Hardness of FO model-checking on random graphs. 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 11:1-11:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.IPEC.2019.11.
  11. Ronald Fagin. Probabilities on finite models. J. Symb. Log., 41(1):50-58, 1976. URL: https://doi.org/10.1017/S0022481200051756.
  12. Jörg Flum and Martin Grohe. Model-checking problems as a basis for parameterized intractability. Logical Methods in Computer Science, 1(1), 2005. URL: https://doi.org/10.2168/LMCS-1(1:2)2005.
  13. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. URL: https://doi.org/10.1007/3-540-29953-X.
  14. Nikolaos Fountoulakis, Tobias Friedrich, and Danny Hermelin. On the average-case complexity of parameterized clique. Theor. Comput. Sci., 576:18-29, 2015. URL: https://doi.org/10.1016/j.tcs.2015.01.042.
  15. Etienne Grandjean. Complexity of the first-order theory of almost all finite structures. Information and Control, 57(2/3):180-204, 1983. URL: https://doi.org/10.1016/S0019-9958(83)80043-6.
  16. Martin Grohe. Generalized model-checking problems for first-order logic. In Afonso Ferreira and Horst Reichel, editors, STACS 2001, 18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 15-17, 2001, Proceedings, volume 2010 of Lecture Notes in Computer Science, pages 12-26. Springer, 2001. URL: https://doi.org/10.1007/3-540-44693-1_2.
  17. Yuri Gurevich. Complete and incomplete randomized NP problems. In 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987, pages 111-117. IEEE Computer Society, 1987. URL: https://doi.org/10.1109/SFCS.1987.14.
  18. Valentin F. Kolchin. Random graphs, volume 53 of Encyclopedia of mathematics and its applications. Cambridge University Press, 1999. Google Scholar
  19. Leonid A. Levin. Problems, complete in "average" instance. In Richard A. DeMillo, editor, Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA, page 465. ACM, 1984. URL: https://doi.org/10.1145/800057.808713.
  20. Jerzy Loś. On the categoricity in power of elementary deductive systems and some related problems. Colloq. Math., 3:58-62, 1954. Google Scholar
  21. Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. Splitters and near-optimal derandomization. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 182-191. IEEE Computer Society, 1995. URL: https://doi.org/10.1109/SFCS.1995.492475.
  22. Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006. URL: https://doi.org/10.1093/ACPROF:OSO/9780198566076.001.0001.
  23. Robert L. Vaught. Applications to the Löwenheim-Skolem-Tarski theorem to problems of completeness and decidability. Indagationes Mathematicae, 16:467-472, 1954. Google Scholar
  24. John von Neumann. Various techniques used in connection with random digits. In Alston S. Householder, George E. Forsythe, and Hallett-Hunt Germond, editors, Monte Carlo method. Proceedings of a Symposium Held June 29, 30 and July 1, 1949 in Los Angeles, California, volume 12, pages 36-38, 1951. URL: https://dornsifecms.usc.edu/assets/sites/520/docs/VonNeumann-ams12p36-38.pdf.
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