Abstract
Parameterized algorithms is a new approach to tackle NPhard 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 kChinese 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 cLOAD COLORING problem asks
whether there is a ccoloring φ : V → [c] such that for every i ∈ [c], there are at least k
edges with both endvertices colored i. We show that the cLOAD COLORING problem
parameterized by k admits a fixed parameter algorithm, by giving both a linearvertex and a linearedge 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.
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 kChinese 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 cLOAD COLORING problem asks
whether there is a ccoloring φ : V → [c] such that for every i ∈ [c], there are at least k
edges with both endvertices colored i. We show that the cLOAD COLORING problem
parameterized by k admits a fixed parameter algorithm, by giving both a linearvertex and a linearedge 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 language  English 

Qualification  Ph.D. 
Awarding Institution 

Supervisors/Advisors 

Thesis sponsors  
Award date  1 Aug 2017 
Publication status  Unpublished  2017 
Keywords
 Parameterized Complexity, Chinese Postman Problem, Kernelization, Linear Kernel, Edge Colored Graphs, Polynomial Time Algorithm, Acyclicity, Packing Problem