Document Open Access Logo

Recovering Sparse Graphs

Authors Jakub Gajarský, Daniel Král'

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.29.pdf
  • Filesize: 462 kB
  • 15 pages

Document Identifiers

Author Details

Jakub Gajarský
  • Technical University Berlin, Berlin, Germany
Daniel Král'
  • Mathematics Institute, DIMAP and Department of Computer Science, University of Warwick, Coventry CV4 7AL, UK

Funding

  • Gajarský, Jakub: This author’s research was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (ERC Consolidator Grant DISTRUCT, grant agreement No 648527). This publication reflects only its authors' view; the European Research Council Executive Agency is not responsible for any use that may be made of the information it contains.
  • Král', Daniel: The work of this author was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (ERC Consolidator Grant LADIST, grant agreement No 648509). This publication reflects only its authors' view; the European Research Council Executive Agency is not responsible for any use that may be made of the information it contains.

Cite As Get BibTex

Jakub Gajarský and Daniel Král'. Recovering Sparse Graphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.29

Abstract

We construct a fixed parameter algorithm parameterized by d and k that takes as an input a graph G' obtained from a d-degenerate graph G by complementing on at most k arbitrary subsets of the vertex set of G and outputs a graph H such that G and H agree on all but f(d,k) vertices.
Our work is motivated by the first order model checking in graph classes that are first order interpretable in classes of sparse graphs. We derive as a corollary that if G is a graph class with bounded expansion, then the first order model checking is fixed parameter tractable in the class of all graphs that can obtained from a graph G in G by complementing on at most k arbitrary subsets of the vertex set of G; this implies an earlier result that the first order model checking is fixed parameter tractable in graph classes interpretable in classes of graphs with bounded maximum degree.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Logic
  • Theory of computation → Finite Model Theory
Keywords
  • model checking
  • degenerate graphs
  • interpretations
  • bounded expansion

Metrics

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

References

  1. Noga Alon and Shai Gutner. Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. In Computing and Combinatorics, 13th Annual International Conference, COCOON, Proceedings, volume 4598 of Lecture Notes in Computer Science, pages 394-405. Springer, 2007. URL: http://dx.doi.org/10.1007/978-3-540-73545-8.
  2. Bruno Courcelle. The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. URL: http://dx.doi.org/10.1016/0890-5401(90)90043-H.
  3. Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach, volume 138 of Encyclopedia of mathematics and its applications. Cambridge University Press, 2012. URL: http://www.cambridge.org/fr/knowledge/isbn/item5758776/?site_locale=fr_FR.
  4. 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: http://dx.doi.org/10.1007/s002249910009.
  5. Anuj Dawar, Martin Grohe, and Stephan Kreutzer. Locally excluding a minor. In 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), Proceedings, pages 270-279. IEEE Computer Society, 2007. URL: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=4276538.
  6. Anuj Dawar and Stephan Kreutzer. Parameterized complexity of first-order logic. Electronic Colloquium on Computational Complexity (ECCC), 16:131, 2009. URL: http://eccc.hpi-web.de/report/2009/131.
  7. Zdenek Dvořák, Daniel Král', and Robin Thomas. Deciding first-order properties for sparse graphs. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS, Proceedings, pages 133-142. IEEE Computer Society, 2010. URL: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=5669376.
  8. Zdenek Dvořák, Daniel Král', and Robin Thomas. Testing first-order properties for subclasses of sparse graphs. J. ACM, 60(5):36:1-36:24, 2013. URL: http://dx.doi.org/10.1145/2499483.
  9. Kord Eickmeyer and Ken-ichi Kawarabayashi. FO model checking on map graphs. In Fundamentals of Computation Theory - 21st International Symposium, FCT, Proceedings, volume 10472 of Lecture Notes in Computer Science, pages 204-216. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-662-55751-8.
  10. Markus Frick and Martin Grohe. Deciding first-order properties of locally tree-decomposable structures. J. ACM, 48(6):1184-1206, 2001. URL: http://dx.doi.org/10.1145/504794.504798.
  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 Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS, pages 176-184. ACM, 2016. URL: http://dx.doi.org/10.1145/2933575.
  12. Jakub Gajarský, Stephan Kreutzer, Jaroslav Nesetřil, Patrice Ossona de Mendez, Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. First-order interpretations of bounded expansion classes. To appear in proceedings of Automata, Languages, and Programming - 40th International Colloquium, ICALP, 2018. Google Scholar
  13. Robert Ganian, Petr Hliněný, Daniel Král', Jan Obdržálek, Jarett Schwartz, and Jakub Teska. FO model checking of interval graphs. Log. Methods Comp. Science, 11(4), 2015. URL: http://dx.doi.org/10.2168/LMCS-11(4:11)2015.
  14. Martin Grohe and Stephan Kreutzer. Methods for algorithmic meta theorems. In Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics: AMS-ASL Joint Special Session, volume 558, pages 181-206, 2011. Google Scholar
  15. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. In Symposium on Theory of Computing, STOC, proceedings, pages 89-98. ACM, 2014. URL: http://dl.acm.org/citation.cfm?id=2591796.
  16. Petr Hliněný, Filip Pokrývka, and Bodhayan Roy. FO model checking of geometric graphs. In 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, proceedings, volume 89 of LIPIcs, pages 19:1-19:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://www.dagstuhl.de/dagpub/978-3-95977-051-4.
  17. Stephan Kreutzer. Algorithmic meta-theorems. Electronic Colloquium on Computational Complexity (ECCC), 16:147, 2009. URL: http://eccc.hpi-web.de/report/2009/147.
  18. Jaroslav Nešetřil and Patrice Ossona de Mendez. Linear time low tree-width partitions and algorithmic consequences. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC, pages 391-400. ACM, 2006. Google Scholar
  19. Jaroslav Nešetřil and Patrice Ossona de Mendez. Grad and classes with bounded expansion I. decompositions. Eur. J. Comb., 29(3):760-776, 2008. URL: http://dx.doi.org/10.1016/j.ejc.2006.07.013.
  20. Jaroslav Nešetřil and Patrice Ossona de Mendez. Grad and classes with bounded expansion II. algorithmic aspects. Eur. J. Comb., 29(3):777-791, 2008. URL: http://dx.doi.org/10.1016/j.ejc.2006.07.014.
  21. Jaroslav Nešetřil and Patrice Ossona de Mendez. Grad and classes with bounded expansion III. restricted graph homomorphism dualities. Eur. J. Comb., 29(4):1012-1024, 2008. URL: http://dx.doi.org/10.1016/j.ejc.2007.11.019.
  22. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-27875-4.
  23. Sang-il Oum and Paul D. Seymour. Approximating clique-width and branch-width. J. Comb. Theory, Ser. B, 96(4):514-528, 2006. URL: http://dx.doi.org/10.1016/j.jctb.2005.10.006.
  24. Detlef Seese. Linear time computable problems and logical descriptions. Electr. Notes Theor. Comput. Sci., 2:246-259, 1995. URL: http://dx.doi.org/10.1016/S1571-0661(05)80203-8.
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