10.4230/LIPICS.STACS.2011.404
Ganian, Robert
Robert
Ganian
Hlineny, Petr
Petr
Hlineny
Obdrzalek, Jan
Jan
Obdrzalek
Clique-width: When Hard Does Not Mean Impossible
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2011
Article
clique-width
bi-rank-width
minimum leaf out-branching
minimum leaf spanning tree
edge-disjoint paths
Schwentick, Thomas
Thomas
Schwentick
Dürr, Christoph
Christoph
Dürr
2011
2011-03-11
2011-03-11
2011-03-11
en
urn:nbn:de:0030-drops-30309
10.4230/LIPIcs.STACS.2011
978-3-939897-25-5
1868-8969
10.4230/LIPIcs.STACS.2011
LIPIcs, Volume 9, STACS 2011
28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
2013
9
34
404
415
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Schwentick, Thomas
Thomas
Schwentick
Dürr, Christoph
Christoph
Dürr
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2011
9
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
756320 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
In recent years, the parameterized complexity approach has lead to the introduction of many new algorithms and frameworks on graphs and digraphs of bounded clique-width and, equivalently, rank-width. However, despite intensive work on the subject, there still exist well-established hard problems where neither a parameterized algorithm nor a theoretical obstacle to its existence are known. Our article is interested mainly in the digraph case, targeting the well-known Minimum Leaf Out-Branching (cf. also Minimum Leaf Spanning Tree) and Edge Disjoint Paths problems on digraphs of bounded clique-width with non-standard new approaches.
The first part of the article deals with the Minimum Leaf Out-Branching problem and introduces a novel XP-time algorithm wrt. clique-width. We remark that this problem is known to be W[2]-hard, and that our algorithm does not resemble any of the previously published attempts solving special cases of it such as the Hamiltonian Path. The second part then looks at the Edge Disjoint Paths problem (both on graphs and digraphs) from a different perspective -- rather surprisingly showing that this problem has a definition in the MSO_1 logic of graphs. The linear-time FPT algorithm wrt. clique-width then follows as a direct consequence.
LIPIcs, Vol. 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), pages 404-415