[Model] BalancedCompleteBipartiteSubgraph

[isPANN]

---

name: Problem
about: Propose a new problem type
title: "[Model] BalancedCompleteBipartiteSubgraph"
labels: model
assignees: ''

Motivation

BALANCED COMPLETE BIPARTITE SUBGRAPH from Garey & Johnson, A1.2 GT24. A classical NP-complete problem useful for reductions. Also known as the Maximum Balanced Biclique Problem (MBBP), it has applications in data mining, bioinformatics (protein-protein interaction networks), VLSI design, and document clustering.

Associated reduction rules:

• As target: R26 (CLIQUE -> BALANCED COMPLETE BIPARTITE SUBGRAPH) -- the NP-completeness proof by Garey and Johnson.
• As source: None found in the current rule set.

Definition

Name: BalancedCompleteBipartiteSubgraph

Canonical name: BALANCED COMPLETE BIPARTITE SUBGRAPH (also: Maximum Balanced Biclique, Balanced Biclique)
Reference: Garey & Johnson, Computers and Intractability, A1.2 GT24

Mathematical definition:

INSTANCE: Bipartite graph G = (V,E), positive integer K <= |V|.
QUESTION: Are there two disjoint subsets V1, V2 <= V such that |V1| = |V2| = K and such that u in V1, v in V2 implies that {u,v} in E?

Variables

• Count: n = |V| binary variables (one per vertex), encoding membership in V1 or V2. For a bipartite graph with bipartition V = A union B where |A| = n_A and |B| = n_B, we have n = n_A + n_B binary variables.
• Per-variable domain: {0, 1} where 0 = not selected, 1 = selected.
• dims(): returns vec![2; n] where n = n_A + n_B (total number of vertices). The first n_A variables correspond to vertices in partition A, the remaining n_B variables correspond to vertices in partition B.
• Meaning: For i < n_A, config[i] = 1 means vertex i from partition A is included in V1. For j >= n_A, config[j] = 1 means vertex j - n_A from partition B is included in V2. A satisfying assignment has sum(config[0..n_A]) = sum(config[n_A..n]) = K and for every pair (i,j) with config[i] = 1 and config[n_A + j] = 1, the edge {i,j} exists in E.

Schema (data type)

Type name: BalancedCompleteBipartiteSubgraph
Variants: graph type parameter G (bipartite graphs only)

Field	Type	Description
graph	BipartiteGraph	The bipartite graph in which a balanced complete bipartite subgraph is sought
k	usize	The required size K of each side of the biclique

Size fields (getter methods for overhead expressions):

• num_vertices() -> usize — total number of vertices |V|
• num_edges() -> usize — number of edges |E|
• k() -> usize — required biclique side size K

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• The graph must be bipartite. The BipartiteGraph type encodes the bipartition.
• Uses lowercase k consistently for the field name; corresponds to the parameter K in the mathematical definition.

Complexity

Best known algorithm and declare_variants!:

crate::declare_variants! {
    BalancedCompleteBipartiteSubgraph => "1.3803^num_vertices",
}

• The O*(1.3803^n) bound is from Chen et al. (2020), specifically for dense bipartite graphs. For sparse graphs, performance may differ.

• Brute force: O(2^n) by trying all subsets of each partition.

• NP-completeness: NP-complete (Garey and Johnson, 1979, GT24). Transformation from CLIQUE.

• Parameterized complexity: W[1]-hard parameterized by solution size K (Lin, 2018, "The Parameterized Complexity of the k-Biclique Problem").

• Approximation hardness: NP-hard to approximate within a factor of n^(1-epsilon) for any epsilon > 0, assuming the Small Set Expansion Hypothesis and NP != BPP (Manurangsi, 2017).

• References:

  • Garey, M.R. and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman.
  • Chen, Y. et al. (2020). "Efficient Exact Algorithms for Maximum Balanced Biclique Search in Bipartite Graphs". arXiv:2007.08836.
  • Lin, B. (2018). "The Parameterized Complexity of the k-Biclique Problem". Journal of the ACM 65(5).

Extra Remark

Full book text:

INSTANCE: Bipartite graph G = (V,E), positive integer K <= |V|.
QUESTION: Are there two disjoint subsets V1, V2 <= V such that |V1| = |V2| = K and such that u in V1, v in V2 implies that {u,v} in E?
Reference: [Garey and Johnson, ----]. Transformation from CLIQUE.
Comment: The related problem in which the requirement "|V1| = |V2| = K" is replaced by "|V1|+|V2| = 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].

How to solve

• It can be solved by (existing) bruteforce -- enumerate all pairs of K-subsets from each partition and check completeness.
• It can be solved by reducing to integer programming -- ILP formulation: binary variables for vertex selection, constraints for completeness and balance.
• Other: Branch-and-bound with upper bound propagation (Chen et al., 2020); reduction to CLIQUE on a derived graph.

Example Instance

Instance 1 (maximum balanced biclique is K=2):
Bipartite graph G with bipartition A = {a0, a1, a2, a3} and B = {b0, b1, b2, b3}, 10 edges:

• Edges: {a0,b0}, {a0,b1}, {a0,b2}, {a1,b0}, {a1,b1}, {a1,b3}, {a2,b0}, {a2,b2}, {a2,b3}, {a3,b1}
• K = 2: YES. Solution: V1 = {a0, a1}, V2 = {b0, b1} — all 4 cross-edges exist: a0-b0, a0-b1, a1-b0, a1-b1.
• K = 3: NO. No three vertices from A share three common neighbors in B.

Instance 2 (has balanced biclique of size 3):
Bipartite graph G with bipartition A = {a0, a1, a2, a3} and B = {b0, b1, b2, b3}, 12 edges:

• Edges: {a0,b0}, {a0,b1}, {a0,b2}, {a1,b0}, {a1,b1}, {a1,b2}, {a2,b0}, {a2,b1}, {a2,b2}, {a3,b0}, {a3,b1}, {a3,b3}
• K = 3: YES. Solution: V1 = {a0, a1, a2}, V2 = {b0, b1, b2}.
  • Check all 9 pairs: a0-b0, a0-b1, a0-b2, a1-b0, a1-b1, a1-b2, a2-b0, a2-b1, a2-b2 — all present.
• Note: a3 is NOT in V1 because a3-b2 is missing.
• Greedy trap: Including a3 (which has 3 edges) leads to failure since a3's neighbors {b0, b1, b3} don't fully overlap with any 3 vertices in B that also connect to a0, a1, a2.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph; distinct from existing BicliqueCover
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	⚠️ Warn	Minor citation inaccuracies; approximation hardness claim omits an assumption
Well-written	⚠️ Warn	Variable encoding inconsistency; decision vs. optimization ambiguity; example Instance 1 has self-correcting errors

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. The problem BalancedCompleteBipartiteSubgraph does not exist in the current codebase. It is distinct from the existing BicliqueCover problem (which covers all bipartite edges with k bicliques, a covering/partition problem). This problem instead asks whether a balanced complete bipartite subgraph K_{K,K} exists — a subgraph-finding problem with different feasibility constraints and objective.

The motivation is concrete (data mining, bioinformatics, VLSI design) and the issue identifies a reduction path from CLIQUE. The problem would add a new node to the reduction graph with at least one incoming edge.

Non-trivial

Pass. This problem has genuinely different feasibility constraints from all 24 existing problems. It requires finding two equal-sized disjoint vertex sets that form a complete bipartite subgraph — this is not equivalent to any existing problem under renaming or restriction. While BicliqueCover also involves bicliques, its objective (covering all edges) is fundamentally different from finding a single large balanced biclique.

Correctness

Warn. Most claims are verifiable, but there are minor inaccuracies:

1. Garey & Johnson GT24 — Correct. Multiple sources confirm that "Balanced Complete Bipartite Subgraph" is indeed GT24 in Garey & Johnson (1979), p. 196. The NP-completeness via transformation from CLIQUE is correct.

2. Chen et al. (2020) — Correct. The paper "Efficient Exact Algorithms for Maximum Balanced Biclique Search in Bipartite Graphs" (arXiv:2007.08836) exists and proposes the O*(1.3803^n) algorithm for dense bipartite graphs. However, this bound is specifically for dense bipartite graphs. The issue presents it as the general best-known bound without this qualification.

3. Lin (2015) — Year is wrong. The paper "The Parameterized Complexity of the k-Biclique Problem" by Bingkai Lin was published in JACM 2018 (volume 65, issue 5), not 2015. The arXiv preprint dates to 2014. The W[1]-hardness result is correct — the paper provides an fpt-reduction from k-Clique to k-Biclique.

4. Manurangsi (2017) — Partially correct. The paper "Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis" (ICALP 2017) does prove n^(1-epsilon) inapproximability. However, the issue omits that this requires both SSEH and NP ≠ BPP (not just SSEH alone).

Well-written

Warn. The issue is mostly complete and well-structured, but has several issues:

Variable Encoding Inconsistency

The Variables section presents two conflicting encodings:

• First: "Per-variable domain: {0, 1, 2}" (ternary encoding)
• Then: "Alternatively, two binary indicator vectors: x_i in {0,1} for V1, y_j in {0,1} for V2"

These are not equivalent — the ternary encoding uses n variables while the binary encoding uses n_A + n_B variables. The issue should commit to one. For this codebase, the binary encoding (two indicator vectors) is more natural and matches how dims() would return [2, 2, ..., 2].

Decision vs. Optimization Ambiguity

The Schema section says this is a satisfaction problem with Metric = bool, but then mentions an optimization variant with Metric = SolutionSize<usize>. Following the project naming conventions:

• If it is a decision problem (given K, does a K_{K,K} exist?): the name BalancedCompleteBipartiteSubgraph is fine, and it should implement SatisfactionProblem.
• If it is an optimization problem (find the largest K): it should be named with a Maximum prefix (e.g., MaximumBalancedBiclique).

The issue should pick one. Garey & Johnson's GT24 is a decision problem.

Example Instance 1 Contains Self-Correcting Errors

Instance 1 initially claims K=3 is achievable, then through trial-and-error discovers it is not, concluding the maximum is K=2. While the final answer is correct, this reads as a draft — the working-out of incorrect attempts is confusing. The example should be cleaned up to state the instance, the answer (K=3: NO, K=2: YES), and provide the solution directly without the false starts.

Instance 2 is well-constructed and clearly presented.

Missing Size Fields

The Schema does not mention what size_fields (getter methods) the problem type should expose. For overhead expressions in future reductions, fields like num_vertices, num_edges, k would be needed.

Minor: Symbol Consistency

The definition uses K (uppercase) for the biclique size parameter, but the schema table uses k (lowercase). These should be consistent.

Recommendations

• Fix Lin citation year from 2015 to 2018 (JACM publication) or 2014 (arXiv preprint)
• Add "NP ≠ BPP" to the Manurangsi approximation hardness assumptions
• Clarify that O*(1.3803^n) is specifically for dense bipartite graphs
• Commit to either decision or optimization formulation
• Clean up Example Instance 1 to remove trial-and-error working
• Standardize K/k notation across sections

[isPANN]

Resolved the warnings above.

[isPANN]

Changelog: Added missing 'and NP != BPP' assumption to Manurangsi (2017) approximation hardness claim.