[Model] StrongConnectivityAugmentation

[isPANN]

---

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

Motivation

STRONG CONNECTIVITY AUGMENTATION (P95) from Garey & Johnson, A2 ND19. An NP-complete directed graph augmentation problem studied by Eswaran and Tarjan (1976). Given a directed graph with weighted potential arcs, the goal is to add a minimum-weight set of arcs so that the resulting digraph is strongly connected (every vertex is reachable from every other vertex). The unweighted version is polynomial-time solvable in linear time, but the weighted version is NP-complete. Fundamental to robust communication network design.

This issue covers the decision (satisfaction) version. A separate issue for the optimization version (MinimumStrongConnectivityAugmentation, minimizing total arc weight subject to strong connectivity) is planned.

Associated rules:

• R40: HAMILTONIAN CIRCUIT -> STRONG CONNECTIVITY AUGMENTATION (ND19)

Definition

Name: StrongConnectivityAugmentation
Canonical name: Strong Connectivity Augmentation (also: Weighted Strong Connectivity Augmentation)
Reference: Garey & Johnson, Computers and Intractability, A2 ND19

Mathematical definition:

INSTANCE: Directed graph G = (V,A), weight w(u,v) in Z+ for each ordered pair (u,v) in V x V \ A, positive integer B.
QUESTION: Is there a set A' of ordered pairs of vertices from V \ A such that sum_{a in A'} w(a) <= B and such that the graph G' = (V, A union A') is strongly connected?

Variables

• Count: arc_weights.len() binary variables (one per potential directed arc not already in A)
• Per-variable domain: binary {0, 1} -- whether arc (u,v) is added to A'
• Meaning: variable x_{u,v} = 1 if the arc (u,v) is added to A'. The configuration must satisfy: G' = (V, A union A') is strongly connected and sum(w(u,v) * x_{u,v}) <= B.

Schema (data type)

Type name: StrongConnectivityAugmentation
Variants: graph topology (directed graph type parameter)

Field	Type	Description
graph	petgraph::Graph<(), (), Directed>	The initial directed graph G = (V, A), using petgraph's DiGraph directly
arc_weights	Vec<(usize, usize, W)>	List of potential arcs (u, v, weight) not in A
budget	W	Maximum total weight B for added arcs

Key getter methods: num_vertices() (= |V|), num_arcs() (= |A|), num_potential_arcs() (= arc_weights.len()).

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• The graph field uses petgraph::Graph<(), (), Directed> (i.e., DiGraph<(), ()>) directly rather than a custom wrapper type. This avoids the need for a separate DirectedGraph abstraction.

Complexity

• Decision complexity: NP-complete (Eswaran and Tarjan, 1976; transformation from HAMILTONIAN CIRCUIT). Remains NP-complete when all weights are 1 or 2 and A is empty. Solvable in polynomial time when all weights are equal (reduces to unweighted case).
• Best known exact algorithm: No specialized exact algorithm with a tight bound is known for the weighted directed case. Brute-force enumeration over all subsets of potential arcs gives 2^num_potential_arcs where num_potential_arcs() returns self.arc_weights.len().
• Approximation: 2-approximation via minimum cost branching/arborescence. The (1.5+epsilon)-approximation of Traub and Zenklusen (2023) applies to the related undirected connectivity augmentation; the directed weighted case remains harder to approximate.
• References:
  • K.P. Eswaran, R.E. Tarjan (1976). "Augmentation Problems." SIAM Journal on Computing, 5(4):653-665.
  • S. Raghavan (2005). "A Note on Eswaran and Tarjan's Algorithm for the Strong Connectivity Augmentation Problem." The Next Wave in Computing, Optimization, and Decision Technologies, pp. 19-26.

Extra Remark

Full book text:

INSTANCE: Directed graph G = (V,A), weight w(u,v) in Z+ for each ordered pair (u,v) in V x V, positive integer B.
QUESTION: Is there a set A' of ordered pairs of vertices from V such that sum_{a in A'} w(a) <= B and such that the graph G' = (V,A union A') is strongly connected?

Reference: [Eswaran and Tarjan, 1976]. Transformation from HAMILTONIAN CIRCUIT.
Comment: Remains NP-complete if all weights are either 1 or 2 and A is empty. 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 arcs, check if adding them achieves strong connectivity and total weight <= B.
• It can be solved by reducing to integer programming. Binary variable per potential arc, minimize total weight subject to strong connectivity constraints (flow-based formulation).
• Other: For the unweighted case, linear-time algorithm based on SCC decomposition. The minimum number of arcs to add is max(s, p), where s and p are the number of sources and sinks in the condensation DAG.

Example Instance

Directed path graph G with 5 vertices {0, 1, 2, 3, 4} and 4 arcs:

Existing arcs A:

• (0→1), (1→2), (2→3), (3→4) — a directed path

Every vertex can reach those ahead of it, but vertex 4 is a sink with no outgoing arcs. The graph is not strongly connected.

Candidate arcs with weights:

candidate_arcs = [
  (4,0,10),  // direct fix, too expensive
  (4,3,3),   // 4-escape to dead end
  (4,2,3),   // 4-escape to dead end
  (4,1,3),   // correct 4-escape
  (3,0,7),   // too expensive to combine
  (3,1,3),   // dead-end intermediate
  (2,0,7),   // too expensive to combine
  (2,1,3),   // dead-end intermediate
  (1,0,5),   // the closing arc
]

9 candidate arcs (binary variables), search space = 2^9 = 512.

Budget B = 8:
The unique satisfying augmentation selects (4→1, w=3) + (1→0, w=5) with total weight 3+5 = 8 = B. Adding these arcs creates the cycle 0→1→2→3→4→1→0, making every vertex reachable from every other. Answer: YES.

Budget B = 0:
Cannot add any arcs. Vertex 4 cannot reach any other vertex. Answer: NO.

Why this is non-trivial: All 9 candidate arcs are individually within budget. Alternative escape arcs from v4 (to v3 at w=3, or to v2 at w=3) look equally attractive, but they land on vertices from which reaching v0 within the remaining budget is impossible — all paths from v3 or v2 to v0 cost 7+, exceeding what remains after the first arc. The solver must find the specific two-step relay through v1 (the vertex closest to v0) to close the cycle within budget.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not in the reduction graph; concrete motivation (network design)
Non-trivial	✅ Pass	Distinct problem — directed graph augmentation with weights, not isomorphic to any existing model
Correctness	⚠️ Warn	Core references verified; complexity section is vague and partially inaccurate
Well-written	❌ Fail	Missing concrete complexity bound; naming convention violation; schema issues; inconsistent problem framing

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

Pass. StrongConnectivityAugmentation does not exist in the codebase (confirmed via pred show). The 24 currently registered problems do not include any directed graph augmentation problem. The motivation cites robust communication network design, which is a concrete use case. One associated reduction rule is mentioned (Hamiltonian Circuit → SCA), which would connect this to the reduction graph.

Non-trivial

Pass. This problem has genuinely distinct feasibility constraints from all existing problems. It requires: (1) selecting a subset of weighted directed arcs, (2) ensuring the augmented digraph is strongly connected, and (3) staying within a weight budget. No existing model in the codebase involves directed graph connectivity augmentation. This is not a variant of any existing problem.

Correctness

Warn. Core claims are verified but the complexity section has issues:

Verified references:

• Eswaran & Tarjan (1976), "Augmentation Problems," SIAM Journal on Computing 5(4):653-665 — Confirmed. This paper establishes the linear-time algorithm for the unweighted case and NP-completeness of the weighted case. The citation details (journal, volume, pages) match.
• Raghavan (2005), "A Note on Eswaran and Tarjan's Algorithm for the Strong Connectivity Augmentation Problem," in The Next Wave in Computing, Optimization, and Decision Technologies, pp. 19-26 — Confirmed. This note corrects an error in the original Eswaran-Tarjan algorithm.
• Garey & Johnson A2 ND19 — Consistent with the known classification of this problem.

Issues found:

1. The claim "Remains NP-complete when all weights are 1 or 2 and A is empty" is consistent with Garey & Johnson.
2. The claim "Solvable in polynomial time when all weights are equal" is correct — this reduces to the unweighted case.
3. The complexity section is too vague. The statement "Exact algorithms have exponential complexity in O(min(n, alpha))" is not a proper complexity bound — alpha is undefined, and no specific algorithm or citation is given. For declare_variants!, this project requires a concrete complexity string like "2^num_vertices" with a specific citation.
4. The Traub & Zenklusen (2023) reference is correctly noted as applying to undirected connectivity augmentation, not the directed weighted case. Good distinction.

Well-written

Fail. Several issues need to be addressed:

4a: Information Completeness

• Complexity section is incomplete: no concrete best-known exact algorithm time bound is provided. The project requires a specific complexity string (e.g., "2^num_vertices") for declare_variants!. A simple 2^(num_vertices * (num_vertices - 1)) bound from brute-force enumeration would suffice if no better bound is known, but it should be stated explicitly.

4b: Naming Convention

• The issue frames this as a satisfaction/decision problem (Metric = bool), but the natural optimization version (minimize total weight of added arcs subject to strong connectivity) would be more useful for reductions. If it remains a decision problem, the name StrongConnectivityAugmentation is acceptable. However, if the optimization version is intended, it should be named MinimumStrongConnectivityAugmentation per project naming conventions (Minimum prefix for minimization problems).
• The issue body is ambiguous — it mentions both "QUESTION: Is there a set A'..." (decision) and "The optimization version minimizes sum(w(a))..." (optimization) without clearly committing to one.

4c: Schema Issues

• DirectedGraph type does not exist in the codebase. The existing graph types are: SimpleGraph, PlanarGraph, BipartiteGraph, UnitDiskGraph, KingsSubgraph, TriangularSubgraph. A new directed graph type would need to be created (or the issue should specify how directed edges are represented).
• HashMap<(usize,usize), W> for arc_weights — this is unusual for the codebase, which typically uses graph-native weight storage. The schema should be reconsidered in light of how directed graphs would be represented.

4d: Symbol Consistency

• The variable alpha in "O(min(n, alpha))" is undefined.
• The variable count "n*(n-1)" is correct for all ordered pairs of distinct vertices, but the issue should clarify that this includes arcs already in A (which presumably should not be variables since they are already present).

4e: Example Quality

• The first example is good — a directed path with 6 vertices, clear arc weights, and a worked solution showing the Hamiltonian cycle.
• The alternative example (two SCCs) is also illustrative.
• However, the first example has a minor confusion: "weight 1 + ... wait, need to check:" reads like unfinished work. The final answer is correct (adding arc (5->0) with w=1 creates a Hamiltonian cycle), but the presentation should be cleaned up.

Recommendations

• Decide definitively whether this is a decision problem or optimization problem, and adjust the name accordingly.
• Provide a concrete worst-case complexity bound with citation for declare_variants!.
• Address the DirectedGraph type — this would be the first directed graph problem in the codebase, so the type needs to be designed or the issue should acknowledge this dependency.
• Clean up the "wait, need to check" text in the example.
• Define all symbols before use (especially alpha in the complexity section).

[isPANN]

Changelog (design decisions applied):

1. Schema: use petgraph DiGraph directly -- Changed graph field from DirectedGraph wrapper to petgraph::Graph<(), (), Directed> (i.e., DiGraph<(), ()>). Removed the "blocked until DirectedGraph is implemented" prerequisite note.

2. Schema: use Vec for arc_weights -- Changed arc_weights from HashMap<(usize,usize), W> to Vec<(usize, usize, W)> for simpler representation.

3. Complexity: use num_potential_arcs -- Changed brute-force bound from 2^(num_vertices * (num_vertices - 1)) to 2^num_potential_arcs where num_potential_arcs() returns self.arc_weights.len(). This is tighter since not all ordered pairs need to be potential arcs.

4. Example: non-trivial instance -- Replaced the trivial directed-path example with a 6-vertex, 3-SCC instance (18 potential arcs) where greedy cheapest-arc selection fails and structural SCC analysis is needed to find the optimal solution.