[Rule] KClique to BalancedCompleteBipartiteSubgraph

[isPANN]

---

name: Rule
about: Propose a new reduction rule
title: "[Rule] KClique to BalancedCompleteBipartiteSubgraph"
labels: rule
assignees: ''
canonical_source_name: 'KClique'
canonical_target_name: 'BalancedCompleteBipartiteSubgraph'
source_in_codebase: false
target_in_codebase: true

Source: KClique (satisfaction: does G have a clique of size k?)
Target: BALANCED COMPLETE BIPARTITE SUBGRAPH
Motivation: Establishes NP-completeness of BALANCED COMPLETE BIPARTITE SUBGRAPH via polynomial-time reduction from CLIQUE. This is the classical reduction attributed to Garey and Johnson (unpublished, cited in Computers and Intractability [GT24]) and later published in Johnson's NP-completeness column (1987). The problem has applications in data mining, bioinformatics (protein interaction networks), and VLSI design.
Reference: Johnson, D.S. (1987). "The NP-completeness column: an ongoing guide." Journal of Algorithms 8(3):438–448. Originally referenced as [Garey and Johnson, ----] in Computers and Intractability, A1.2 GT24.

GJ Source Entry

[GT24] BALANCED COMPLETE BIPARTITE SUBGRAPH
INSTANCE: Bipartite graph G = (V,E), positive integer K <= |V|.
QUESTION: Are there two disjoint subsets V_1, V_2 <= V such that |V_1| = |V_2| = K and such that u in V_1, v in V_2 implies that {u,v} in E?

Reference: [Garey and Johnson, ----]. Transformation from CLIQUE.
Comment: The related problem in which the requirement "|V_1| = |V_2| = K" is replaced by "|V_1|+|V_2| = K" is solvable in polynomial time for bipartite graphs (because of the connection between matchings and independent sets in such graphs, e.g., see [Harary, 1969]), but is NP-complete for general graphs [Yannakakis, 1978b].

Reduction Algorithm

Given a KClique instance (G = (V, E), k) where G is a general graph with n = |V| vertices and m = |E| edges, construct a BalancedCompleteBipartiteSubgraph instance (H = (A ∪ B, F), K') as follows:

1. Pad the vertex set. Let C(k) = k(k−1)/2 (the number of edges in a k-clique). To guarantee the construction is valid, add C(k) isolated vertices to V. Set n' = n + C(k). Isolated vertices do not change the clique number.

2. Part A (left partition). A = V' = {v₀, v₁, …, v_{n'−1}}, the padded vertex set. |A| = n'.

3. Part B (right partition). B consists of two types of elements:

   • Edge elements: one element eⱼ for each edge eⱼ = {u, w} ∈ E. There are m such elements.
   • Padding elements: W = {w₀, w₁, …, w_{|W|−1}} where |W| = n − k. (Note: n' − k − C(k) = n + C(k) − k − C(k) = n − k ≥ 0 since k ≤ n.)
   • |B| = m + n − k.

4. Bipartite edges (non-incidence + full padding). For each v ∈ A and b ∈ B:

   • If b = eⱼ = {u, w} is an edge element: add edge {v, eⱼ} to F if and only if v ∉ {u, w} (v is not an endpoint of eⱼ).
   • If b = wᵢ is a padding element: always add edge {v, wᵢ} to F.

5. Balanced biclique parameter. Set K' = n' − k = n + C(k) − k.

6. Solution extraction. Given a satisfying BCBS assignment selecting left vertices A' ⊆ A and right elements B' ⊆ B with |A'| = |B'| = K', the k-clique in G is S = {v ∈ V : v ∉ A'} — the original vertices not selected on the left side. The extracted source configuration is: source_config[v] = 1 − target_config[v] for v ∈ {0, …, n−1}.

Correctness proof sketch:

• (Forward) If S ⊆ V is a k-clique, let A' = V' \ S (the n' − k vertices not in S) and B' = E(S) ∪ W, where E(S) = {eⱼ ∈ E : both endpoints in S}. Since S is a k-clique, |E(S)| = C(k) and |B'| = C(k) + (n − k) = n' − k = K'. For any v ∈ A' and eⱼ ∈ E(S): both endpoints of eⱼ are in S, and v ∉ S, so v is not an endpoint of eⱼ — the edge exists. For any v ∈ A' and wᵢ ∈ W: the edge always exists. So (A', B') is a balanced K'-biclique.

• (Backward) If (A', B') is a balanced K'-biclique in H, let S = {v ∈ V : v ∉ A'} with |S| = k. Consider any edge eⱼ = {u, w} ∈ E with at least one endpoint in A' (say u ∈ A'). Then u is an endpoint of eⱼ, so {u, eⱼ} ∉ F, meaning eⱼ ∉ B'. Therefore B' ∩ E ⊆ E(S) (only edges with both endpoints in S can be in B'). Since |B'| = K' = n' − k and B' ⊆ E(S) ∪ W with |W| = n − k, we need |E(S)| ≥ K' − |W| = (n' − k) − (n − k) = C(k). But |E(S)| ≤ C(k) (at most C(k,2) edges among k vertices), so |E(S)| = C(k), which means every pair in S is connected — S is a k-clique.

Size Overhead

Symbols:

• n = num_vertices of source G
• m = num_edges of source G
• k = k (clique size parameter of source KClique)

Target metric (code name)	Formula (using source getters)
left_size	num_vertices + k * (k - 1) / 2
right_size	num_edges + num_vertices - k
k	num_vertices + k * (k - 1) / 2 - k

Derivation:

• left_size = n' = n + C(k,2) = n + k(k−1)/2. One vertex per original vertex plus C(k,2) isolated padding vertices.
• right_size = m + |W| = m + (n − k). One element per original edge plus n − k padding elements.
• Target biclique parameter K' = n' − k = n + k(k−1)/2 − k.

Validation Method

• Closed-loop test: Construct a KClique instance, reduce to BalancedCompleteBipartiteSubgraph, solve the target with BruteForce (find_satisfying), extract the clique via solution extraction (invert left-side selection), verify it is a valid k-clique in the original graph.
• Forward test: Construct a graph with a known k-clique, verify the bipartite graph contains a balanced K'-biclique.
• Backward test (negative): Construct a graph with no k-clique (e.g., K_{3,3} bipartite graph with k = 3), verify the bipartite graph has no balanced K'-biclique.
• Size verification: Check left_size = n + C(k,2), right_size = m + n − k, target k = n + C(k,2) − k.

Example

Source instance (KClique):
Graph G with 4 vertices {0, 1, 2, 3} and 4 edges:

• Edges: {0,1}, {0,2}, {1,2}, {2,3}
• k = 3
• The unique 3-clique is {0, 1, 2}. No other 3-clique exists ({0,1,3}: no edge {1,3}; {0,2,3}: no edge {0,3}; {1,2,3}: no edge {1,3}).

Construction:

• n = 4, m = 4, k = 3, C(3,2) = 3.
• Pad with 3 isolated vertices: V' = {0, 1, 2, 3, 4, 5, 6}, n' = 7.
• Part A: {0, 1, 2, 3, 4, 5, 6} (7 vertices).
• Part B: {e₀={0,1}, e₁={0,2}, e₂={1,2}, e₃={2,3}, w₀} (4 edges + 1 padding = 5 elements).
• |W| = n − k = 4 − 3 = 1. K' = n' − k = 7 − 3 = 4.

Bipartite edges (non-incidence for edge elements, always for padding):

Vertex v	Connected B-elements (v not endpoint of eⱼ, or padding)
0	e₂={1,2}, e₃={2,3}, w₀
1	e₁={0,2}, e₃={2,3}, w₀
2	e₀={0,1}, w₀
3	e₀={0,1}, e₁={0,2}, e₂={1,2}, w₀
4 (pad)	e₀, e₁, e₂, e₃, w₀ (all)
5 (pad)	e₀, e₁, e₂, e₃, w₀ (all)
6 (pad)	e₀, e₁, e₂, e₃, w₀ (all)

Total bipartite edges: 3 + 3 + 2 + 4 + 5 + 5 + 5 = 27.

Constructed target instance:
BalancedCompleteBipartiteSubgraph with left_size = 7, right_size = 5, k = 4, and the 27 bipartite edges listed above.

Solution mapping:

• Balanced 4-biclique: A' = {3, 4, 5, 6}, B' = {e₀, e₁, e₂, w₀}.
• Verify completeness (all 16 cross-edges):
  • v=3: e₀ ✓ (3 ∉ {0,1}), e₁ ✓ (3 ∉ {0,2}), e₂ ✓ (3 ∉ {1,2}), w₀ ✓ (padding)
  • v=4: e₀ ✓, e₁ ✓, e₂ ✓, w₀ ✓ (isolated, not endpoint of anything)
  • v=5: e₀ ✓, e₁ ✓, e₂ ✓, w₀ ✓
  • v=6: e₀ ✓, e₁ ✓, e₂ ✓, w₀ ✓
• Extracted clique: S = V \ A' ∩ {0,1,2,3} = {0, 1, 2}.
• Check in G: {0,1} ✓, {0,2} ✓, {1,2} ✓. Valid 3-clique. ✓

Target metric	Value	Formula check
left_size	7	4 + 3·2/2 = 7 ✓
right_size	5	4 + 4 − 3 = 5 ✓
k	4	4 + 3 − 3 = 4 ✓

References

• Johnson (1987): D.S. Johnson, "The NP-completeness column: an ongoing guide," Journal of Algorithms 8(3):438–448, 1987. Published proof of the CLIQUE → BALANCED COMPLETE BIPARTITE SUBGRAPH reduction originally referenced as [Garey and Johnson, ----] in Computers and Intractability.
• Garey & Johnson (1979): M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979. Problem [GT24], p. 196.
• [Harary, 1969]: F. Harary, Graph Theory, Addison-Wesley, 1969.
• [Yannakakis, 1978b]: M. Yannakakis, "Node- and edge-deletion NP-complete problems," in Proc. 10th Ann. ACM Symp. on Theory of Computing, pp. 253–264, 1978.

Note on related but distinct problems: Peeters (2003) proves NP-completeness of the maximum edge biclique problem (maximize |A|·|B|) using a modification of this reduction. That is a different problem from the balanced biclique problem (|A| = |B| = K) addressed here.

[isPANN]

Issue Quality Check — Rule

Check	Result	Details
Prerequisites	❌ Fail	BalancedCompleteBipartiteSubgraph is not implemented in the codebase

Overall: 0 passed, 1 failed (remaining checks skipped)

---

Prerequisites

• ✅ Source MaximumClique: implemented
• ❌ Target BalancedCompleteBipartiteSubgraph: not found in codebase

Cannot evaluate this rule: BalancedCompleteBipartiteSubgraph is not implemented in the codebase. The corresponding [Model] issue must be merged first before this [Rule] can be evaluated.

Note: BicliqueCover exists in the codebase but is a different problem (covering edges with bicliques, not finding a balanced complete bipartite subgraph).

Checks 1–4 skipped.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path MaximumClique → BalancedCompleteBipartiteSubgraph; target not yet in codebase
Non-trivial	✅ Pass	Involves gadget construction with auxiliary padding vertices and complement encoding
Correctness	❌ Fail	The reduction algorithm described in the issue does NOT match the known Garey-Johnson/Peeters construction; multiple factual errors
Well-written	❌ Fail	Algorithm is internally inconsistent, example discovers its own failure mid-way, overhead table is wrong

Overall: 2 passed, 0 warnings, 2 failed

---

Usefulness

Pass. The target problem "Balanced Complete Bipartite Subgraph" does not exist in the codebase, and there is no existing reduction path from MaximumClique to any biclique-type problem. MaximumClique currently only reduces to ILP. This reduction would add a novel connection to the reduction graph.

Note: The issue is already labeled Blocked because the target model is not yet implemented.

Non-trivial

Pass. The actual CLIQUE → BALANCED COMPLETE BIPARTITE SUBGRAPH reduction (as published) involves a genuine structural transformation: constructing a bipartite graph where one partition contains vertices and the other contains edges plus auxiliary padding elements, with a complement-style edge construction. This is not a simple relabeling or subtype coercion.

Correctness

Fail. The reduction algorithm described in the issue is fundamentally wrong, and several references are inaccurate.

Algorithm errors

The issue proposes a "bipartite double" construction: create two copies L and R of V, add edge {u_L, v_R} for each edge {u,v} in G. This does not correctly reduce CLIQUE to BALANCED COMPLETE BIPARTITE SUBGRAPH. The issue itself discovers this failure in the Example section, where it notes that V_1 = {0_L, 1_L, 2_L}, V_2 = {0_R, 1_R, 2_R} does not work because "0_L--0_R is NOT present." It then patches with diagonal edges, but this ad-hoc fix is not the standard reduction and its correctness is not proven.

The actual reduction (published in Johnson 1987, referenced in Peeters 2003) is completely different:

• V_1 = V (original vertices)
• V_2 = E ∪ W (original edges plus a padding set W of size K²/2 − K)
• Edges in the bipartite graph: {v, e} where v ∈ V, e ∈ E, and v is NOT an endpoint of e (complement encoding), plus {v, w} for all v ∈ V, w ∈ W
• The target biclique size K' = K³ − 3K²/2

This is a fundamentally different construction where one side of the bipartition contains edges of the original graph (not a second copy of vertices), and the adjacency is complement-based (vertex connects to edge when it is NOT incident to that edge).

Reference errors

1. The issue cites "Garey and Johnson, ----" as the source. The GJ book entry [GT24] states "Transformation from CLIQUE" and cites "[Garey and Johnson, ----]" — meaning the proof was unpublished at the time of the book. The actual proof was later published in: D.S. Johnson, "The NP-completeness column: an ongoing guide," J. Algorithms 8(3), pp. 438–448, 1987. The issue should cite Johnson (1987) as the primary reference.

2. The Peeters (2003) citation is accurate — the paper exists in Discrete Applied Mathematics 131(3), pp. 651–654, and it does discuss a modification of the CLIQUE → balanced biclique reduction. However, Peeters' paper proves NP-completeness of the maximum edge biclique problem (|A|*|B| ≥ K), which is a different problem from the balanced biclique problem (|A| = |B| = K). The issue conflates these two problems.

Well-written

Fail. Multiple issues:

1. Algorithm is internally inconsistent. The "Reduction Algorithm" section describes one construction (bipartite double with adjacency edges), but the "Example" section discovers that this construction fails and proposes a different one (adding diagonal edges). The example contradicts the algorithm.

2. Example is not fully worked. The example attempts to verify the biclique, discovers the construction doesn't work, then proposes a "Revised construction with diagonal" that was never mentioned in the algorithm. An example should demonstrate the algorithm, not debug it.

3. Size Overhead table is wrong. The table claims num_edges = 2 * num_edges, but the "Revised construction" in the example produces 24 = 2*9 + 6 edges, which is 2 * num_edges + num_vertices, contradicting the overhead table. Under the actual Johnson (1987) reduction, the construction is entirely different and the overhead would involve the number of edges of G appearing as vertices on one side.

4. Solution extraction is incorrect. Step 4 claims "let S = {u ∈ V : u_L ∈ V_1} = {v ∈ V : v_R ∈ V_2}. Then S is a clique." In the actual reduction, the biclique's two sides are V−C (vertices) and the clique's edges plus padding — the extraction is quite different.

5. Symbol inconsistency. The "Derivation" paragraph under Size Overhead mentions "directed bipartite edges" and "self-loops u_L--u_R," introducing concepts not defined in the algorithm.

6. Missing definition of n and m. While the Symbols subsection defines n and m, the algorithm section uses |V| and |E| without connecting them to the overhead table's num_vertices and num_edges.

7. The "Note" at the end of the algorithm acknowledges that "precise details vary" and mentions "padding vertices (W)" — which is actually the correct construction — but this is buried as a disclaimer rather than being the primary algorithm.

Recommendations

• Rewrite the algorithm to match the actual Johnson (1987) construction: V_1 = V, V_2 = E ∪ W with complement-style edges. Read Peeters (2003) Section 2 for the clearest presentation.
• Add the Johnson (1987) reference: D.S. Johnson, "The NP-completeness column: an ongoing guide," J. Algorithms 8(3), 1987, pp. 438–448.
• Clarify which problem is being targeted: the balanced biclique problem (|A| = |B| = K) from GT24, not the maximum edge biclique problem from Peeters.
• Redo the example using the correct construction and verify the biclique step by step.
• Recalculate the overhead table based on the correct construction, where V_2 has |E| + K²/2 − K vertices.