Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/LICS.2010.42 | logic in computer science |
Keywords | DocType | Volume |
capturing polynomial time,polynomialtime computable query,interval graph,polynomial-time computable,fixed-point logic,incomparability graph,unordered interval graph,graph class,modular decomposition,polynomial time,chordal graph,interval graphs,polynomials,lead,formal logic,canonical form,graph theory,fixed point,data structures,canonical forms,bipartite graph,construction industry,computational complexity | Conference | abs/0911.3799 |
ISSN | ISBN | Citations |
1043-6871 E-ISBN : 978-1-4244-7589-6 | 978-1-4244-7589-6 | 10 |
PageRank | References | Authors |
0.57 | 22 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bastian Laubner | 1 | 31 | 2.14 |