Details

Autor(en) / Beteiligte

• Gurski, Frank
• Wanke, Egon
• Yilmaz, Eda

Titel

Directed NLC-width

Ist Teil von

• Theoretical computer science, 2016-02, Vol.616, p.1-17

Ort / Verlag

Elsevier B.V

Erscheinungsjahr

2016

Link zum Volltext

Quelle

EZB Electronic Journals Library

Beschreibungen/Notizen

• In this paper we generalize the concept of NLC-width introduced by Wanke in [39] to directed graphs. We show bounds of this new width parameter for directed graphs and relationships between directed NLC-width and directed clique-width which was introduced by Courcelle and Olariu in [8]. We also compare the measures with their undirected versions of the underlying undirected graphs. Our results imply that computing the directed NLC-width of a directed graph is NP-hard. Further we consider the directed width of digraph classes. We show that the set of directed co-graphs equals the set of graphs of directed NLC-width 1, while the set of directed co-graphs is characterized, by excluding two digraphs, as a proper subset of the set of all graphs of directed clique-width 2, which is a remarkable difference to the undirected versions of the graphs. From an algorithmic point of view directed NLC-width is a powerful digraph parameter, since for every digraph problem expressible in monadic second order logic with quantifications over vertices and vertex sets (MSO1-logic) there exists an fpt-algorithm with respect to the parameter directed NLC-width (of the input digraph). We show how the tree structure of directed NLC-width expressions can be used to solve a lot of further hard digraph problems efficiently on graphs of bounded width. We apply our method in order to give xp-algorithms for the problems Directed Hamiltonian Path, Directed Hamiltonian Cycle, Directed Cut, and Regular Subdigraph with respect to the parameter directed NLC-width. For most of these problems this is best possible, since they are known to be fixed-parameter intractable with respect to the parameter directed NLC-width.