Magnús M. HalldórssonWe 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 $\Delta$ that cut at least a $\frac{k-1}{k} (1 + \frac{1}{2\Delta+k-1})$ fraction of the 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 best performance ratio for the weighted independent set problem to $\frac{3}{\Delta+2}$, and obtain an efficient algorithm for coloring 3-colorable graphs with at most $\frac{3\Delta+2}{4}$ colors. (Nov 25, 1997)

Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.Hoong Chuin Lau

hclau@iti.gov.sg

Information Technology Institute, 11 Science Park Road, Singapore 117685