Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring
Magnús M. Halldórsson, Hoong Chuin Lau · Journal of Graph Algorithms and Applications · 1997
We present practical algorithms for constructing partitions of graphs into a fixed number of vertex-disjoint subgraphs that satisfy particular degree constraints. We use this in particular to find k-cuts of graphs of maximum degree ∆ that cut at least a k−1 1 (1 + k 2∆+k−1)fractionofthe edges, improving previous bounds known. The partitions also apply to constraint networks, for which we give a tight analysis of natural local search heuristics for the maximum constraint satisfaction problem. These partitions also imply efficient approximations for several problems on weighted bounded-degree graphs. In particular, we improve the 3 best performance ratio for the weighted independent set problem to ∆+2, and obtain an efficient algorithm for coloring 3-colorable graphs with at colors. most 3∆+2