Document Open Access Logo

K4-free Graphs as a Free Algebra

Authors Enric Cosme Llópez, Damien Pous

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.76.pdf
  • Filesize: 0.48 MB
  • 14 pages

Document Identifiers

Author Details

Enric Cosme Llópez
Damien Pous

Cite As Get BibTex

Enric Cosme Llópez and Damien Pous. K4-free Graphs as a Free Algebra. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 76:1-76:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.76

Abstract

Graphs of treewidth at most two are the ones excluding the clique with four vertices as a minor. Equivalently, they are the graphs whose biconnected components are series-parallel.
We turn those graphs into a free algebra, answering positively a question by Courcelle and Engelfriet, in the case of treewidth two.
First we propose a syntax for denoting them: in addition to series and parallel compositions, it suffices to consider the neutral elements of those operations and a unary transpose operation. Then we give a finite equational presentation and we prove it complete: two terms from the syntax are congruent if and only if they denote the same graph.

Subject Classification

Keywords
  • Universal Algebra
  • Graph theory
  • Axiomatisation
  • Tree decompositions
  • Graph minors

Metrics

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

References

  1. H. Andréka and D. A. Bredikhin. The equational theory of union-free algebras of relations. Algebra Universalis, 33(4):516-532, 1995. URL: http://dx.doi.org/10.1007/BF01225472.
  2. S. Arnborg, B. Courcelle, A. Proskurowski, and D. Seese. An algebraic theory of graph reduction. Journal of the ACM, 40(5):1134-1164, 1993. URL: http://dx.doi.org/10.1145/174147.169807.
  3. Michel Bauderon and Bruno Courcelle. Graph expressions and graph rewritings. Mathematical Systems Theory, 20(2-3):83-127, 1987. URL: http://dx.doi.org/10.1007/BF01692060.
  4. Ulrich Berger and Helmut Schwichtenberg. An inverse of the evaluation functional for typed lambda-calculus. In LICS, pages 203-211. IEEE, 1991. URL: http://dx.doi.org/10.1109/LICS.1991.151645.
  5. H.L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209(1):1-45, 1998. URL: http://dx.doi.org/10.1016/S0304-3975(97)00228-4.
  6. Mikołaj Bojańczyk and Michal Pilipczuk. Definability equals recognizability for graphs of bounded treewidth. In LICS, pages 407-416. ACM, 2016. URL: http://dx.doi.org/10.1145/2933575.2934508.
  7. Chandra Chekuri and Anand Rajaraman. Conjunctive query containment revisited. Theoretical Computer Science, 239(2):211-229, 2000. URL: http://dx.doi.org/10.1016/S0304-3975(99)00220-0.
  8. Enric Cosme-Llópez and Damien Pous. K₄-free graphs as a free algebra, 2017. Full version of this extended abstract, with all proofs, available at URL: https://hal.archives-ouvertes.fr/hal-01515752/.
  9. B. Courcelle. The monadic second-order logic of graphs. I: Recognizable sets of finite graphs. Information and Computation, 85(1):12-75, 1990. URL: http://dx.doi.org/10.1016/0890-5401(90)90043-H.
  10. B. Courcelle. The monadic second-order logic of graphs V: on closing the gap between definability and recognizability. Theoretical Computer Science, 80(2):153-202, 1991. URL: http://dx.doi.org/10.1016/0304-3975(91)90387-H.
  11. B. Courcelle. Recognizable sets of graphs: equivalent definitions and closure properties. Mathematical Structures in Computer Science, 4(1):1-32, 1994. Google Scholar
  12. B. Courcelle. The monadic second-order logic of graphs XI: Hierarchical decompositions of connected graphs. Theoretical Computer Science, 224(1):35-58, 1999. URL: http://dx.doi.org/10.1016/S0304-3975(98)00306-5.
  13. B. Courcelle and J. 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. Google Scholar
  14. B. Courcelle and J. Lagergren. Equivalent definitions of recognizability for sets of graphs of bounded tree-width. Mathematical Structures in Computer Science, 6(2):141-165, 1996. URL: http://dx.doi.org/10.1017/S096012950000092X.
  15. Bruno Courcelle. Graph grammars, monadic second-order logic and the theory of graph minors. In Graph Structure Theory, volume 147 of Contemporary Mathematics, pages 565-590. American Mathematical Society, 1993. Proceedings of a Joint Summer Research Conference on Graph Minors held June 22 to July 5, 1991, at the University of Washington, Seattle. URL: http://dx.doi.org/10.1090/conm/147.
  16. R. Diestel. Graph Theory. Graduate Texts in Mathematics. Springer, 2005. Google Scholar
  17. Daniel J. Dougherty and Claudio Gutiérrez. Normal forms for binary relations. Theoretical Computer Science, 360(1-3):228-246, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2006.03.023.
  18. R.J Duffin. Topology of series-parallel networks. Journal of Mathematical Analysis and Applications, 10(2):303-318, 1965. URL: http://dx.doi.org/10.1016/0022-247X(65)90125-3.
  19. Eugene C. Freuder. Complexity of k-tree structured constraint satisfaction problems. In NCAI, pages 4-9. AAAI Press / The MIT Press, 1990. URL: http://www.aaai.org/Library/AAAI/1990/aaai90-001.php.
  20. P.J. Freyd and A. Scedrov. Categories, Allegories. North Holland. Elsevier, 1990. URL: https://books.google.fr/books?id=fCSJRegkKdoC.
  21. Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM, 54(1):1:1-1:24, 2007. URL: http://dx.doi.org/10.1145/1206035.1206036.
  22. D. Kozen. Kleene algebra with tests. Transactions on Programming Languages and Systems, 19(3):427-443, May 1997. URL: http://dx.doi.org/10.1145/256167.256195.
  23. J. Mezei and J.B. Wright. Algebraic automata and context-free sets. Information and Control, 11(1–2):3-29, 1967. URL: http://dx.doi.org/10.1016/S0019-9958(67)90353-1.
  24. R. Milner. Communication and Concurrency. Prentice Hall, 1989. Google Scholar
  25. David Park. Concurrency and automata on infinite sequences. In Theoretical Computer Science, pages 167-183, 1981. URL: http://dl.acm.org/citation.cfm?id=647210.720030.
  26. Neil Robertson and P.D. Seymour. Graph minors. XX. Wagner’s conjecture. Journal of Combinatorial Theory, Series B, 92(2):325-357, 2004. URL: http://dx.doi.org/10.1016/j.jctb.2004.08.001.
  27. W. Tutte. Graph Theory. Addison-Wesley, Reading, MA, 1984. 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