Fixed-parameter tractability and characterizations of small special treewidth

H.L. Bodlaender, S. Kratsch, V.J.C. Kreuzen

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationGraph
Subtitle of host publicationTheoretic Concepts in Computer Science - 39th International Workshop, WG 2013, Revised Papers
EditorsAndreas Brandstädt, Klaus Jansen, Rüdiger Reischuk
Place of PublicationBerlin
PublisherSpringer
Chapter9
Pages88-99
Number of pages12
ISBN (Electronic)978-3-642-45043-3
ISBN (Print)978-3-642-45042-6
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013 - Lubeck, Germany
Duration: 19 Jun 201321 Jun 2013

Publication series

NameLecture Notes in Computer Science
Volume8165
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013
CountryGermany
CityLubeck
Period19/06/1321/06/13

Fingerprint

Dive into the research topics of 'Fixed-parameter tractability and characterizations of small special treewidth'. Together they form a unique fingerprint.

Cite this