Polynomial and FPT algorithms for Chinese Postman, Packing and Acyclicity

Bin Sheng

Research output: ThesisDoctoral Thesis

473 Downloads (Pure)


Parameterized algorithms is a new approach to tackle NP-hard problems. Parameterized complexity studies classic hard problems from a multivariate perspective. Apart from the input instance size, it uses some other parameter reflecting useful problem structure. The main purpose is to study how the additional structural information helps to solve the problem. In classic complexity theory, we want to decide whether a problem can be solved in polynomial time, likewise, in parameterized complexity research, we aim to provide fixed parameterized algorithms. In this thesis, we study several problems in graphs for their fixed parameter tractability or polynomial time solvability.

We first study several variants of the Chinese Postman Problem, in which we are asked to find a minimum weight closed walk that traverses each edge or arc at least once. The variants we study include the Directed k-Chinese Postman Problem and the Mixed Chinese Postman Problem. We show that both problems are fixed parameter tractable with the corresponding parameters.

Kernelization is an important subfield in the study of parameterized tractability. It asks
whether we can reduce a given problem instance into an equivalent instance of bounded size with respect to the parameter. Polynomial size kernel is of particular interest, as they extract exactly the small hard part of the problem.

In the second part of this thesis, we obtain some linear kernelization results. Let c, k be
two positive integers, given a graph G = (V, E), the c-LOAD COLORING problem asks
whether there is a c-coloring φ : V → [c] such that for every i ∈ [c], there are at least k
edges with both end-vertices colored i. We show that the c-LOAD COLORING problem
parameterized by k admits a fixed parameter algorithm, by giving both a linear-vertex and a linear-edge kernel. For a related problem, the star packing problem, we show that it also admits a linear kernel in graphs with no long induced paths. We also studied some problems on edge colored graphs from classic algorithmic perspective, including Odd Properly Colored Cycle detection, Chinese Postman Problem in edge colored graphs, cycles and acyclicity.
Original languageEnglish
Awarding Institution
  • Royal Holloway, University of London
  • Gutin, Gregory, Supervisor
  • Wahlström, Magnus, Supervisor
Thesis sponsors
Award date1 Aug 2017
Publication statusUnpublished - 2017


  • Parameterized Complexity, Chinese Postman Problem, Kernelization, Linear Kernel, Edge Colored Graphs, Polynomial Time Algorithm, Acyclicity, Packing Problem

Cite this