[Model] MaximumBipartiteSubgraph

[isPANN]

Motivation

MAXIMUM BIPARTITE SUBGRAPH (GT25) from Garey & Johnson, A1.1. Find a bipartition of vertices maximizing the number of edges crossing the partition (equivalently, find a maximum-size bipartite subgraph). NP-hard even for cubic graphs (Garey, Johnson, Stockmeyer 1976). Polynomial for planar graphs (Hadlock 1975, Orlova and Dorfman 1972). For simple unweighted graphs, this is equivalent to MaxCut with unit weights.

This issue proposes adding the MaxCut/SimpleGraph/One variant with alias MaximumBipartiteSubgraph, connecting the G&J GT25 problem to the existing reduction graph. The unweighted variant serves as target for R268 (Maximum2Satisfiability → MaximumBipartiteSubgraph).

Implementation

Variant: MaxCut<SimpleGraph, One> — MaxCut with unit edge weights.
Alias: MaximumBipartiteSubgraph

This reuses the existing MaxCut model infrastructure. The implementation requires:

1. Register MaxCut/SimpleGraph/One in declare_variants!
2. Add MaximumBipartiteSubgraph as an alias in the CLI

Definition

Name: MaxCut/SimpleGraph/One (alias: MaximumBipartiteSubgraph)
Reference: Garey & Johnson, Computers and Intractability, A1.1 GT25; Garey, Johnson, Stockmeyer 1976

Mathematical definition:

INSTANCE: Graph G = (V, E).
OBJECTIVE: Find a partition of V into disjoint sets V₁, V₂ that maximizes the number of edges with one endpoint in V₁ and the other in V₂.

Equivalently: find a subset E' ⊆ E of maximum size such that (V, E') is bipartite.

Variables

• Count: n = |V| (one per vertex)
• Per-variable domain: {0, 1} (partition side)
• Meaning: The bipartition assignment. An edge {u,v} crosses the partition iff the endpoints are on different sides. The objective maximizes the number of crossing edges.

Schema (data type)

Uses existing MaxCut<SimpleGraph, One>:

Field	Type	Description
graph	SimpleGraph	The input graph G = (V, E)
edge_weights	Vec<One>	Unit weights (all equal to 1)

Complexity

• Best known exact algorithm: Same as MaxCut: O*(2^(0.7907 · num_vertices)) via reduction to MaxTriangle + fast matrix multiplication (Williams 2004, ω < 2.3714).
• Complexity string: "2^(0.7907 * num_vertices)"
• Special cases: Polynomial for planar graphs via T-join / matching (Hadlock 1975). Approximable: greedy gives 1/2 approximation; SDP gives 0.878 (Goemans-Williamson 1995).

Extra Remark

Full book text:

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 [Garey, Johnson, and Stockmeyer, 1976]. Solvable in polynomial time for planar graphs [Hadlock, 1975], [Orlova and Dorfman, 1972].

Note: The original G&J formulation is a decision problem with threshold K. We use the equivalent optimization formulation: maximize the number of bipartite edges.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all 2^n partitions; count crossing edges; return maximum.)
• It can be solved by reducing to integer programming. (Inherits MaxCut's existing ILP reduction with unit weights.)
• Other:

Reduction Rule Crossref

• [Rule] MAXIMUM 2-SATISFIABILITY to MaximumBipartiteSubgraph #886 — [Rule] Maximum2Satisfiability → MaximumBipartiteSubgraph (R268, G&J GT25)
• Inherits existing MaxCut ↔ SpinGlass reductions via the variant hierarchy

Example Instance

Input:
Graph G with V = {v0, v1, v2, v3, v4} (5 vertices), 7 edges:
E = {(v0,v1), (v0,v2), (v0,v3), (v1,v2), (v1,v4), (v2,v3), (v3,v4)}

Optimal partition: V₁ = {v0, v2, v4}, V₂ = {v1, v3} (config = [0, 1, 0, 1, 0]).
Crossing edges: (v0,v1)✓, (v0,v3)✓, (v1,v2)✓, (v1,v4)✓, (v2,v3)✓, (v3,v4)✓ — 6 out of 7 edges.
Non-crossing: (v0,v2) — both in V₁.

Why 7 is impossible: Edge (v0,v1,v2) forms a triangle — at least one edge must have both endpoints on the same side. So at most 6 edges can cross.

Suboptimal partition: V₁ = {v0, v4}, V₂ = {v1, v2, v3} — 5 crossing edges.

Expected Outcome

Optimal value: Max(6) — the maximum number of bipartite edges is 6 out of 7. Out of 32 partitions, there are 6 distinct crossing-edge counts: 0, 2, 3, 4, 5, 6.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	Isomorphic to existing MaxCut for unweighted graphs; no planned reductions
Non-trivial	❌ Fail	Mathematically equivalent to MaxCut<SimpleGraph, i32> with unit weights
Correctness	⚠️ Warn	Complexity 2^num_vertices is brute-force, not the best known algorithm
Well-written	❌ Fail	Missing Expected Outcome section; decision-problem framing inconsistent with optimization semantics

Overall: 0 passed, 3 failed, 1 warning

---

Usefulness

The issue itself states multiple times that Maximum Bipartite Subgraph equals Maximum Cut for simple graphs:

"The maximum bipartite subgraph size equals the maximum cut size for simple graphs."
"this is equivalent to MAX-CUT for unweighted graphs"

MaxCut already exists in the codebase as MaxCut<SimpleGraph, i32> (GT24), with MaxCut::unweighted() constructor for unit-weight instances. Adding BipartiteSubgraph as a separate model would create an orphan node that duplicates existing functionality.

Additionally, no concrete reduction rules are mentioned connecting this problem to anything other than MaxCut (which is an identity). The "How to solve" section only checks brute-force, and notes that "the existing MaxCut model and reduction infrastructure may be reusable" — further confirming this is a duplicate rather than a novel problem.

Non-trivial

The proposed BipartiteSubgraph has identical feasibility constraints and objective to MaxCut on unweighted graphs:

• MaxCut: Given graph G = (V,E), find a partition (S, V\S) maximizing the number of edges crossing the cut.
• BipartiteSubgraph: Given graph G = (V,E), find a partition (V1, V2) maximizing the number of edges with one endpoint in V1 and one in V2.

These are the same problem. The issue's Variables section confirms: "An edge {u,v} is in E' if and only if u and v are on different sides. The objective is to maximize |E'|, so this is equivalent to MAX-CUT on unweighted graphs."

This is a trivial renaming of an existing problem (same feasibility constraints, same objective, different name).

Correctness

References verified:

• Garey & Johnson GT25 — confirmed real (Computers and Intractability, Appendix A1.1)
• Garey, Johnson, Stockmeyer 1976 — "Some Simplified NP-Complete Graph Problems", Theoretical Computer Science 1(3):237-267. Already in references.bib as gareyJohnsonStockmeyer1976 and garey1976
• Goemans-Williamson 0.878-approximation for MAX-CUT — well-known, correct

Complexity concern: The issue proposes 2^num_vertices (brute force). The existing MaxCut model uses 2^(2.372 * num_vertices / 3) which corresponds to the best known exact algorithm. Since this is the same problem, using a naive brute-force bound when a better algorithm is known is inaccurate.

Well-written

1. Missing "Expected Outcome" section: The template requires concrete optimal solutions with objective values. The example shows K3 with "Answer: YES" for K=2, but does not state the optimal objective value (maximum bipartite subgraph size = 2) in the required format.

2. Decision vs. optimization framing inconsistency: The schema has a min_edges threshold field (decision problem framing), but the issue repeatedly describes it as an optimization problem equivalent to MAX-CUT. The codebase uses optimization semantics (Max<W::Sum>) for MaxCut. This inconsistency would cause confusion during implementation.

3. No planned reductions: The "How to solve" section does not check ILP and does not reference any companion [Rule] issues. The Motivation section mentions applications but no concrete graph connectivity.

Recommendations

• If the goal is to have the Garey-Johnson GT25 naming available, consider adding BipartiteSubgraph as an alias for MaxCut (similar to how GraphPartitioning is an alias for MaxCut) rather than a separate model.
• If a genuinely distinct weighted variant is intended (where edge weights matter differently than in MaxCut), the issue should clarify how the problem differs from weighted MaxCut.

[isPANN]

Renamed from BipartiteSubgraph to MaximumBipartiteSubgraph and converted from decision framing (threshold K) to optimization framing: maximize the number of bipartite edges. Removed the min_edges field from the schema. Updated the example to show optimal values. Removed Useless/Trivial/PoorWritten labels — the problem is distinct from MaxCut for multigraphs and weighted variants, and the optimization framing is now clean.

[isPANN]

Resolution: Duplicate — use MaxCut/SimpleGraph/One variant with alias

MaximumBipartiteSubgraph on SimpleGraph is mathematically identical to MaxCut with unit weights. Rather than creating a separate model, the right approach is:

1. Register MaxCut/SimpleGraph/One as a variant in declare_variants!
2. Add MaximumBipartiteSubgraph as an alias (similar to how GraphPartitioning is already an alias for MaxCut)
3. Update rule [Rule] MAXIMUM 2-SATISFIABILITY to MaximumBipartiteSubgraph #886 (MAX-2-SAT → MaximumBipartiteSubgraph) to target MaxCut/SimpleGraph/One

This avoids an orphan duplicate model while still making the G&J GT25 name discoverable.

Closing as duplicate of existing MaxCut infrastructure.