Report Number: CS-TN-94-11
Institution: Stanford University, Department of Computer Science
Title: On Exact and Approximate Cut Covers of Graphs
Author: Motwani, Rajeev
Author: Naor, Joseph
Date: September 1994
Abstract: We consider the minimum cut cover problem for a simple, undirected graphs G(V,E): find a minimum cardinality family of cuts C in G such that each edge e in E belongs to at least one cut c in C. The cardinality of the minimum cut cover of G is denoted by c(G). The motivation for this problem comes from testing of electronic component boards. Loulou showed that the cardinality of a minimum cut cover in the complete graph is precisely the ceiling of log n. However, determining the minimum cut cover of an arbitrary graph was posed as an open problem by Loulou. In this note we settle this open problem by showing that the cut cover problem is closely related to the graph coloring problem, thereby also obtaining a simple proof of Loulou's main result. We show that the problem is NP-complete in general, and moreover, the approximation version of this problem still remains NP-complete. Some other observations are made, all of which follow as a consequence of the close connection to graph coloring.
http://i.stanford.edu/pub/cstr/reports/cs/tn/94/11/CS-TN-94-11.pdf