Alliances in graphs of bounded clique-width

作者：Kiyomi Masashi; Otachi Yota^*

来源：Discrete Applied Mathematics, 2017, 223: 91-97.

DOI：10.1016/j.dam.2017.02.004

• Graph algorithm
• Alliance
• Clique-width
• Vertex cover

An alliance in a graph is a set of vertices that is either safe under attacks from the neighborhood (defensive), capable of attacking its neighbors (offensive), or simultaneously defensive and offensive (powerful). An alliance is global if all nonmembers are adjacent to some members of the alliance. The concept of alliances was introduced by Kristiansen et al. (2004). After that many results concerning the complexity for finding a minimum alliance were shown. It was shown that the problem of finding a minimum alliance of any variant is NP-hard in general. For some variants, it was shown that the problem becomes polynomial time solvable when restricted to trees or series-parallel graphs.
In this paper, we show that the problems for all variants are efficiently solvable for much larger graph classes. We present a polynomial-time algorithm for graphs of bounded clique-width. We also show that the problem is fixed-parameter tractable when parameterized by the vertex cover number.

• 出版日期2017-5-31