Parameterized complexity of k-Chinese postman problem

DOI10.1016/J.TCS.2013.10.012zbMATH Open1408.68119arXiv1308.0482OpenAlexW1984595263MaRDI QIDQ391983FDOQ391983

Authors: G. Gutin, Gabriele Muciaccia, A. Yeo 

Publication date: 13 January 2014

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

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$.

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

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

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)

Cites Work

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

Cited In (11)

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

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)