**Polynomial and FPT algorithms for Chinese Postman, Packing and Acyclicity.** / Sheng, Bin.

Research output: Thesis › Doctoral Thesis

Unpublished

**Polynomial and FPT algorithms for Chinese Postman, Packing and Acyclicity.** / Sheng, Bin.

Research output: Thesis › Doctoral Thesis

Sheng, B 2017, 'Polynomial and FPT algorithms for Chinese Postman, Packing and Acyclicity', Ph.D., Royal Holloway, University of London.

@phdthesis{8eedd88a5ae748b6a8eb7c15a83c8979,

title = "Polynomial and FPT algorithms for Chinese Postman, Packing and Acyclicity",

abstract = "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 askswhether 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 betwo positive integers, given a graph G = (V, E), the c-LOAD COLORING problem askswhether there is a c-coloring φ : V → [c] such that for every i ∈ [c], there are at least kedges with both end-vertices colored i. We show that the c-LOAD COLORING problemparameterized 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.",

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

author = "Bin Sheng",

year = "2017",

language = "English",

school = "Royal Holloway, University of London",

}

TY - THES

T1 - Polynomial and FPT algorithms for Chinese Postman, Packing and Acyclicity

AU - Sheng, Bin

PY - 2017

Y1 - 2017

N2 - 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 askswhether 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 betwo positive integers, given a graph G = (V, E), the c-LOAD COLORING problem askswhether there is a c-coloring φ : V → [c] such that for every i ∈ [c], there are at least kedges with both end-vertices colored i. We show that the c-LOAD COLORING problemparameterized 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.

AB - 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 askswhether 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 betwo positive integers, given a graph G = (V, E), the c-LOAD COLORING problem askswhether there is a c-coloring φ : V → [c] such that for every i ∈ [c], there are at least kedges with both end-vertices colored i. We show that the c-LOAD COLORING problemparameterized 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.

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

M3 - Doctoral Thesis

ER -