Berit Grußien - 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 - https://doi.org/10.23638/LMCS-15(3:2)2019
Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free GraphsArticle

Authors: Berit Grußien

    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.


    Volume: Volume 15, Issue 3
    Published on: July 8, 2019
    Accepted on: June 4, 2019
    Submitted on: March 1, 2018
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Discrete Mathematics

    Consultation statistics

    This page has been seen 1673 times.
    This article's PDF has been downloaded 331 times.