See also:
Q. Clique Problem. Given a graph what is the maximum set of vertices such that all vertices in are fully connected, i.e. for every , there exists edge
- NP-complete problem
Q. Independent Set Problem. (=Stable set =anti-clique) Given a graph what is the maximum set of vertices such that no edges connect any two vertices in this set?
- Complement with vertex cover.
- is an maximal independent set ⇔ is a minimal vertex cover
- Reduction both ways is trivial thm. 3-SAT Independent Set
- Construction: each clause to a fully connected tri-vertex component, and connect the variable and its negations between tri-vertex components.
- that satisfies where has clauses ⇔ Independent Set of size .
Q. Vertex Cover. Given find the minimal subset such that it covers all edges in the graph.
- e.g. graph that has a vertex cover comprising 2 vertices (bottom), but none with fewer.
- NP-complete problem
- is a minimal vertex cover ⇔ is a maximal Independent Set
- Red is vertex cover, and white is independent set:
alg. Approximate Vertex Cover.
- Choose any edge that connects vertices
- remove edge from graph, as well as any edges that connected to and
- are added to the vertex cover set
- Repeat until no edges remain
- Is a 2-approximation
alg. Approximate Greedy Vertex Cover.
- Choose vertex with maximum degree
- Add this as part of vertex cover. Remove edges connected to this vertex
- Repeat until no edges remain
- Is not optimal.
Q. Triangle Cover. Given find the minial subset of vertices that it covers at least one vertex per triangle, for every triangle in graph.
- Triangle Cover is NP-complete (reduce from vertex cover)
Q. Dominating Set. Given find the minial subset of vertices such that, every vertex in is either in or is a neighbor of
Q. Critical Vertices. Given connected graph find all vertices that when removed will disconnect the graph.