The Kernelization And Parameterized Algorithms For Graph Cut Problems

Graph cut problems have always been a classic and active theme in the fields of combinatorial optimization. The research on such problems makes not only great theoretical significance in Multicommodity Network Flows, Fuzzy Cluster Editing and Directed Feedback Vertex Set, etc, but also very important practical significance in parallel and distributed computing, VLSI chip design, circuit design, computer vision, the research on the reliability and robustness of computer communication networks and many other application fields. There are many famous graph cut problems, such as Multiterminal cut, Multicut, Maximum cut and k-cut, etc, all of which are classical NP-hard problems. In this paper, we, based on the parameterized computation and complexity theory, study the edge-multiterminal cut problem and the edge-multicut problem, both of which have made some achievements.In the respect of the kernelization of the edge-multiterminal cut problem, by means of discovering its hidden structural features, we first prove that the edge-multiterminal cut problem remains NP-hard even if all the edges of the graph in the considered instance are of excess at most 1, and provide the first partial kernelization algorithm for it, which can lead to a partial kernel of size at most 6k, k is the number of removed edges. Our result, as the first kernelization achievement for the edge-multiterminal cut problem, makes great significance not only for its independence of the number l of terminal sets but also for its linear dependence on parameter k. Therefore, this result is feasible in practical use and points out a new direction for studying the kernelization of the edge-multiterminal cut problem.For the edge-multicut problem, we propose an FPT algorithm of time 0(min{(2l)l, k2l}2kn2), in which l denotes the number of terminal pairs and k denotes the number of removed edges. This algorithm improves the previously best algorithm significantly. It's noticeable that we use a thoroughly new method to prove that the upper bound on the number m of the subsets in an arbitrary greatest appropriate division of any set is [√2l], which is much more simple than the previous proof and applicable when the size of the set is at most 21. In addition, according to some characteristics of the problem, we get another upper bound on m, i.e., k+1, from which we can further infer that the final upper bound of m is min{[√2l], k+1}. Obviously, this result is also stronger than the previous best result. And based on it, we get a stronger upper bound on the total number of all the greatest appropriate division, i.e., min{(2l)l, k2l}.Finally, the study work on the above two problems is summed up, and some related future research directions are discussed briefly.