TY - GEN

T1 - Fixed-parameter tractability and characterizations of small special treewidth

AU - Bodlaender, H.L.

AU - Kratsch, S.

AU - Kreuzen, V.J.C.

PY - 2013

Y1 - 2013

N2 - We investigate fixed-parameter aspects of the notion of special treewidth, which was recently introduced by Courcelle [8,9]. In a special tree decomposition, for each vertex v, the bags containing v form a rooted path in decomposition tree. We resolve an open problem by Courcelle, and show that an algorithm by Bodlaender and Kloks [7] can be modified to obtain for each fixed k, a linear time algorithm that decides if the special treewidth of a given graph is at most k, and if so, finds a corresponding special tree decomposition. This establishes that special treewidth is fixed-parameter tractable. We obtain characterizations for the class of graphs of special treewidth at most two. The first characterization consists of certain linear structures (termed mambas, or equivalently, biconnected partial two-paths) arranged in a specific tree-like fashion, building upon characterizations of biconnected graphs of treewidth two or of pathwidth two. We show that the class of graphs of special treewidth at most two is closed under taking of minors, and give explicitly the obstruction set for this class. For k ≥ 3, the class of graphs of special treewidth at most k is not closed under taking minors.

AB - We investigate fixed-parameter aspects of the notion of special treewidth, which was recently introduced by Courcelle [8,9]. In a special tree decomposition, for each vertex v, the bags containing v form a rooted path in decomposition tree. We resolve an open problem by Courcelle, and show that an algorithm by Bodlaender and Kloks [7] can be modified to obtain for each fixed k, a linear time algorithm that decides if the special treewidth of a given graph is at most k, and if so, finds a corresponding special tree decomposition. This establishes that special treewidth is fixed-parameter tractable. We obtain characterizations for the class of graphs of special treewidth at most two. The first characterization consists of certain linear structures (termed mambas, or equivalently, biconnected partial two-paths) arranged in a specific tree-like fashion, building upon characterizations of biconnected graphs of treewidth two or of pathwidth two. We show that the class of graphs of special treewidth at most two is closed under taking of minors, and give explicitly the obstruction set for this class. For k ≥ 3, the class of graphs of special treewidth at most k is not closed under taking minors.

UR - http://www.scopus.com/inward/record.url?scp=84893082967&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-45043-3_9

DO - 10.1007/978-3-642-45043-3_9

M3 - Conference contribution

AN - SCOPUS:84893082967

SN - 978-3-642-45042-6

T3 - Lecture Notes in Computer Science

SP - 88

EP - 99

BT - Graph

A2 - Brandstädt, Andreas

A2 - Jansen, Klaus

A2 - Reischuk, Rüdiger

PB - Springer

CY - Berlin

T2 - 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013

Y2 - 19 June 2013 through 21 June 2013

ER -