|
Published Articles >> Table of Contents >> Abstract
22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007)
pp. 270-279
Locally Excluding a Minor
Anuj Dawar, University of Cambridge, UK
Martin Grohe, Humboldt Universitat zu Berlin, Germany
Stephan Kreutzer, Universitat zu Berlin, Germany
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2007.31
Send link to a friend
| Abstract |
|
We introduce the concept of locally excluded minors.
Graph classes locally excluding a minor are a common generalisation
of the concept of excluded minor classes and of
graph classes with bounded local tree-width.
We show that first-order model-checking is fixed-parameter
tractable on any class of graphs locally excluding
a minor. This strictly generalises analogous results by
Flum and Grohe on excluded minor classes and Frick and
Grohe on classes with bounded local tree-width.
As an important consequence of the proof we obtain
fixed-parameter algorithms for problems such as dominating
or independent set on graph classes excluding a minor,
where now the parameter is the size of the dominating set
and the excluded minor.
We also study graph classes with excluded minors, where
the minor may grow slowly with the size of the graphs
and show that again, first-order model-checking is fixed-parameter
tractable on any such class of graphs.
|
 Additional Information
|
Citation:
Anuj Dawar, Martin Grohe, Stephan Kreutzer,
"Locally Excluding a Minor,"
lics,
pp. 270-279,
22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007),
2007
|
|
