Document Open Access Logo

Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs

Author Berit Grußien

PDF
Thumbnail PDF

File

LIPIcs.CSL.2017.26.pdf
  • Filesize: 0.63 MB
  • 19 pages

Document Identifiers

Author Details

Berit Grußien

Cite As Get BibTex

Berit Grußien. Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 26:1-26:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CSL.2017.26

Abstract

We show that the class of chordal claw-free graphs admits LREC=-definable canonization. LREC= is a logic that extends first-order logic with counting by an operator that allows it to formalize a limited form of recursion. This operator can be evaluated in logarithmic space. It follows that there exists a logarithmic-space canonization algorithm for the class of chordal claw-free graphs, and that LREC= captures logarithmic space on this graph class. Since LREC= is contained in fixed-point logic with counting, we also obtain that fixed-point logic with counting captures polynomial time on the class of chordal claw-free graphs.

Subject Classification

Keywords
  • Descriptive complexity
  • logarithmic space
  • polynomial time
  • chordal claw-free graphs

Metrics

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

References

  1. J. R. S. Blair and B. Peyton. An introduction to chordal graphs and clique trees. In A. George, J. R. Gilbert, and J. W. H. Liu, editors, Graph Theory and Sparse Matrix Computation, pages 1-29. Springer New York, 1993. Google Scholar
  2. P. Buneman. A characterisation of rigid circuit graphs. Discrete Math., 9:205-212, 1974. Google Scholar
  3. J. Cai, M. Fürer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12:389-410, 1992. Google Scholar
  4. H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer-Verlag, 1999. Google Scholar
  5. K. Etessami and N. Immerman. Tree canonization and transitive closure. Information and Computation, 157(1-2):2-24, 2000. Google Scholar
  6. R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In R.M. Karp, editor, Complexity of Computation, SIAM-AMS Proceedings 7, pages 43-73, 1974. Google Scholar
  7. F. Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B, 16(1):47-56, 1974. Google Scholar
  8. M. Grohe. Fixed-point logics on planar graphs. In LICS, pages 6-15, 1998. Google Scholar
  9. M. Grohe. Definable tree decompositions. In LICS, pages 406-417, 2008. Google Scholar
  10. M. Grohe. Fixed-point definability and polynomial time on chordal graphs and line graphs. In A. Blass, N. Dershowitz, and W. Reisig, editors, Fields of Logic and Computation, Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday, pages 328-353, 2010. Google Scholar
  11. M. Grohe. Fixed-point definability and polynomial time on graphs with excluded minors. In LICS, 2010. Google Scholar
  12. M. Grohe. Descriptive complexity, canonisation, and definable graph structure theory, 2013. [Online; accessed 2017-03-31]. URL: http://lii.rwth-aachen.de/images/Mitarbeiter/pub/grohe/cap/all.pdf.
  13. M. Grohe, B. Grußien, A. Hernich, and B. Laubner. L-recursion and a new logic for logarithmic space. In CSL, pages 277-291, 2011. Google Scholar
  14. M. Grohe, B. Grußien, A. Hernich, and B. Laubner. L-recursion and a new logic for logarithmic space. Logical Methods in Computer Science, 9(1), 2012. Google Scholar
  15. M. Grohe and J. Mariño. Definability and descriptive complexity on databases of bounded tree-width. In ICDT, pages 70-82, 1999. Google Scholar
  16. B. Grußien. Capturing Polynomial Time and Logarithmic Space using Modular Decompositions and Limited Recursion. PhD thesis, Humboldt-Universität zu Berlin, 2016. Google Scholar
  17. B. Grußien. Capturing polynomial time using modular decomposition. In LICS, 2017. Google Scholar
  18. N. Immerman. Relational queries computable in polynomial time. Information and Control, 68:86-104, 1986. Google Scholar
  19. N. Immerman. Languages that capture complexity classes. SIAM Journal on Computing, 16:760-778, 1987. Google Scholar
  20. B. Laubner. Capturing polynomial time on interval graphs. In LICS, pages 199-208, 2010. Google Scholar
  21. B. Laubner. The Structure of Graphs and New Logics for the Characterization of Polynomial Time. PhD thesis, Humboldt-Universität zu Berlin, 2011. Google Scholar
  22. S. Lindell. A logspace algorithm for tree canonization. In STOC, pages 400-404, 1992. Google Scholar
  23. R. Sedgewick. Algorithms in Java: Parts 1-4. Addison-Wesley, 3rd edition, 2002. Google Scholar
  24. M. Y. Vardi. The complexity of relational query languages. In STOC, pages 137-146, 1982. Google Scholar
  25. J. R. Walter. Representations of Rigid Cycle Graphs. PhD thesis, Wayne State University, 1972. 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 About DROPS Imprint Privacy Contact