Enumerating and Indexing Constrained Graph Partitions Using Decision Diagrams

Yu Nakahata (1651202)

Graph partitioning is important for several applications such as evacuation planning, political redistricting, VLSI design, and so on. Many types of graph partitioning problems are NP-hard, and thus it is difficult to find a good graph partition efficiently. In addition, it is often the case that there are several objective functions and we cannot decide the priority between them clearly. Then it is difficult to define what is the optimal solution. In such a case, it is useful to enumerate some solutions with moderately good objectives. However, there are exponentially many graph partitions in a graph, and thus it is difficult to enumerate such graph partitions efficiently.

In this thesis, we study an approach using a zero-suppressed binary decision diagram (ZDD), which is a data structure representing a family of sets in a compressed way. Especially, we focus on two types of graph partitioning problems and propose algorithms to construct ZDDs representing sets of such graph partitions. First, we deal with the evacuation planning problem, which asks us to partition a target area, represented by a graph, into several regions so that each region contains exactly one shelter. The problem has many complex constraints on the distances between evacuees and the assigned shelters, the capacities of shelters, and the convexity of components such that the intersections of evacuation routes less occur. There is an existing method to construct a ZDD representing a set of graph partitions satisfying the constraints. However, the algorithm is limited to a grid graph because the definition of convexity of components is specialized for grid graphs. To deal with general graphs, we reformulated the definition of convexity of components as spanning shortest path forests (SSPFs), and propose an algorithm to construct a ZDD representing a set of SSPFs in a given graph. Experimental results using real-world map data show that our algorithm can construct a ZDD for graphs with hundreds of edges in a few minutes.

Second, we deal with balanced graph partitions. When we are given a vertex-weighted graph, it is important to find a graph partition such that each weight of its connected component is in a given range for applications such as political redistricting, VLSI design, parallel processing, and so on. There is an existing algorithm to construct a ZDD representing the set of balanced graph partitions. However, the computation is tractable only for graphs with less than a hundred of vertices because the algorithm tries to construct the ZDD in one step, which leads to the increase of the memory consumption exponentially. To construct a ZDD more efficiently, we propose a new algorithm for the problem. The proposed algorithm divides the construction of the ZDD into several steps and suppresses the memory consumption. Experimental results show that our algorithm runs up to tens of times faster than the existing algorithm.

In the presentation, we will talk mainly about the second study, which is on balanced graph partitions.