Parameterized complexity of k-Chinese postman problem

DOI10.1016/J.TCS.2013.10.012MaRDI QIDQ391983zbMATH OpenOpenAlexFDO

Authors G. Gutin, Gabriele Muciaccia, A. Yeo

Publication date 13 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.0482

zbMATH Keywords

Chinese postman problemfixed-parameter tractabilitypolynomial kernels

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45)

Abstract: We consider the following problem called the $k$-Chinese Postman Problem ($k$-CPP): given a connected edge-weighted graph $G$ and integers $p$ and $k$, decide whether there are at least $k$ closed walks such that every edge of $G$ is contained in at least one of them and the total weight of the edges in the walks is at most $p$? The problem $k$-CPP is NP-complete, and van Bevern et al. (to appear) and Sorge (2013) asked whether the $k$-CPP is fixed-parameter tractable when parameterized by $k$. We prove that the $k$-CPP is indeed fixed-parameter tractable. In fact, we prove a stronger result: the problem admits a kernel with $O(k^{2}logk)$ vertices. We prove that the directed version of $k$-CPP is NP-complete and ask whether the directed version is fixed-parameter tractable when parameterized by $k$.

Recommendations

• Parameterized Complexity of the k-Arc Chinese Postman Problem
• Parameterized directed \(k\)-Chinese postman problem and \(k\) arc-disjoint cycles problem on Euler digraphs
• Parameterized complexity of the k-arc Chinese postman problem
• Solvable cases of the \(k\)-person Chinese postman problem
• Chinese postman problem on edge-colored multigraphs

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A new view on rural postman based on Eulerian extension and matching
• Digraphs
• Efficient algorithms for Eulerian extension and rural Postman
• Finding a Minimum Circuit in a Graph
• From few components to an Eulerian graph by adding ARCS
• Kernel bounds for disjoint cycles and disjoint paths
• Kernels: Annotated, Proper and Induced
• On the Complexity of Finding a Minimum Cycle Cover of a Graph
• Parametrized complexity theory.
• Solvable cases of the \(k\)-person Chinese postman problem
• The Moore bound for irregular graphs
• The NP-Completeness of Some Edge-Partition Problems
• The complexity of arc routing problems

Cited in

(11)

• Solvable cases of the \(k\)-person Chinese postman problem
• The mixed Chinese postman problem parameterized by pathwidth and treedepth
• Improved approximation algorithms for some min-max postmen cover problems with applications to the min-max subtree cover
• Approximation algorithms for some min-max postmen cover problems
• Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
• Parameterized complexity of the \(k\)-arc Chinese postman problem
• Parameterized directed \(k\)-Chinese postman problem and \(k\) arc-disjoint cycles problem on Euler digraphs
• Structural parameterizations of the mixed Chinese postman problem
• Parameterized Complexity of the k-Arc Chinese Postman Problem
• Completing partial schedules for open shop with unit processing times and routing
• Approximation algorithms for some minimum postmen cover problems

This page was built for publication: Parameterized complexity of \(k\)-Chinese postman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q391983)