License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.404
URN: urn:nbn:de:0030-drops-30309
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3030/
Go to the corresponding LIPIcs Volume Portal

Ganian, Robert ; Hlineny, Petr ; Obdrzalek, Jan

Clique-width: When Hard Does Not Mean Impossible

pdf-format:
38.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{ganian_et_al:LIPIcs:2011:3030,
  author =	{Robert Ganian and Petr Hlineny and Jan Obdrzalek},
  title =	{{Clique-width: When Hard Does Not Mean Impossible}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
  pages =	{404--415},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Thomas Schwentick and Christoph D{\"u}rr},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3030},
  URN =		{urn:nbn:de:0030-drops-30309},
  doi =		{10.4230/LIPIcs.STACS.2011.404},
  annote =	{Keywords: clique-width, bi-rank-width, minimum leaf out-branching, minimum leaf spanning tree, edge-disjoint paths}
}

Keywords: clique-width, bi-rank-width, minimum leaf out-branching, minimum leaf spanning tree, edge-disjoint paths
Collection: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Issue Date: 2011
Date of publication: 11.03.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI