Parameterized complexity of \(k\)-Chinese postman problem

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

Author name not available (Why is that?)

Publication date: 13 January 2014

Published in: (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

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

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)