Algorithms For The Judicious Partitions Of Digraphs

The graph partition problem mainly studies how to divide the vertex set of a given graph into several parts to optimize one or several quantities.It is a hot issue in combinatorial optimization theory and is widely used in many fields such as the field of image segmentation.One of the most classical graph partition problems is the max-cut problem of graphs,which asks for a partition V1,V2 of the vertex set V of a graph G so that the number e(V1,V2)of the crossing edges is maximal.When the max-cut problem is generalized to directed graphs,the number e(V1,V2)of arcs for V1 to V2 and the number e(V2,V1)of arcs for V2 to V1 should be considered simultaneously.This kind of problems considering multiple quantities at the same time are called the judicious partition problems.In 2005,Scott introduced the judicious partition problem of directed graphs:Given a directed graph D,ask for a partition Vi,V2 of the vertex set V(D)to maximize min{e(Vi,V2),e(V1,V2)}.The problem of judicious partitions of digraphs is NP hard,and so there is still not a non-trivial characterization of its optimal solutions and a corresponding polynomial time exact algorithm.At present,the research on the judicious partitions of digraphs mainly focuses on the lower bound of its optimal value.This thesis will study its algorithms.In Chapter 2,firstly,we consider the judicious partitions of weighted digraphs,and build nine integer programming models for the judicious partitions of digraphs from different angles.For two of the models,the integer constraints are relaxed and the corresponding relaxation models are given.Based on the optimal solution of the relaxation models,random algorithms are designed by random rounding technique.It is proved that the expected approximation ratio of one of the algorithms is 0.7566.In Chapter 3,we introduce the definition of k-optimal judicious partitions and give some sufficient and necessary conditions for its existence.Based on the sufficient and necessary conditions,an exact algorithm for solving the judicious partition problem of digraphs is designed from the perspective of searching special arc sets,and the correctness and time complexity of the algorithm are proved.Then,the judicious partition problem of a digraph is transformed into an independent set problem in its line graph,and then is transformed into a problem about control sets and controlled sets in an auxiliary graph.Finally,from the perspective of searching special control sets and controlled sets,an exact algorithm for finding the optimal judicious partition of directed graphs is given,and the correctness and time complexity of the algorithm are proved.