Rural Postman Parameterized by the Number of Components of Required Edges. / Gutin, Gregory; Wahlström, Magnus; Yeo, Anders.

In: Journal of Computer and System Sciences, Vol. 83, No. 1, 01.02.2017, p. 121-131.

Research output: Contribution to journalArticle

Published

Abstract

In the Directed Rural Postman Problem (DRPP), given a strongly connected directed multigraph 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)) where f is a function of k only and the O⁎ notation suppresses polynomial factors. Using an algebraic approach, we prove that DRPP has a randomized algorithm of running time O⁎(2k) when ℓ is bounded by a polynomial in the number of vertices in D. The same result holds for the undirected version of DRPP. © 2016 Elsevier Inc.
Original languageEnglish
Pages (from-to)121-131
Number of pages11
JournalJournal of Computer and System Sciences
Volume83
Issue number1
DOIs
Publication statusPublished - 1 Feb 2017
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 22854318