文摘
In the Directed Rural Postman Problem (DRPP), given a strongly connected directed multigraph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300411&_mathId=si1.gif&_user=111111111&_pii=S0022000016300411&_rdoc=1&_issn=00220000&md5=879c8f76f8bc058c30330a579f0adac4" title="Click to view the MathML source">D=(V,A)class="mathContainer hidden">class="mathCode"> 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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300411&_mathId=si2.gif&_user=111111111&_pii=S0022000016300411&_rdoc=1&_issn=00220000&md5=19905b1d5ce3e0b1dc1664f24f717a55" title="Click to view the MathML source">O⁎(f(k))class="mathContainer hidden">class="mathCode"> where f is a function of k only and the class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300411&_mathId=si3.gif&_user=111111111&_pii=S0022000016300411&_rdoc=1&_issn=00220000&md5=735e4425728a167faa0c381a6e642856" title="Click to view the MathML source">O⁎class="mathContainer hidden">class="mathCode"> notation suppresses polynomial factors. Using an algebraic approach, we prove that DRPP has a randomized algorithm of running time class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300411&_mathId=si189.gif&_user=111111111&_pii=S0022000016300411&_rdoc=1&_issn=00220000&md5=8b910dc2b1235f01a5828a1001c36b71" title="Click to view the MathML source">O⁎(2k)class="mathContainer hidden">class="mathCode"> when ℓ is bounded by a polynomial in the number of vertices in D. The same result holds for the undirected version of DRPP.