11.27

Membership in NP. For a graph G_e whose vertices all have even degree and an integer k, a certificate is just a list of at most k vertices; in O(|E|) time we can check that every edge is incident to one of them. Thus the problem is in NP.

NP–hardness – reduction from ordinary vertex cover.
Given an arbitrary instance ⟨G=( V,E ), k⟩ we build, in polynomial time, a graph G_e whose vertices all have even degree and an integer k_e such that     (G,k) is a YES-instance  ⇔  (G_e,k_e) is a YES-instance.

1. Compute the set O of vertices of odd degree in G. |O| is even.
2. Arbitrarily pair the vertices of O; write the pairs as {u₁,v₁}, … , {u_t,v_t} with t=|O|/2.
3. For every pair {u,v} introduce two fresh vertices p_uv and q_uv and the 3-edge path     u – p_uv – q_uv – v. (The new vertices have degree 2, the paired vertices gain one new incident edge, so every vertex degree becomes even.)
4. Let G_e be the resulting graph and set     k_e = k + 2t. (Each added path will force exactly two extra vertices into any minimum cover, as shown below.)

Correctness.
• (⇒) Let S be a vertex cover of G with |S|≤k. For every added path u – p – q – v insert p and q into S; call the extended set S′. |S′| = |S| + 2t = k_e, and every edge of G_e is incident to S′, so (G_e,k_e) is accepted.

• (⇐) Let S′ be a vertex cover of G_e with |S′|≤k_e. Inspect any added path u – p – q – v. A single vertex covers at most two of its three edges, so every cover must select at least two vertices from {u,p,q,v}. If S′ already contains both p and q we do nothing; otherwise replace whichever endpoints of the path lie in S′ by the missing internal vertices so that exactly {p,q} stays in the cover. This local replacement never increases the size of S′ and still covers the path. After processing all t paths we obtain a cover S″ with
    • both internal vertices of every added path are in S″;
    • no endpoint u or v of a path lies in S″ unless it was already needed for an original edge.
Consequently S = S″∩V covers every edge of the original graph G and |S| = |S″| – 2t ≤ k_e – 2t = k. Hence (G,k) is accepted.

Size and degree. The construction adds only 2t vertices and 3t edges, so it is polynomial. By Step 3 every vertex (old or new) has even degree, so G_e satisfies the promised restriction.

Because the reduction is polynomial, the problem remains NP-complete even when all vertices are required to have even degree.

Back to Chapter 11