In the Directed k-Chinese Postman Problem (k-DCPP), we are given a connected weighted digraph G and asked to find k non-empty closed directed walks covering all arcs of G such that the total weight of the walks is minimum. Gutin, Muciaccia and Yeo (Theor. Comput. Sci. 513, 124-128 (2013)) asked for the parameterized complexity of k-DCPP when k is the parameter. We prove that the k-DCPP is fixed-parameter tractable. We also consider a related problem of finding k arc-disjoint directed cycles in an Euler digraph, parameterized by k. Slivkins (ESA 2003) showed that this problem is W-hard for general digraphs. Generalizing another result by Slivkins, we prove that the problem is fixed-parameter tractable for Euler digraphs. The corresponding problem on vertex-disjoint cycles in Euler digraphs remains W-hard even for Euler digraphs.
展开▼
