Capturing Polynomial Time on Interval Graphs

Details Capturing Polynomial Time on Interval Graphs Capturing Polynomial Time on Interval Graphs

2009-11-19

arxiv.org/abs/0911.3799v3

Laubner, B.: Capturing polynomial time on interval graphs. In LICS 2010, pp. 199-208. 2010

Computer Science

Logic in Computer Science

17 pages

Scientific paper

We prove a characterization of all polynomial-time computable queries on the class of interval graphs by sentences of fixed-point logic with counting. More precisely, it is shown that on the class of unordered interval graphs, any query is polynomial-time computable if and only if it is definable in fixed-point logic with counting. This result is one of the first establishing the capturing of polynomial time on a graph class which is defined by forbidden induced subgraphs. For this, we define a canonical form of interval graphs using a type of modular decomposition, which is different from the method of tree decomposition that is used in most known capturing results for other graph classes, specifically those defined by forbidden minors. The method might also be of independent interest for its conceptual simplicity. Furthermore, it is shown that fixed-point logic with counting is not expressive enough to capture polynomial time on the classes of chordal graphs or incomparability graphs.

Affiliated with

Also associated with

No associations

Rating

Capturing Polynomial Time on Interval Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Capturing Polynomial Time on Interval Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Capturing Polynomial Time on Interval Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-453430