zbMATH — the first resource for mathematics

Fixed-parameter tractability and characterizations of small special treewidth. (English) Zbl 1400.05234
Brandstädt, Andreas (ed.) et al., Graph-theoretic concepts in computer science. 39th international workshop, WG 2013, Lübeck, Germany, June 19–21, 2013. Revised papers. Berlin: Springer (ISBN 978-3-642-45042-6/pbk). Lecture Notes in Computer Science 8165, 88-99 (2013).
Summary: We investigate fixed-parameter aspects of the notion of special treewidth, which was recently introduced by B. Courcelle [LIPICS – Leibniz International Proceedings in Informatics 8, 13–29 (2010; Zbl 1245.68133); Discrete Appl. Math. 160, No. 6, 866–887 (2012; Zbl 1236.05143)]. 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 H. L. Bodlaender and T. Kloks [J. Algorithms 21, No. 2, 358–402 (1996; Zbl 0861.68036)] 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\geq 3\), the class of graphs of special treewidth at most \(k\) is not closed under taking minors.
For the entire collection see [Zbl 1276.68009].

05C85 Graph algorithms (graph-theoretic aspects)
05C05 Trees
05C38 Paths and cycles
05C75 Structural characterization of families of graphs
05C83 Graph minors
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI