Subexponential fixed-parameter algorithms for partial vector domination

详细信息    查看全文

• 作者：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}
• 关键词：(Total) vector dominating set ; Partial dominating set ; Fixed-parameter tractability ; Branchwidth ; Apex-minor-free graphs
• 刊名：Discrete Optimization
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：22
• 期：part_PA
• 页码：111-121
• 全文大小：652 K

文摘

Given a graph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000049&_mathId=si1.gif&_user=111111111&_pii=S1572528616000049&_rdoc=1&_issn=15725286&md5=c025d9e29ce1ca8c483f48d66bc8da4d" title="Click to view the MathML source">G=(V,E)class="mathContainer hidden">class="mathCode">$G=(V,E)$ of order class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000049&_mathId=si2.gif&_user=111111111&_pii=S1572528616000049&_rdoc=1&_issn=15725286&md5=f699fc51bcd09cd7cbea117f8b1f1c02" title="Click to view the MathML source">nclass="mathContainer hidden">class="mathCode">$n$ and an class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000049&_mathId=si2.gif&_user=111111111&_pii=S1572528616000049&_rdoc=1&_issn=15725286&md5=f699fc51bcd09cd7cbea117f8b1f1c02" title="Click to view the MathML source">nclass="mathContainer hidden">class="mathCode">$n$-dimensional non-negative vector class="mathmlsrc">class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000049&_mathId=si4.gif&_user=111111111&_pii=S1572528616000049&_rdoc=1&_issn=15725286&md5=49e02f1c3a70c7a9f790f6e6cd56b869">class="imgLazyJSB inlineImage" height="13" width="153" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S1572528616000049-si4.gif">class="mathContainer hidden">class="mathCode">$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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000049&_mathId=si5.gif&_user=111111111&_pii=S1572528616000049&_rdoc=1&_issn=15725286&md5=03b7d1037b8905ad6a94bc47fb097356" title="Click to view the MathML source">S⊆Vclass="mathContainer hidden">class="mathCode">$S\subseteq V$ such that every vertex class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000049&_mathId=si6.gif&_user=111111111&_pii=S1572528616000049&_rdoc=1&_issn=15725286&md5=71b73bbe35a37ba3718927d4dbd5018e" title="Click to view the MathML source">vclass="mathContainer hidden">class="mathCode">$v$ in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000049&_mathId=si7.gif&_user=111111111&_pii=S1572528616000049&_rdoc=1&_issn=15725286&md5=553a6bcfba6439cc2627772fbdc60e80" title="Click to view the MathML source">V∖Sclass="mathContainer hidden">class="mathCode">$V\setminus S$ (resp., in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000049&_mathId=si8.gif&_user=111111111&_pii=S1572528616000049&_rdoc=1&_issn=15725286&md5=309bac7dac9c2e48cc9f1808ebf36009" title="Click to view the MathML source">Vclass="mathContainer hidden">class="mathCode">$V$) has at least class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000049&_mathId=si9.gif&_user=111111111&_pii=S1572528616000049&_rdoc=1&_issn=15725286&md5=22dc5eca66b727d5f56090397c2ed8c5" title="Click to view the MathML source">d(v)class="mathContainer hidden">class="mathCode">$d\left(v\right)$ neighbors in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000049&_mathId=si10.gif&_user=111111111&_pii=S1572528616000049&_rdoc=1&_issn=15725286&md5=b9e1ea11ab7a1feebfba1fe86f5eaaf0" title="Click to view the MathML source">Sclass="mathContainer hidden">class="mathCode">$S$. The (total) vector domination is a generalization of many dominating set type problems, e.g., the (total) dominating set problem, the (total) class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000049&_mathId=si11.gif&_user=111111111&_pii=S1572528616000049&_rdoc=1&_issn=15725286&md5=c0c0c09bc775a3bf64c195e72255c0e6" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$-dominating set problem (this class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000049&_mathId=si11.gif&_user=111111111&_pii=S1572528616000049&_rdoc=1&_issn=15725286&md5=c0c0c09bc775a3bf64c195e72255c0e6" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$ is different from the solution size), and so on, and subexponential fixed-parameter algorithms with respect to solution size for apex-minor-free graphs (so for planar graphs) are known. In this paper, we consider maximization versions of the problems; that is, for a given integer class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000049&_mathId=si11.gif&_user=111111111&_pii=S1572528616000049&_rdoc=1&_issn=15725286&md5=c0c0c09bc775a3bf64c195e72255c0e6" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$, the goal is to find an class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000049&_mathId=si5.gif&_user=111111111&_pii=S1572528616000049&_rdoc=1&_issn=15725286&md5=03b7d1037b8905ad6a94bc47fb097356" title="Click to view the MathML source">S⊆Vclass="mathContainer hidden">class="mathCode">$S\subseteq V$ with size class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000049&_mathId=si11.gif&_user=111111111&_pii=S1572528616000049&_rdoc=1&_issn=15725286&md5=c0c0c09bc775a3bf64c195e72255c0e6" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$ that maximizes the total sum of satisfied demands. For these problems, we design subexponential fixed-parameter algorithms with respect to class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1572528616000049&_mathId=si11.gif&_user=111111111&_pii=S1572528616000049&_rdoc=1&_issn=15725286&md5=c0c0c09bc775a3bf64c195e72255c0e6" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$ for apex-minor-free graphs.