Parameterized Domination in Circle Graphs
Parameterized Domination in Circle Graphs
复制标题
DOI：
10.1007/s00224-013-9478-8
复制
发表时间：
2012-05
影响因子：
0.5
通讯作者：
N. Bousquet;D. Gonçalves;G. B. Mertzios;C. Paul;Ignasi Sau;Stéphan Thomassé
中科院分区：
文献类型：
--
作者：
N. Bousquet;D. Gonçalves;G. B. Mertzios;C. Paul;Ignasi Sau;Stéphan Thomassé
圆图：一组弦在圆上的交点图。[离散苹果]数学。[j] .数学学报，42(1):51-63,1993]证明了圆形图的支配集、连通支配集和总支配集是完全的。据我们所知，我们对这些圆图问题的参数化复杂性一无所知。在此基础上，我们证明了圆图中的控制集、独立控制集、连通控制集、总控制集和无环控制集，这些结果都是由解的大小参数化的。虽然连通控制集和无环控制集在圆图中都很难，但在圆图中证明了连通无环控制集是多项式时间可解的。如果是自由的，判断一个圆图是否有一个支配集，当输入为T时，诱导一个图同构于tisnp -complete，当参数化为byt=|V(T)|时，诱导一个ftp -complete。我们证明了FPT算法在次指数时间内运行，即当=|V(G)|时。
Acircle graphis the intersection graph of a set of chords in a circle. Keil [Discrete Appl. Math., 42(1):51–63, 1993] proved thatDominating Set,Connected Dominating Set, andTotal Dominating SetareNP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction:Dominating Set,Independent Dominating Set,Connected Dominating Set,Total Dominating Set, andAcyclic Dominating SetareW[1]-hard in circle graphs, parameterized by the size of the solution.Whereas bothConnected Dominating SetandAcyclic Dominating SetareW[1]-hard in circle graphs, it turns out thatConnected Acyclic Dominating Setis polynomial-time solvable in circle graphs.IfTis agiventree, deciding whether a circle graphGhas a dominating set inducing a graph isomorphic toTisNP-complete whenTis in the input, andFPTwhen parameterized byt=|V(T)|. We prove that the FPT algorithm runs in subexponential time, namely, wheren=|V(G)|.