Rural postman parameterized by the number of components of required edges

详细信息    查看全文

• 作者：Gregory Gutin^a ; ^{gutin@cs.rhul.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Magnus Wahlströ ; m^a ; ^{Magnus.Wahlstrom@rhul.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Anders Yeo^b ; ^c ; ^{andersyeo@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Fixed-parameter tractable ; Rural postman problem ; Randomized algorithms
• 刊名：Journal of Computer and System Sciences
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：83
• 期：1
• 页码：121-131
• 全文大小：430 K

文摘

In the Directed Rural Postman Problem (DRPP), given a strongly connected directed multigraph D=(V,A)$D=(V,A)$ with nonnegative integral weights on the arcs, a subset R of required arcs and a nonnegative integer ℓ, decide whether D has a closed directed walk containing every arc of R and of weight at most ℓ. Let k be the number of weakly connected components in the subgraph of D induced by R. Sorge et al. [30] asked whether the DRPP is fixed-parameter tractable (FPT) when parameterized by k  , i.e., whether there is an algorithm of running time O^⁎(f(k))$O^{⁎}(f(k))$ where f is a function of k   only and the O^⁎$O^{⁎}$ notation suppresses polynomial factors. Using an algebraic approach, we prove that DRPP has a randomized algorithm of running time O^⁎(2^k)$O^{⁎}(2^k)$ when ℓ is bounded by a polynomial in the number of vertices in D. The same result holds for the undirected version of DRPP.