On spanning galaxies in digraphs

详细信息	查看全文 | 推荐本文 |

• 作者：Daniel Gonç ; alves^a ; ^{Daniel.Goncalves@lirmm.fr} ; Fré ; dé ; ric Havet^b ; ^{Frederic.Havet@sophia.inria.fr} ; ^{fhavet@sophia.inria.fr} ; Alexandre Pinlou^a ; ^{Alexandre.Pinlou@lirmm.fr} ; Sté ; phan Thomassé ; ^a ; ^{thomasse@lirmm.fr}
• 关键词：Spanning galaxy ; Even strong subdigraph ; Directed star arboricity ; Algorithms ; Fixed parameter tractable
• 刊名：Discrete Applied Mathematics
• 出版年：2012
• 期刊代码：46_0166218x
• 类别：cp
• 出版时间：April, 2012
• 卷：160
• 期：6
• 页码：744-754
• 文件大小：267 K

摘要

In a directed graph, a star is an arborescence with at least one arc, in which the root dominates all the other vertices. A galaxy is a vertex-disjoint union of stars. In this paper, we consider the Spanning Galaxy problem of deciding whether a digraph has a spanning galaxy or not. We show that although this problem is NP-complete (even when restricted to acyclic digraphs), it becomes polynomial-time solvable when restricted to strong digraphs. In fact, we prove that restricted to this class, the Spanning Galaxy problem聽is equivalent to the problem of deciding whether a strong digraph has a strong subdigraph with an even number of vertices. We then show a polynomial-time algorithm to solve this problem. We also consider some parameterized version of the Spanning Galaxy problem. Finally, we improve some results concerning the notion of directed star arboricity of a digraph , which is the minimum number of galaxies needed to cover all the arcs of . We show in particular that for every digraph and that for every acyclic digraph .