Grußien, Berit - Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs

lmcs:4333 - Logical Methods in Computer Science, July 8, 2019, Volume 15, Issue 3
Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs

Authors: Grußien, Berit

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, and therefore a logarithmic-space isomorphism test, for the class of chordal claw-free graphs. As a further consequence, 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.


Source : oai:arXiv.org:1802.10331
Volume: Volume 15, Issue 3
Published on: July 8, 2019
Submitted on: March 1, 2018
Keywords: Computer Science - Logic in Computer Science,Computer Science - Discrete Mathematics


Share