[Model] BiconnectivityAugmentation

[isPANN]

---

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

Motivation

BICONNECTIVITY AUGMENTATION from Garey & Johnson, A2 ND18. An NP-complete graph augmentation problem studied by Eswaran and Tarjan (1976). Given an undirected graph with weighted potential edges, the goal is to add a minimum-weight set of edges so that the resulting graph is biconnected (2-vertex-connected: cannot be disconnected by removing any single vertex). The unweighted version is polynomial-time solvable, but the weighted version is NP-complete. This problem is fundamental to network design and fault-tolerant communication network construction.

Associated rules:

• R39: HAMILTONIAN CIRCUIT -> BICONNECTIVITY AUGMENTATION (ND18)

Prerequisites: This problem depends on HamiltonianCircuit (issue #216) which is not yet in the codebase. The associated reduction rule (issue #252) cannot be implemented until both models exist.

Definition

Name: BiconnectivityAugmentation
Canonical name: Biconnectivity Augmentation (also: Weighted 2-Vertex-Connectivity Augmentation)
Reference: Garey & Johnson, Computers and Intractability, A2 ND18

Mathematical definition:

INSTANCE: Graph G = (V,E), weight w({u,v}) in Z+ for each unordered pair {u,v} of vertices from V, positive integer B.
QUESTION: Is there a set E' of unordered pairs of vertices from V such that sum_{e in E'} w(e) <= B and such that the graph G' = (V, E union E') is biconnected, i.e., cannot be disconnected by removing a single vertex?

Variables

• Count: num_potential_edges binary variables (one per potential edge listed in potential_weights)
• Per-variable domain: binary {0, 1} — whether edge {u,v} is added to E'
• Meaning: variable x_{u,v} = 1 if the edge {u,v} is added to E'. The configuration must satisfy: G' = (V, E union E') is biconnected and sum(w({u,v}) * x_{u,v}) <= B.
• dims() specification: vec![2; self.potential_weights.len()]. Each variable is binary, representing whether a potential edge is added.

Schema (data type)

Type name: BiconnectivityAugmentation
Variants: graph topology (graph type parameter G), weight type (W)

Field	Type	Description
graph	G: Graph	The initial undirected graph G = (V, E)
potential_weights	Vec<(usize, usize, W)>	Weighted potential edges: list of (u, v, weight) triples
budget	W	Maximum total weight B for added edges

Size fields (getter methods for overhead expressions):

• num_vertices() → self.graph.num_vertices() (= |V|)
• num_edges() → self.graph.num_edges() (= |E|)
• num_potential_edges() → self.potential_weights.len() (= number of candidate edges)

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• The optimization version minimizes sum(w(e)) for e in E' subject to biconnectivity of G union E'.
• A graph is biconnected if it is connected and has no articulation point (cut vertex).
• Potential edges are stored as explicit (u, v, weight) triples rather than a HashMap to align with codebase conventions.

Complexity

• Decision complexity: NP-complete (Eswaran and Tarjan, 1976; transformation from HAMILTONIAN CIRCUIT). Remains NP-complete when all weights are 1 or 2 and E is empty. Solvable in polynomial time when all weights are equal.
• Best known exact algorithm: Brute-force enumeration over all subsets of potential edges with biconnectivity check: O*(2^num_potential_edges) in the worst case. For practical instances, ILP-based exact methods with cut enumeration are used, but no better worst-case bound is known for the general weighted case.
• Unweighted version: Solvable in O(n + m) time by finding the block-cut tree and computing the minimum number of edges to add (Eswaran and Tarjan, 1976).
• Approximation: 2-approximation via primal-dual methods (Frederickson and Ja'Ja', 1981). Note: the (1.5+epsilon)-approximation by Traub and Zenklusen (2023) addresses edge-connectivity augmentation (WCAP), not 2-vertex-connectivity/biconnectivity augmentation.
• declare_variants! guidance:

  crate::declare_variants! {
      BiconnectivityAugmentation<SimpleGraph, i32> => "2^num_potential_edges",
  }

  This reflects the brute-force bound over all potential edge subsets. If a better exact algorithm is found in the literature, update accordingly.
• References:
  • K.P. Eswaran, R.E. Tarjan (1976). "Augmentation Problems." SIAM Journal on Computing, 5(4):653-665.
  • G.N. Frederickson, J. Ja'Ja' (1981). "Approximation Algorithms for Several Graph Augmentation Problems." SIAM Journal on Computing, 10(2):270-283.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), weight w({u,v}) in Z+ for each unordered pair {u,v} of vertices from V, positive integer B.
QUESTION: Is there a set E' of unordered pairs of vertices from V such that sum_{e in E'} w(e) <= B and such that the graph G' = (V,E union E') is biconnected, i.e., cannot be disconnected by removing a single vertex?

Reference: [Eswaran and Tarjan, 1976]. Transformation from HAMILTONIAN CIRCUIT.
Comment: The related problem in which G' must be bridge connected, i.e., cannot be disconnected by removing a single edge, is also NP-complete. Both problems remain NP-complete if all weights are either 1 or 2 and E is empty. Both can be solved in polynomial time if all weights are equal.

How to solve

• It can be solved by (existing) bruteforce. Enumerate all subsets of potential edges, check if adding them achieves biconnectivity and total weight <= B.
• It can be solved by reducing to integer programming. Binary variable per potential edge, minimize total weight subject to biconnectivity constraints (no cut vertex).
• Other: For the unweighted case, linear-time algorithms exist based on the block-cut tree decomposition.

Example Instance

Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 5 edges (a path graph):

• Existing edges: {0,1}, {1,2}, {2,3}, {3,4}, {4,5}
• This is a path graph; every internal vertex is an articulation point, so G is NOT biconnected.
• Edge weights for all potential edges:
  • {0,2}: w=1, {0,3}: w=2, {0,4}: w=3, {0,5}: w=2
  • {1,3}: w=1, {1,4}: w=2, {1,5}: w=3
  • {2,4}: w=1, {2,5}: w=2
  • {3,5}: w=1
• Budget B = 4

Solution: add E' = {{0,2}, {1,3}, {2,4}, {3,5}} with weights 1+1+1+1 = 4 <= B:

• New graph G' has edges: {0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {0,2}, {1,3}, {2,4}, {3,5}
• Check biconnectivity: remove any single vertex:
  • Remove 0: remaining {1,2,3,4,5} connected via {1,2},{1,3},{2,3},{2,4},{3,4},{3,5},{4,5}
  • Remove 1: remaining {0,2,3,4,5} connected via {0,2},{2,3},{2,4},{3,4},{3,5},{4,5}
  • Remove 2: remaining {0,1,3,4,5} connected via {0,1},{1,3},{3,4},{3,5},{4,5}
  • Remove 3: remaining {0,1,2,4,5} connected via {0,1},{0,2},{1,2},{2,4},{4,5}
  • Remove 4: remaining {0,1,2,3,5} connected via {0,1},{0,2},{1,2},{1,3},{2,3},{3,5}
  • Remove 5: remaining {0,1,2,3,4} connected via {0,1},{0,2},{1,2},{1,3},{2,3},{2,4},{3,4}
• G' is biconnected. Answer: YES with B=4.
• With B=3: we can only add 3 unit-weight edges. Adding {0,2},{1,3},{2,4} leaves vertex 5 as a pendant -- removing vertex 4 disconnects 5. Answer: NO.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not in the reduction graph; listed in G&J as ND18 and in the Compendium of NP Optimization Problems
Non-trivial	✅ Pass	Distinct feasibility constraint (biconnectivity) from all 24 existing problems
Correctness	⚠️ Warn	Two issues: (1) Traub & Zenklusen result is for edge-connectivity augmentation, not vertex-connectivity/biconnectivity; (2) no concrete best-known exact algorithm time bound cited
Well-written	⚠️ Warn	Missing concrete complexity string for declare_variants!; naming should use Minimum prefix per project conventions

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

The problem BiconnectivityAugmentation does not exist in the codebase (confirmed via pred show). It is a well-known NP-complete problem from Garey & Johnson (A2 ND18) and appears in the Compendium of NP Optimization Problems under Network Design. The associated rule (Hamiltonian Circuit -> Biconnectivity Augmentation) would connect it to the reduction graph, assuming a Hamiltonian Circuit model is added later. The motivation (network fault tolerance, communication network design) is concrete and well-justified.

Non-trivial

This is genuinely distinct from all 24 existing problems. It is a graph augmentation problem with a biconnectivity feasibility constraint — no existing problem has this structure. The closest existing problem is TravelingSalesman (also a graph connectivity problem), but TSP asks for a minimum-cost Hamiltonian cycle, not minimum-cost edge augmentation for 2-vertex-connectivity. This is clearly a different problem.

Correctness

References verified:

1. Eswaran & Tarjan (1976), "Augmentation Problems", SIAM J. Comput. 5(4):653-665 — Confirmed. The paper proves that weighted biconnectivity augmentation is NP-complete via transformation from Hamiltonian Circuit, and gives polynomial-time algorithms for the unweighted version. The claims in the issue match the paper's results.

2. Frederickson & Ja'Ja' (1981), "Approximation Algorithms for Several Graph Augmentation Problems", SIAM J. Comput. 10(2):270-283 — Confirmed. The paper presents constant-factor approximation algorithms for weighted graph augmentation problems including biconnectivity. Citation is accurate.

3. Traub & Zenklusen (2023), "(1.5+epsilon)-approximation" — The issue is slightly misleading here. The Traub & Zenklusen (1.5+epsilon)-approximation is for the Weighted Connectivity Augmentation Problem (WCAP), which concerns edge-connectivity, not vertex-connectivity/biconnectivity. The issue says "the related weighted connectivity augmentation problem," which is technically correct (it is related), but readers could easily confuse this with an approximation for the biconnectivity augmentation problem itself. The best known approximation for weighted biconnectivity augmentation is the 2-approximation from Frederickson & Ja'Ja'.

Complexity concerns:

• The statement "Exact algorithms have complexity exponential in O(min(n, alpha)), where alpha is related to the block-cut tree structure" is vague and not backed by a specific citation. No concrete best-known exact algorithm with a specific time bound (e.g., O*(2^n) or similar) is provided. This is needed for the declare_variants! macro, which requires a concrete complexity string.
• The claim "Remains NP-complete when all weights are 1 or 2 and E is empty" is consistent with Garey & Johnson.
• The claim "Solvable in polynomial time when all weights are equal" is consistent with Eswaran & Tarjan 1976.

Well-written

Information completeness: All required template sections are present and substantive.

Issues found:

1. Naming convention: Per project conventions, minimization problems use the Minimum prefix (e.g., MinimumVertexCover, MinimumDominatingSet, MinimumSetCovering). The optimization version of this problem minimizes total edge weight, so the name should be MinimumBiconnectivityAugmentation rather than BiconnectivityAugmentation. However, since the issue defines this as a satisfaction/decision problem (Metric = bool), the current name could be acceptable — but this is inconsistent with the Compendium which lists it as "Minimum Biconnectivity Augmentation".

2. Missing concrete complexity string: The declare_variants! macro requires a concrete complexity expression like "2^num_vertices". The issue's complexity section only gives a vague "exponential in O(min(n, alpha))" without a specific algorithm or bound. This needs to be resolved before implementation.

3. Schema design: The edge_weights: HashMap<(usize,usize), W> field is non-standard for this codebase. Existing graph-based problems use the graph type parameter G with inherent weight support. Consider whether this problem should store potential edges as a separate weighted graph or use a different representation.

4. Decision vs. optimization framing: The issue frames this as a satisfaction problem with a budget parameter B, but the Compendium and most literature treat it as an optimization problem (minimize total weight subject to biconnectivity). Consider whether the optimization formulation (Metric = SolutionSize<W>, minimize sum of added edge weights) would be more natural and useful for reductions.

Example quality: The worked example with 6 vertices is well-detailed, shows the full reduction construction, verifies biconnectivity by checking all vertex removals, and includes a negative case (B=3). This is good.

Recommendations

• Clarify the Traub & Zenklusen citation to explicitly state it addresses edge-connectivity, not biconnectivity (2-vertex-connectivity).
• Provide a concrete best-known exact algorithm time bound for the weighted case (likely O*(2^n) via brute-force over edge subsets, or better via ILP).
• Consider renaming to MinimumBiconnectivityAugmentation and using the optimization formulation, which would be more consistent with project conventions and the literature.

[isPANN]

Fix-issue changelog

• Aligned Variables section with schema: changed variable count from n*(n-1)/2 to num_potential_edges (one per entry in potential_weights)
• Updated dims() specification from vec![2; n*(n-1)/2] to vec![2; self.potential_weights.len()]
• Updated best known exact algorithm complexity from O*(2^(n*(n-1)/2)) to O*(2^num_potential_edges)
• Updated declare_variants! complexity string from "2^(num_vertices * (num_vertices - 1) / 2)" to "2^num_potential_edges"

Applied by /fix-issue.