Vertex Cover to Dominating Set (Karp Reduction)

Definition

Vertex Cover to Dominating Set

There is a polynomial-time many-one reduction from the Vertex Cover problem to the Dominating Set problem:

Construction

Given a vertex cover instance with , first remove trivial thresholds. If , output a fixed no-instance of Dominating Set; if , output a fixed yes-instance. A single isolated vertex with threshold and threshold , respectively, supplies these fixed instances.

It remains to consider . We want to turn each requirement “select an endpoint of this edge” into “dominate this new vertex”. Domination also requires us to take care of the original vertices; a separate gadget will do that for one extra selection.

Reserve one selection for the original vertices

Retain , add a new vertex adjacent to every , and attach leaves to . The target budget will be . Each leaf has only one neighbour: .

If is not selected, all leaves must be selected themselves. Since , this is impossible within the budget. Thus is forced, leaving at most selections. This works even when has isolated vertices. The picture shows only the new star edges; the original edges are handled next.

Turn each edge into a vertex to dominate

For each original edge , delete and insert a fresh vertex with exactly the neighbours and . In particular, do not join to .

The orange edges join to the original endpoints, not to the new subdivision vertex. Selecting therefore dominates and , but not : domination does not pass through an already dominated neighbour. The leaves and the rest of the graph are omitted here.

Once is selected, the only vertices still requiring attention are the subdivision vertices. Selecting dominates every whose original edge is incident with : the same selection covers those edges in .

There is one subtlety: a dominating set could select itself instead of an endpoint. The backward proof below explicitly removes this possibility by replacement; it does not assume that all remaining selections already lie in .

Assemble the output

The construction is therefore:

1. Retain every original vertex .
2. Add a vertex , join it to every original vertex, and attach new leaves to . The vertex dominates the original vertices and the leaves.
3. For every original edge , introduce a subdivision vertex and replace by the two edges and . The vertex is not adjacent to any .
4. Output the Dominating Set instance

Equivalently,

The vertex dominates every original vertex and every leaf. The chosen original vertex dominates both subdivision vertices, exactly as it covers both original edges.

Correctness

The graph has a vertex cover of size at most if and only if has a dominating set of size at most .

Correctness

Forward: a vertex cover gives a dominating set

Suppose that has a vertex cover with . Set

The vertex dominates itself, every original vertex, and every leaf. Now fix an edge . Since covers , at least one endpoint belongs to . That selected endpoint is adjacent to in :

The two rows show either endpoint supplying the required neighbour. If both endpoints belong to , both dominate ; the argument requires at least one, not exactly one. Since every original edge is covered, every subdivision vertex is dominated. Hence, is a dominating set with .

Backward: a dominating set gives a vertex cover

Suppose that dominates and .

Force the extra vertex

If , each leaf must belong to , so , a contradiction. Hence .

Replace selections that are not original vertices

First remove selected leaves from the selected set, not from the graph. Each leaf has only the neighbour , and remains selected. Thus neither the leaf nor loses domination.

Next, for every selected , choose one endpoint and replace by in the selected set. The graph again stays unchanged. The following picture chooses ; choosing is symmetric. Orange vertices are selected, and orange edges show the relevant domination adjacencies.

Only could lose domination when is unselected: these are all the vertices it dominated. Afterwards, dominates , and the still-selected dominates both endpoints. Every other vertex keeps its previous selected dominator. If was already selected, simply remove ; otherwise replace one selection by one selection. In either case the number of selected vertices does not increase.

Define the resulting original-vertex set directly by

Repeated endpoints count only once, so

Check every original edge

Fix any . The only ways to dominate are to select , , or itself. If or belongs to , that endpoint belongs to . Otherwise , and the chosen endpoint belongs to . In either case . Since was arbitrary, covers every edge.

Running Time

After the trivial thresholds are removed, we have . The construction adds one forced vertex, leaves, and one subdivision vertex per edge. It creates

vertices and edges and can be computed in polynomial time. More precisely, writing and ,

The graph can be built in vertex/edge operations. The threshold preprocessing matters: is encoded in binary, so constructing leaves without first bounding would not in general be polynomial in the input length.

The output is linear in , not necessarily in : a dense graph can have . For an ETH lower bound measured in the number of target vertices, the direct reduction from 3-SAT avoids this potential quadratic increase.

NP-completeness

Vertex Cover is NP-hard, so this reduction proves that Dominating Set is NP-hard. Together with membership in NP, this proves that Dominating Set is NP-complete.