[Rule] MAXIMUM 2-SATISFIABILITY to MaximumBipartiteSubgraph

[isPANN]

Source: MAXIMUM 2-SATISFIABILITY (MAX 2-SAT)
Target: BIPARTITE SUBGRAPH

Motivation: Establishes NP-completeness of BIPARTITE SUBGRAPH (equivalently, MAX-CUT for unweighted graphs) via polynomial-time reduction from MAXIMUM 2-SATISFIABILITY. The reduction by Garey, Johnson, and Stockmeyer (1976) shows a natural connection between maximizing satisfied 2-literal clauses and maximizing edges in a bipartite subgraph. Both are optimization problems with simple local structure but global intractability.
Reference: Garey & Johnson, Computers and Intractability, A1.1 GT25; Garey, Johnson, Stockmeyer 1976

GJ Source Entry

BIPARTITE SUBGRAPH
INSTANCE: Graph G = (V,E), positive integer K ≤ |E|.
QUESTION: Are there a subset E' ⊆ E with |E'| ≥ K and a partition of V into disjoint sets V_1, V_2 such that each edge in E' has one endpoint in V_1 and one endpoint in V_2?

Reference: Transformation from MAXIMUM 2-SATISFIABILITY [Garey, Johnson, and Stockmeyer, 1976].
Comment: NP-complete even if every vertex in G has degree at most 3. Solvable in polynomial time for planar graphs.

Reduction Algorithm

Summary:
Given a Maximum 2-Satisfiability instance with n variables U = {u_1, ..., u_n}, m clauses each with at most 2 literals, and a target K (number of clauses to satisfy), construct a BipartiteSubgraph instance (G, K') as follows:

1. Variable vertices: For each variable u_i, create a vertex v_i. The bipartition assignment (V_1 or V_2) encodes the truth value: v_i ∈ V_1 means u_i = True, v_i ∈ V_2 means u_i = False.

2. Clause edges: For each 2-literal clause, add an edge encoding the clause's satisfiability condition:

   • Clause (u_i ∨ u_j): add edge {v_i, v_j} — this edge is in the bipartite subgraph (crossing) when v_i and v_j are on different sides, corresponding to at least one being True under a suitable convention (requires negation gadgets).
   • Clause (¬u_i ∨ u_j): the edge or gadget encodes the implication structure.

3. Negation handling: To handle negated literals, either use auxiliary vertices (one per literal, with forced edges) or adjust the edge counting. A common approach:

   • For each variable u_i, create two vertices: p_i (positive) and n_i (negative), connected by an edge. Any bipartition must place them on opposite sides, encoding the complementary assignment.
   • Each clause edge connects the appropriate literal vertex (p_i or n_i) to the other clause literal's vertex.

4. Bipartite edge target: Set K' as a function of K and the construction's overhead, so that achieving K' crossing edges corresponds to satisfying at least K clauses.

5. Solution extraction: From the bipartition, read off truth values from vertex placement and count satisfied clauses.

Size Overhead

Symbols:

• n = number of variables in the MAX 2-SAT instance
• m = number of clauses in the MAX 2-SAT instance

Target metric (code name)	Polynomial (using symbols above)
num_vertices	O(n) or O(2n) with literal vertices
num_edges	O(n + m)

Derivation:
With the literal-pair approach: 2n vertices (one per literal), n forced edges (between complementary literals), plus m clause edges. The bipartite subgraph target K' = K + n (satisfying K clauses corresponds to K crossing clause-edges, plus the n forced edges always cross).

Validation Method

• Closed-loop test: reduce MAX 2-SAT instance to BipartiteSubgraph, solve target with BruteForce, extract truth assignment from bipartition, count satisfied clauses, verify count ≥ K
• Test with instances where the optimum is known
• Verify the bipartite subgraph property: all retained edges cross the partition
• Note: source problem (MAX 2-SAT) is not yet in the codebase; this reduction requires implementing MAX 2-SAT first

Example

Source instance (Maximum 2-Satisfiability):
3 variables: u_1, u_2, u_3 (n = 3)
4 clauses (m = 4):

• c_1 = (u_1 ∨ u_2)
• c_2 = (¬u_1 ∨ u_3)
• c_3 = (u_2 ∨ ¬u_3)
• c_4 = (¬u_2 ∨ ¬u_3)

Target: satisfy at least K = 3 clauses.

Assignment u_1 = True, u_2 = True, u_3 = False satisfies c_1 (T∨T), c_2 (F∨F — fails), c_3 (T∨T), c_4 (F∨T) — 3 out of 4. So K = 3 is achievable.

Target instance (BipartiteSubgraph):
With literal vertices: {p_1, n_1, p_2, n_2, p_3, n_3} — 6 vertices.
Forced edges: {p_1,n_1}, {p_2,n_2}, {p_3,n_3} — 3 edges.
Clause edges: edges encoding c_1 through c_4 connecting appropriate literal vertices — 4 edges.
Total: 7 edges. Target K' = 3 + 3 = 6 (satisfy 3 clauses + 3 forced edges).

Bipartition from u_1=T, u_2=T, u_3=F: V_1 = {p_1, p_2, n_3}, V_2 = {n_1, n_2, p_3}.
Crossing edges: all 3 forced edges cross (by construction), plus clause edges for satisfied clauses cross. Total crossing ≥ 6 = K'.

References

• Garey, M. R., Johnson, D. S., & Stockmeyer, L. (1976). "Some simplified NP-complete graph problems." Theoretical Computer Science, 1(3), 237-267.
• Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, A1.1 GT25.