Clique cover

Last updated

In graph theory, a clique cover or partition into cliques of a given undirected graph is a partition of the vertices into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum k for which a clique cover exists is called the clique cover number of the given graph.

Contents

Relation to coloring

A clique cover of a graph G may be seen as a graph coloring of the complement graph of G, the graph on the same vertex set that has edges between non-adjacent vertices of G. Like clique covers, graph colorings are partitions of the set of vertices, but into subsets with no adjacencies (independent sets) rather than cliques. A subset of vertices is a clique in G if and only if it is an independent set in the complement of G, so a partition of the vertices of G is a clique cover of G if and only if it is a coloring of the complement of G.

Computational complexity

The clique cover problem in computational complexity theory is the algorithmic problem of finding a minimum clique cover, or (rephrased as a decision problem) finding a clique cover whose number of cliques is below a given threshold. Finding a minimum clique cover is NP-hard, and its decision version is NP-complete. It was one of Richard Karp's original 21 problems shown NP-complete in his 1972 paper "Reducibility Among Combinatorial Problems". [1]

The equivalence between clique covers and coloring is a reduction that can be used to prove the NP-completeness of the clique cover problem from the known NP-completeness of graph coloring. [2]

In special classes of graphs

Perfect graphs are defined as the graphs in which, for every induced subgraph, the chromatic number (minimum number of colors in a coloring) equals the size of the maximum clique. According to the weak perfect graph theorem, the complement of a perfect graph is also perfect. Therefore, the perfect graphs are also the graphs in which, for every induced subgraph, the clique cover number equals the size of the maximum independent set. It is possible to compute the clique cover number in perfect graphs in polynomial time.

Another class of graphs in which the minimum clique cover can be found in polynomial time are the triangle-free graphs. In these graphs, every clique cover consists of a matching (a set of disjoint pairs of adjacent vertices) together with singleton sets for the remaining unmatched vertices. The number of cliques equals the number of vertices minus the number of matched pairs. Therefore, in triangle-free graphs, the minimum clique cover can be found by using an algorithm for maximum matching.

The optimum partition into cliques can also be found in polynomial time for graphs of bounded clique-width. [3] These include, among other graphs, the cographs and distance-hereditary graphs, which are both also classes of perfect graphs.

The clique cover problem remains NP-complete on some other special classes of graphs, including the cubic planar graphs [4] and unit disk graphs. [5]

Approximation

The same hardness of approximation results that are known for graph coloring also apply to clique cover. Therefore, unless P = NP, there can be no polynomial time approximation algorithm for any ε > 0 that, on n-vertex graphs, achieves an approximation ratio better than n1 −ε. [6]

In graphs where every vertex has at most three neighbors, the clique cover remains NP-hard, and there is a constant ρ > 1 such that it is NP-hard to approximate with approximation ratio ρ or better. Nevertheless, in polynomial time it is possible to find an approximation with ratio 5/4. That is, this approximation algorithm finds a clique cover whose number of cliques is no more than 5/4 times the optimum. [4]

Baker's technique can be used to provide a polynomial-time approximation scheme for the problem on planar graphs. [7]

The related clique edge cover problem concerns partitioning the edges of a graph, rather than the vertices, into subgraphs induced by cliques. It is also NP-complete. [8]

Related Research Articles

Clique problem Task of computing complete subgraphs

In computer science, the clique problem is the computational problem of finding cliques in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique, finding a maximum weight clique in a weighted graph, listing all maximal cliques, and solving the decision problem of testing whether a graph contains a clique larger than a given size.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

Graph coloring Methodic assignment of colors to elements of a graph

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Clique (graph theory) Subset of the vertices of a node-link graph that are all adjacent to each other

In the mathematical area of graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.

Independent set (graph theory) Unrelated vertices in graphs

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.

Vertex cover Subset of a graphs vertices, including at least one endpoint of every edge

In graph theory, a vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. Finding a matching in a bipartite graph can be treated as a network flow problem.

Perfect graph Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph. Equivalently stated in symbolic terms an arbitrary graph is perfect if and only if for all we have .

Chordal graph Graph where all long cycles have a chord

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

Dominating set Subset of a graphs nodes such that all other nodes linked to at least one

In graph theory, a dominating set for a graph G = is a subset D of the vertices V such that every vertex not in D is adjacent to at least one member of D. The domination numberγ(G) is the number of vertices in a smallest dominating set for G.

In graph theory, a domatic partition of a graph is a partition of into disjoint sets , ,..., such that each Vi is a dominating set for G. The figure on the right shows a domatic partition of a graph; here the dominating set consists of the yellow vertices, consists of the green vertices, and consists of the blue vertices.

In the mathematical discipline of graph theory, a feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles. Equivalently, each FVS contains at least one vertex of any cycle in the graph. The feedback vertex set number of a graph is the size of a smallest feedback vertex set. The minimum feedback vertex set problem is an NP-complete problem; it was among the first problems shown to be NP-complete. It has wide applications in operating systems, database systems, and VLSI chip design.

Feedback arc set Edges that hit all cycles in a graph

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing a directed acyclic graph, an acyclic subgraph of the given graph. The feedback arc set with the fewest possible edges is the minimum feedback arc set and its removal leaves the maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.

Kőnigs theorem (graph theory) Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

In computational complexity theory, a gadget is a subset of a problem instance that simulates the behavior of one of the fundamental units of a different computational problem. Gadgets are typically used to construct reductions from one computational problem to another, as part of proofs of NP-completeness or other types of computational hardness. The component design technique is a method for constructing reductions by using gadgets.

Claw-free graph Graph without four-vertex star subgraphs

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

Maximum cut Problem of finding a maximum cut in a graph

For a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets S and T, such that the number of edges between the set S and the set T is as large as possible. The problem of finding a maximum cut in a graph is known as the Max-Cut Problem.

In graph theory, a branch of mathematics, a chordal completion of a given undirected graph G is a chordal graph, on the same vertex set, that has G as a subgraph. A minimal chordal completion is a chordal completion such that any graph formed by removing an edge would no longer be a chordal completion. A minimum chordal completion is a chordal completion with as few edges as possible.

References

  1. ↑ Karp, Richard (1972), "Reducibility Among Combinatorial Problems" (PDF), in Miller, R. E.; Thatcher, J. W. (eds.), Proceedings of a Symposium on the Complexity of Computer Computations, Plenum Press, pp. 85–103, archived from the original (PDF) on 2011-06-29, retrieved 2008-08-29
  2. ↑ Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , W.H. Freeman, ISBN   0-7167-1045-5 A1.2: GT19, pg.194.
  3. ↑ Espelage, Wolfgang; Gurski, Frank; Wanke, Egon (2001), "How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time", International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2001), Lecture Notes in Computer Science, vol. 2204, Springer, pp. 117–128, doi:10.1007/3-540-45477-2_12 .
  4. 1 2 Cerioli, M.R.; Faria, L.; Ferreira, T.O.; Martinhon, C.A.J.; Protti, F.; Reed, B. (June 2008), "Partition into cliques for cubic graphs: Planar case, complexity and approximation", Discrete Applied Mathematics , 156 (12): 2270–2278, doi: 10.1016/j.dam.2007.10.015 .
  5. ↑ Dumitrescu, Adrian; Pach, János (2009), "Minimum clique partition in unit disk graphs", arXiv: 0909.1552 [cs.CG].
  6. ↑ Zuckerman, D. (2007), "Linear degree extractors and the inapproximability of Max Clique and Chromatic Number" (PDF), Theory of Computing , 3: 103–128, doi: 10.4086/toc.2007.v003a006 .
  7. ↑ Blanchette, Mathieu; Kim, Ethan; Vetta, Adrian (January 2012), "Clique cover on sparse networks", 2012 Proceedings of the Fourteenth Workshop on Algorithm Engineering and Experiments (ALENEX), Society for Industrial and Applied Mathematics, pp. 93–102, doi:10.1137/1.9781611972924.10
  8. ↑ Garey & Johnson (1979), Problem GT59.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.