[Rule] VertexCover to MinimumWeightAndOrGraph

[isPANN]

Source: VERTEX COVER (VertexCover)
Target: MINIMUM WEIGHT AND/OR GRAPH SOLUTION (MinimumWeightAndOrGraph)

Motivation: The previous X3C body was incorrect. This is the correct unit-weight reduction for Min-and/or.

Reference: M. D. da Silva, F. Protti, U. S. Souza, "Revisiting the Complexity of And/Or Graph Solution", Theorem 1 (2012).

Model Note

This issue is for the unit-weight version of Minimum Weight And/Or Graph Solution.

If the repository also wants the original Sahni 1974 result, that should be a separate rule:

• 3-SAT -> Min-and/or with 0/1 edge costs.

Reduction Algorithm

Input:

• an undirected graph G = (V, E)
• an integer k

Let

• V = {v_1, ..., v_n}
• E = {e_1, ..., e_m}

Construct an and/or graph G' = (V', E') as follows.

Vertices

Create:

• one source vertex s, labeled and
• for each edge e_i in E, one vertex w_e[i], labeled or
• for each vertex v_j in V, one vertex w_v[j], labeled or
• for each vertex v_j in V, one sink t_v[j]

Edges

Add:

1. (s, w_e[i]) for every i = 1..m
2. (w_e[i], w_v[j]) iff edge e_i is incident to vertex v_j in G
3. (w_v[j], t_v[j]) for every j = 1..n

Assign weight 1 to every edge of G'.

Set
K = 2m + k.

Output the instance (G', K).

Forward Witness Map

Suppose C subseteq V is a vertex cover of G with |C| <= k.

Construct a solution subgraph H of G' as follows:

1. Include s.
2. Since s is an and-vertex, include every edge (s, w_e[i]).
3. For each edge-node w_e[i], choose one endpoint v_j of e_i that lies in C, and include edge (w_e[i], w_v[j]).
4. For each selected vertex-node w_v[j], include edge (w_v[j], t_v[j]).

Weight count:

• m edges from s
• m chosen edges from edge-nodes
• |C| sink edges

So the total weight is
m + m + |C| = 2m + |C| <= 2m + k = K.

Extraction Pass

Suppose G' has a solution subgraph H of weight at most K.

Because all edge weights are positive, delete redundant outgoing edges from every or-node until each or-node keeps exactly one outgoing edge and feasibility is preserved.

Let
X = { v_j in V : w_v[j] belongs to H }.

Then:

1. Every edge (s, w_e[i]) must belong to H, contributing m to the weight.
2. Every edge-node w_e[i] must choose at least one outgoing edge, contributing another m.
3. Every selected vertex-node w_v[j] must include its unique sink edge (w_v[j], t_v[j]), contributing |X|.

Hence
2m + |X| <= K = 2m + k,
so |X| <= k.

Now fix any source edge e_i.
Since w_e[i] is in H and has one outgoing edge in H, that edge must go to some w_v[j] such that e_i is incident to v_j.
Therefore every source edge is incident to some vertex in X.

So X is a vertex cover of G of size at most k.

Correctness

G has a vertex cover of size at most k
iff
G' has a solution subgraph of weight at most 2|E| + k.

Size Overhead

Let n = |V| and m = |E|.

Then:

• |V'| = 1 + m + 2n
• |E'| = m + 2m + n = 3m + n
• all edges have weight 1
• every or-vertex has out-degree at most 2
• every vertex with in-degree greater than 1 is one edge away from a sink

So the construction is polynomial and matches the restricted family used in the proof.

Example

Source instance:

• V = {v_1, v_2, v_3}
• E = {e_1 = {v_1, v_2}, e_2 = {v_2, v_3}}
• k = 1

A vertex cover is C = {v_2}.

Constructed target:

• source s
• edge-nodes w_e[1], w_e[2]
• vertex-nodes w_v[1], w_v[2], w_v[3]
• sinks t_v[1], t_v[2], t_v[3]

Edges:

• (s, w_e[1]), (s, w_e[2])
• (w_e[1], w_v[1]), (w_e[1], w_v[2])
• (w_e[2], w_v[2]), (w_e[2], w_v[3])
• (w_v[j], t_v[j]) for j=1,2,3

All weights are 1, and
K = 2*2 + 1 = 5.

Choose:

• (w_e[1], w_v[2])
• (w_e[2], w_v[2])
• (w_v[2], t_v[2])

Together with the two forced edges from s, this gives a solution subgraph of weight 5.

Implementation Notes

1. This is the correct unit-weight reduction.
2. Do not keep the old X3C "coupling gadget" body.
3. If the project wants the original Sahni construction as well, add a separate issue for
   3-SAT -> Min-and/or with 0/1 weights.

[GiggleLiu]

Implemented in PR #1028. File: src/rules/minimumvertexcover_minimumweightandorgraph.rs