Structural Parameterizations of the Mixed Chinese Postman Problem

DOI10.1007/978-3-662-48350-3_56zbMATH Open1467.68074arXiv1410.5191OpenAlexW1901935697MaRDI QIDQ3452829FDOQ3452829

Author name not available (Why is that?)

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Abstract: In the Mixed Chinese Postman Problem (MCPP), given a weighted mixed graph $G$ ($G$ may have both edges and arcs), our aim is to find a minimum weight closed walk traversing each edge and arc at least once. The MCPP parameterized by the number of edges in $G$ or the number of arcs in $G$ is fixed-parameter tractable as proved by van Bevern {em et al.} (in press) and Gutin, Jones and Sheng (ESA 2014), respectively. In this paper, we consider the unweighted version of MCPP. Solving an open question of van Bevern {em et al.} (in press), we show that somewhat unexpectedly MCPP parameterized by the (undirected) treewidth of $G$ is W[1]-hard. In fact, we prove that even the MCPP parameterized by the pathwidth of $G$ is W[1]-hard. On the positive side, we show that the unweighted version of MCPP parameterized by tree-depth is fixed-parameter tractable. We are unaware of any natural graph parameters between pathwidth and tree-depth and so our results provide a dichotomy of the complexity of MCPP. Furthermore, we believe that MCPP is the first problem known to be W[1]-hard with respect to treewidth but FPT with respect to tree-depth.

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Fundamentals of parameterized complexity
• Matching, Euler tours and the Chinese postman
• On the parameterized complexity of multiple-interval graph problems
• On the complexity of edge traversing
• Networks and vehicle routing for municipal waste collection
• Arc Routing Problems, Part I: The Chinese Postman Problem
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
• Parameterized Complexity of the k-Arc Chinese Postman Problem
• On the complexity of some colorful problems parameterized by treewidth
• Capacitated Domination and Covering: A Parameterized Perspective
• Parameterized complexity of generalized domination problems

Cited In (13)

• Completing Partial Schedules for Open Shop with Unit Processing Times and Routing
• The \(k\)-centrum Chinese postman delivery problem and a related cost allocation game
• Title not available (Why is that?)
• The mixed Chinese postman problem parameterized by pathwidth and treedepth
• Width, depth, and space: tradeoffs between branching and dynamic programming
• Parameterized Complexity of the k-Arc Chinese Postman Problem
• Safe sets in graphs: graph classes and structural parameters
• The complexity landscape of decompositional parameters for ILP
• Parameterized complexity of length-bounded cuts and multicuts
• Safe Sets in Graphs: Graph Classes and Structural Parameters
• Parameterized complexity of the \(k\)-arc Chinese postman problem
• Uncertain multi-objective Chinese postman problem
• Chinese postman problem on edge-colored multigraphs

This page was built for publication: Structural Parameterizations of the Mixed Chinese Postman Problem

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