Bounds for graph bisection

Abstract

Techniques are described for graph partitioning, and in particular, graph bisection. A combinatorial lower bound is provided that is computed in near-linear time. These bounds may be used to determine optimum solutions to real-world graphs with many vertices (e.g., more than a million for road networks, or tens of thousands for VLSI and mesh instances). Combinatorial techniques that reduce the size of the branch-and-bound search tree may use tree packing, assign vertices to trees, and use fractional assignment of vertices to trees. For graph bisection, each node of the branch-and-bound tree corresponds to a partial assignment of vertices to both cells or sets of vertices.

What is claimed: 
     
         1 . A method for graph bisection, comprising:
 receiving as input, at a computing device, a graph comprising a plurality of vertices and a plurality of edges;   generating a plurality of subproblems using the graph, by the computing device;   determining a graph bisection using the subproblems and a plurality of combinatorial bounds based on disjoint paths, by the computing device; and   outputting the graph bisection.   
     
     
         2 . The method of  claim 1 , wherein generating the subproblems using the graph comprises decomposing the graph into the subproblems. 
     
     
         3 . The method of  claim 1 , wherein determining the graph bisection using the subproblems comprises solving the subproblems independently. 
     
     
         4 . The method of  claim 1 , wherein determining the graph bisection using the subproblems comprises using a branch-and-bound technique. 
     
     
         5 . The method of  claim 4 , wherein the branch-and-bound technique generates a tree, and further comprising determining an optimum balanced bisection of the vertices of the graph using the tree. 
     
     
         6 . The method of  claim 5 , further comprising determining a lower bound, and pruning the tree using the lower bound. 
     
     
         7 . The method of  claim 6 , wherein the lower bound is an edge-based packing lower bound. 
     
     
         8 . The method of  claim 6 , wherein determining the lower bound comprises:
 computing a tree packing comprising a plurality of trees; and   allocating a plurality of vertex weights to the plurality of trees.   
     
     
         9 . The method of  claim 8 , wherein allocating the plurality of vertex weights to the plurality of trees comprises fractionally allocating the vertex weights to the trees. 
     
     
         10 . The method of  claim 6 , further comprising reducing the branch-and-bound tree using forced assignments. 
     
     
         11 . The method of  claim 1 , wherein the graph bisection is a balanced bisection of the vertices of the graph. 
     
     
         12 . A method for graph bisection, comprising:
 receiving as input, at a computing device, a graph comprising a plurality of vertices and a plurality of edges;   determining an edge-based packing lower bound of the graph, by the computing device;   determining a graph bisection using the edge-based packing lower bound, by the computing device; and   outputting the graph bisection.   
     
     
         13 . The method of  claim 12 , wherein determining the edge-based packing lower bound comprises:
 determining a tree packing; and   allocating a plurality of vertex weights to the tree packing.   
     
     
         14 . The method of  claim 13 , where the tree packing comprises a plurality of trees, wherein the trees are edge-disjoint and maximal, and wherein each tree contains exactly one edge incident to a set of vertices already assigned to one of the cells. 
     
     
         15 . The method of  claim 14 , further comprising allocating the vertex weights to the tree packing. 
     
     
         16 . The method of  claim 13 , wherein allocating the plurality of vertex weights to the tree packing comprises fractionally allocating the vertex weights to the tree packing. 
     
     
         17 . A system comprising:
 at least one computing device; and   a graph bisection component that receives a graph comprising a plurality of vertices and a plurality of edges, decomposes the graph into a plurality of subproblems that can be solved independently and determines a graph bisection using the subproblems and a branch-and-bound technique.   
     
     
         18 . The system of  claim 17 , wherein the graph bisection component is adapted to perform the branch-and-bound technique using partial assignments of the vertices to both cells comprising the bisected graph. 
     
     
         19 . The system of  claim 17 , wherein the branch-and-bound technique generates a tree, determines an edge-based packing lower bound, and prunes the tree using the edge-based lower bound. 
     
     
         20 . The system of  claim 19 , wherein determining the edge-based packing lower bound comprises computing a tree packing comprising a plurality of trees, and allocating a plurality of vertex weights to the plurality of trees.