(Total) Vector domination for graphs with bounded branchwidth

详细信息    查看全文

• 作者：Toshimasa Ishii^a ; ^{ishii@econ.hokudai.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Hirotaka Ono^b ; ^{hirotaka@econ.kyushu-u.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Yushi Uno^c ; ^{uno@mi.s.osakafu-u.ac.jp" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Vector dominating set ; Total vector dominating set ; Multiple dominating set ; FPT ; Bounded branchwidth
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：10 July 2016
• 年：2016
• 卷：207
• 期：Complete
• 页码：80-89
• 全文大小：405 K

文摘

Given a graph ac6e4" title="Click to view the MathML source">G=(V,E)$G=(V,E)$ of order n$n$ and an n$n$-dimensional non-negative vector d=(d(1),d(2),…,d(n))$d=(d\left(1\right),d\left(2\right),\dots ,d\left(n\right))$, called demand vector, the vector domination (resp., total vector domination) is the problem of finding a minimum S⊆V$S\subseteq V$ such that every vertex v$v$ in V∖S$V\setminus S$ (resp., in ac41098a455" title="Click to view the MathML source">V$V$) has at least d(v)$d\left(v\right)$ neighbors in S$S$. The (total) vector domination is a generalization of many dominating set type problems, e.g., the dominating set problem, the k$k$-tuple dominating set problem (this k$k$ is different from the solution size), and so on, and its approximability and inapproximability have been studied under this general framework. In this paper, we show that a (total) vector domination of graphs with bounded branchwidth can be solved in polynomial time. This implies that the problem is polynomially solvable also for graphs with bounded treewidth. Consequently, the (total) vector domination problem for a planar graph is subexponential fixed-parameter tractable with respect to k$k$, where k$k$ is the size of solution.