BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TN-94-11
       ENTRY:: September 19, 1994
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: On Exact and Approximate Cut Covers of Graphs
        TYPE:: Technical Note
      AUTHOR:: Motwani, Rajeev
      AUTHOR:: Naor, Joseph
        DATE:: September 1994
       PAGES:: 6
    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.
       NOTES:: [Adminitrivia V1/Prg/19940919]
         END:: STAN//CS-TN-94-11