[Rule] HAMILTONIAN CIRCUIT to STRONG CONNECTIVITY AUGMENTATION

[isPANN]

---

name: Rule
about: Propose a new reduction rule
title: "[Rule] HAMILTONIAN CIRCUIT to STRONG CONNECTIVITY AUGMENTATION"
labels: rule
assignees: ''
canonical_source_name: 'HAMILTONIAN CIRCUIT'
canonical_target_name: 'STRONG CONNECTIVITY AUGMENTATION'
source_in_codebase: false
target_in_codebase: false

Source: HAMILTONIAN CIRCUIT
Target: STRONG CONNECTIVITY AUGMENTATION
Motivation: Establishes NP-completeness of the weighted STRONG CONNECTIVITY AUGMENTATION problem via polynomial-time reduction from HAMILTONIAN CIRCUIT. The key insight of Eswaran and Tarjan (1976) is analogous to the biconnectivity reduction: finding a Hamiltonian cycle in an undirected graph G is equivalent to finding a minimum-weight set of directed arcs that makes the arc-less digraph strongly connected, where arcs corresponding to edges of G have weight 1 and other arcs have weight 2.

Reference: Garey & Johnson, Computers and Intractability, ND19, p.211

GJ Source Entry

[ND19] STRONG CONNECTIVITY AUGMENTATION
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.

Reduction Algorithm

Summary:
Given a HamiltonianCircuit instance G = (V, E) with n = |V| vertices (undirected), construct a StrongConnectivityAugmentation instance (G_empty, w, B) as follows:

1. Initial digraph: Start with the arc-less directed graph G_empty = (V, empty set). No arcs at all.

2. Weight function: For each ordered pair (u, v) of distinct vertices from V, define the weight:

   • w(u, v) = 1 if {u, v} in E (the undirected edge exists in G)
   • w(u, v) = 2 if {u, v} not in E (the undirected edge does not exist in G)

   Note: both (u, v) and (v, u) get the same weight since the original graph is undirected.

3. Budget parameter: Set B = n (the number of vertices).

4. Correctness (forward direction): If G has a Hamiltonian circuit C = v_1 -> v_2 -> ... -> v_n -> v_1, orient it as a directed cycle: arcs (v_1, v_2), (v_2, v_3), ..., (v_n, v_1). This gives n directed arcs. The resulting digraph is a directed cycle on all n vertices, which is strongly connected. Each arc corresponds to an edge of G, so each has weight 1. Total weight = n = B.

5. Correctness (reverse direction): If there exists A' with sum(w(a)) <= B = n such that (V, A') is strongly connected, then:

   • A strongly connected digraph on n vertices requires at least n arcs.
   • Each arc has weight >= 1, so with budget n, there are exactly n arcs each of weight 1.
   • All arcs in A' correspond to edges of G (non-edges have weight 2).
   • A strongly connected digraph on n vertices with exactly n arcs must be a directed Hamiltonian cycle (a single directed cycle visiting every vertex exactly once).
   • The underlying undirected edges of A' form a Hamiltonian circuit of G.

6. Solution extraction: Take the set of arcs A', ignore orientations to get undirected edges. These edges form a Hamiltonian circuit of G.

Key insight: A strongly connected digraph on n vertices with exactly n arcs must be a single directed cycle (since every vertex needs in-degree >= 1 and out-degree >= 1, and n arcs among n vertices with these constraints forces a single cycle). This directed cycle, when ignoring orientations, gives a Hamiltonian circuit.

Size Overhead

Symbols:

• n = num_vertices of source HamiltonianCircuit instance (|V|)
• m = num_edges of source HamiltonianCircuit instance (|E|)

Target metric (code name)	Polynomial (using symbols above)
num_vertices	num_vertices
num_arcs (initial)	0
num_potential_arcs	num_vertices * (num_vertices - 1)

Derivation:

• Vertices: same vertex set, no changes -> n
• Initial arcs: 0 (arc-less digraph)
• Potential arcs (all ordered pairs): n(n-1) pairs, each with weight 1 or 2
• Budget: B = n

Validation Method

• Closed-loop test: reduce a HamiltonianCircuit instance G to StrongConnectivityAugmentation (G_empty, w, B=n), solve target with BruteForce (enumerate subsets of arcs with total weight <= n, check strong connectivity), extract Hamiltonian circuit by ignoring arc orientations, verify it visits all vertices exactly once
• Test with a graph known to have a Hamiltonian circuit (e.g., cycle C_n, complete graph K_n) and verify the augmentation solution uses exactly n weight-1 arcs
• Test with a graph known to NOT have a Hamiltonian circuit and verify no valid augmentation within budget n exists
• Verify that any solution arc set A' with weight n forms a directed cycle on all n vertices

Example

Source instance (HamiltonianCircuit):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 9 edges:

• Edges: {0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {5,0}, {0,3}, {1,4}, {2,5}
• (Prism graph / triangular prism)
• Known Hamiltonian circuit: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 0

Constructed target instance (StrongConnectivityAugmentation):

Initial digraph: arc-less on vertices {0, 1, 2, 3, 4, 5} (no arcs).

Weight function for all 30 ordered pairs (u, v) where u != v:

• Weight 1 (ordered pairs where {u,v} in E): (0,1),(1,0), (1,2),(2,1), (2,3),(3,2), (3,4),(4,3), (4,5),(5,4), (5,0),(0,5), (0,3),(3,0), (1,4),(4,1), (2,5),(5,2) -- 18 ordered pairs
• Weight 2 (ordered pairs where {u,v} not in E): (0,2),(2,0), (0,4),(4,0), (1,3),(3,1), (1,5),(5,1), (2,4),(4,2), (3,5),(5,3) -- 12 ordered pairs

Budget: B = 6

Solution mapping:

• Choose A' = {(0,1), (1,2), (2,3), (3,4), (4,5), (5,0)} (directed Hamiltonian cycle)
• Total weight = 6 * 1 = 6 = B
• Digraph (V, A') is the directed cycle 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 0, which is strongly connected
• Extracted Hamiltonian circuit (undirected): {0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {5,0}

Verification that no cheaper solution exists:

• A strongly connected digraph on 6 vertices needs >= 6 arcs
• Each arc costs >= 1, so minimum cost >= 6 = B
• Any solution with cost 6 must use exactly 6 arcs of weight 1 (edges of G)
• The only strongly connected digraph with 6 vertices and 6 arcs is a directed 6-cycle = Hamiltonian circuit

References

• [Eswaran and Tarjan, 1976]: [Eswaran and Tarjan1976] K. P. Eswaran and R. E. Tarjan (1976). "Augmentation problems". SIAM Journal on Computing 5, pp. 653-665.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Both source and target are new problems not in the codebase
Non-trivial	✅ Pass	Genuine structural transformation with weight-based gadget construction
Correctness	✅ Pass	Eswaran & Tarjan (1976) confirmed; reduction matches GJ ND19
Well-written	⚠️ Warn	Minor issues: missing getter names for target, num_potential_arcs not standard

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Neither HAMILTONIAN CIRCUIT nor STRONG CONNECTIVITY AUGMENTATION exist in the codebase. Both pred show HamiltonianCircuit and pred show StrongConnectivityAugmentation fail. This means implementing this rule requires implementing two new models first, which is a significant prerequisite.

Since no path can exist (neither problem is in the graph), the reduction is novel by default. However, the practical usefulness is limited until both models are added. The motivation is well-stated — it establishes NP-completeness of weighted strong connectivity augmentation via Hamiltonian Circuit, following the classic Eswaran-Tarjan construction.

Result: Warn — novel reduction, but depends on two unimplemented models.

Non-trivial

The reduction involves a genuine structural transformation:

• An undirected graph is converted to a weighted directed graph (arc-less digraph with weight function over all ordered pairs)
• Weight assignment encodes graph adjacency: edges of G get weight 1, non-edges get weight 2
• The budget parameter B = n creates a tight constraint forcing any feasible solution to use only weight-1 arcs
• The key insight (a strongly connected digraph on n vertices with exactly n arcs must be a single directed cycle) provides the correctness bridge

This is not a variable substitution, subtype coercion, or identity reduction.

Result: Pass

Correctness

Reference verification:

[Eswaran and Tarjan, 1976] — "Augmentation Problems", SIAM Journal on Computing 5, pp. 653-665.

• Confirmed: Paper exists at SIAM JoC
• The paper proves that the weighted version of strong connectivity augmentation is NP-complete, while the unweighted version is solvable in linear time
• The reduction from Hamiltonian Circuit with weights restricted to {1, 2} is a known result consistent with the literature
• This paper is not currently in docs/paper/references.bib

Garey & Johnson, ND19, p.211 — The issue correctly identifies the GJ classification. The reference file confirms GT34 = Hamiltonian Circuit in the GJ numbering, and ND19 = Strong Connectivity Augmentation is consistent with the Network Design section.

Reduction correctness:

• The forward direction is correct: a Hamiltonian cycle oriented as a directed cycle gives n arcs, each of weight 1, total weight n = B
• The reverse direction is correct: budget n with minimum weight 1 forces exactly n arcs of weight 1 (= edges of G), and n arcs on n vertices with in-degree >= 1, out-degree >= 1 must form a single Hamiltonian cycle
• The construction and proof are mathematically sound

Result: Pass

Well-written

4a: Information Completeness

All required sections are present and substantive: Source, Target, Motivation, Reference, Reduction Algorithm, Size Overhead, Validation Method, Example. No placeholder sections.

4b: Algorithm Completeness

The reduction algorithm is detailed with 6 numbered steps plus a key insight. The construction is clear, the forward and reverse correctness arguments are explicit, and solution extraction is specified. This is implementable.

4c: Symbol and Notation Consistency

• Symbols are generally well-defined: n = |V|, G = (V, E), w(u,v) for weights
• Minor issue: The overhead table uses num_potential_arcs which is not a standard getter name for any existing problem type. Since StrongConnectivityAugmentation doesn't exist yet, these getter names are speculative. The metric num_arcs marked as "(initial)" with value 0 is also unusual — typically overhead describes the target problem's size, and a constant 0 is not informative.
• The num_vertices overhead is correctly num_vertices (identity)

4d: Example Quality

The example uses a 6-vertex prism graph — non-trivial and large enough to be meaningful. The weight function is fully enumerated for all 30 ordered pairs. The solution is worked step-by-step with verification that no cheaper solution exists. Good quality.

Result: Warn — the overhead table metrics (num_potential_arcs, constant 0 for num_arcs) need refinement once the target model is defined. Otherwise well-written.

Recommendations

• Both HAMILTONIAN CIRCUIT and STRONG CONNECTIVITY AUGMENTATION need to be implemented as models before this rule can be added. Consider filing [Model] issues for both first.
• The overhead table should be revised once the target model schema is known — num_potential_arcs and initial arc count are not standard metrics.
• Add Eswaran & Tarjan 1976 to docs/paper/references.bib when implementing.
• The unweighted strong connectivity augmentation is polynomial-time solvable (Eswaran & Tarjan showed linear-time algorithms for it) — only the weighted version is NP-complete. The issue correctly targets the weighted version but this distinction should be made explicit in the model definition.