[Rule] HAMILTONIAN CIRCUIT to QUADRATIC ASSIGNMENT PROBLEM

[isPANN]

Source: HAMILTONIAN CIRCUIT
Target: QUADRATIC ASSIGNMENT PROBLEM
Motivation: Establishes NP-completeness of the QUADRATIC ASSIGNMENT PROBLEM (QAP) via polynomial-time reduction from HAMILTONIAN CIRCUIT. Sahni and Gonzalez (1976) used this reduction to prove that QAP is strongly NP-hard and that no polynomial-time ε-approximation exists unless P = NP, making QAP one of the "hardest of the hard" combinatorial optimization problems.

Reference: Garey & Johnson, Computers and Intractability, ND43, p.218

GJ Source Entry

[ND43] QUADRATIC ASSIGNMENT PROBLEM
INSTANCE: Non-negative integer costs c_{ij}, 1≤i,j≤n, and distances d_{kl}, 1≤k,l≤m, bound B∈Z^+.
QUESTION: Is there a one-to-one function f:{1,2,…,n}→{1,2,…,m} such that
Σ_{i=1}^{n} Σ_{j=1, j≠i}^{n} c_{ij} d_{f(i)f(j)} ≤ B ?
Reference: [Sahni and Gonzalez, 1976]. Transformation from HAMILTONIAN CIRCUIT.
Comment: Special case in which each d_{kl}=k−l and all c_{ji}=c_{ij}∈{0,1} is the NP-complete OPTIMAL LINEAR ARRANGEMENT problem. The general problem is discussed, for example, in [Garfinkel and Nemhauser, 1972].

Reduction Algorithm

Summary:
Given a HAMILTONIAN CIRCUIT instance consisting of a graph G = (V, E) with n = |V| vertices, construct a QUADRATIC ASSIGNMENT PROBLEM instance (cost matrix C, distance matrix D) as follows. The construction follows Sahni and Gonzalez (1976), §2, problem (viii), p. 561.

Note on framing: The G&J entry formulates QAP as a decision problem with bound B. In our codebase, QuadraticAssignment is an optimization problem (minimize). The reduction works because: if G has a Hamiltonian circuit, the optimal QAP cost is exactly n; if G has no Hamiltonian circuit, the optimal cost is ≥ n − 1 + ω (strictly greater than n for ω ≥ 2). Thus a Hamiltonian circuit exists iff the optimal QAP cost equals n.

1. Cost matrix (cycle adjacency) C: Define the n × n cost matrix C as the directed cycle adjacency matrix on n locations:

   c_{i,j} = 1 if j = (i mod n) + 1 (using 1-indexed positions), and c_{i,j} = 0 otherwise.

   This gives exactly n nonzero entries: c_{1,2} = c_{2,3} = ⋯ = c_{n−1,n} = c_{n,1} = 1. The matrix C encodes n locations arranged in a directed cycle 1 → 2 → ⋯ → n → 1.

2. Distance matrix (graph-based) D: Define the n × n distance matrix D from the graph G:

   d_{k,l} = 1 if {v_k, v_l} ∈ E (vertices k and l are adjacent in G), and d_{k,l} = ω otherwise (where ω ≥ 2 is a penalty value; e.g., ω = n + 1).

   Diagonal entries d_{k,k} = 0. The matrix D is symmetric since G is undirected.

3. QAP objective: The total cost for an assignment γ (a permutation mapping locations to vertices) is:

   f(γ) = Σ_{i≠j} c_{i,j} · d_{γ(i),γ(j)}

   Since c_{i,j} = 1 only for the n directed cycle edges, this simplifies to:

   f(γ) = Σ_{i=1}^{n} d_{γ(i),γ((i mod n)+1)}

   This sums the graph-distances between vertices assigned to consecutive cycle locations.

4. Correctness:

   • Forward direction: If G has a Hamiltonian circuit v_{σ(1)} → v_{σ(2)} → ⋯ → v_{σ(n)} → v_{σ(1)}, define γ(i) = σ(i). Then consecutive locations map to consecutive circuit vertices, which are all graph-adjacent: d_{γ(i),γ(i+1)} = 1 for each i. So f(γ) = n.
   • Backward direction: If f(γ) = n, then every term d_{γ(i),γ((i mod n)+1)} = 1 (since each term is ≥ 1 and there are n terms). This means every pair of vertices at consecutive cycle locations is graph-adjacent. Reading γ(1) → γ(2) → ⋯ → γ(n) → γ(1) gives a Hamiltonian circuit in G.
   • No Hamiltonian circuit: If G has no Hamiltonian circuit, then for every permutation γ, at least one pair of consecutive cycle locations maps to non-adjacent vertices, contributing ω instead of 1. So f(γ) ≥ n − 1 + ω > n.

5. Solution extraction: Given the optimal assignment γ, the Hamiltonian circuit is γ(1) → γ(2) → ⋯ → γ(n) → γ(1). If the optimal cost is > n, no Hamiltonian circuit exists.

Size Overhead

Symbols:

• n = number of vertices in source Hamiltonian Circuit instance (num_vertices)

Target metric (code name)	Polynomial (using symbols above)
num_facilities	num_vertices
num_locations	num_vertices

Derivation:

• The cost matrix C is n × n (directed cycle adjacency)
• The distance matrix D is n × n (graph-based distances with penalty ω)
• Both matrices have the same dimension n, equal to the number of vertices in G
• Total data size: O(n²) — two n × n matrices
• The reduction is clearly polynomial: constructing C takes O(n) time, and D requires reading the adjacency structure of G in O(n²) time.

Validation Method

• Closed-loop test: reduce HamiltonianCircuit instance to QuadraticAssignment, solve target with BruteForce (enumerate all n! permutations), extract solution, verify the assignment corresponds to a valid Hamiltonian circuit on source
• Compare with known results from literature
• Test with both Hamiltonian and non-Hamiltonian graphs
• Verify that the QAP optimal cost equals exactly n for graphs with Hamiltonian circuits
• Verify that the QAP optimal cost is > n for non-Hamiltonian graphs

Example

Source instance (HAMILTONIAN CIRCUIT):
Graph G with 6 vertices {1, 2, 3, 4, 5, 6} and 9 edges (prism graph):

• Edges: {1,2}, {2,3}, {3,4}, {4,5}, {5,6}, {6,1}, {1,4}, {2,5}, {3,6}
• Hamiltonian circuit exists, e.g.: 1 → 2 → 3 → 6 → 5 → 4 → 1

Constructed target instance (QUADRATIC ASSIGNMENT):

Cost matrix C (6×6, directed cycle adjacency on 6 locations):

     1  2  3  4  5  6
1  [ 0  1  0  0  0  0 ]
2  [ 0  0  1  0  0  0 ]
3  [ 0  0  0  1  0  0 ]
4  [ 0  0  0  0  1  0 ]
5  [ 0  0  0  0  0  1 ]
6  [ 1  0  0  0  0  0 ]

Distance matrix D (6×6, graph-based with ω = 7):

     1  2  3  4  5  6
1  [ 0  1  7  1  7  1 ]
2  [ 1  0  1  7  1  7 ]
3  [ 7  1  0  1  7  1 ]
4  [ 1  7  1  0  1  7 ]
5  [ 7  1  7  1  0  1 ]
6  [ 1  7  1  7  1  0 ]

Optimal assignment (cost = 6):
Using Hamiltonian circuit 1 → 2 → 3 → 6 → 5 → 4 → 1, define γ(1)=1, γ(2)=2, γ(3)=3, γ(4)=6, γ(5)=5, γ(6)=4.

Verify cost: f(γ) = d_{γ(1),γ(2)} + d_{γ(2),γ(3)} + d_{γ(3),γ(4)} + d_{γ(4),γ(5)} + d_{γ(5),γ(6)} + d_{γ(6),γ(1)}
= d_{1,2} + d_{2,3} + d_{3,6} + d_{6,5} + d_{5,4} + d_{4,1} = 1 + 1 + 1 + 1 + 1 + 1 = 6 = n ✓

Suboptimal assignment (cost = 18):
Non-Hamiltonian permutation γ = (1,3,2,4,5,6):
f(γ) = d_{1,3} + d_{3,2} + d_{2,4} + d_{4,5} + d_{5,6} + d_{6,1} = 7 + 1 + 7 + 1 + 1 + 1 = 18 > 6

The pair (1,3) at consecutive locations are not graph-adjacent, contributing ω = 7 instead of 1. Similarly (2,4) contributes 7.

Solution extraction:
From the optimal γ = (1,2,3,6,5,4), read the Hamiltonian circuit: 1 → 2 → 3 → 6 → 5 → 4 → 1 ✓

Statistics:

• 6 distinct undirected Hamiltonian circuits in the prism graph
• 720 total permutations; optimal cost 6 achieved only by HC permutations
• Suboptimal costs: 18 (432 permutations, 2 non-edges at consecutive positions) and 30 (216 permutations, 4 non-edges)

References

• [Sahni and Gonzalez, 1976]: S. Sahni and T. Gonzalez (1976). "P-Complete Approximation Problems". Journal of the ACM 23(3), pp. 555–565. DOI: 10.1145/321958.321975.
• [Garfinkel and Nemhauser, 1972]: R. S. Garfinkel and G. L. Nemhauser (1972). "Integer Programming". John Wiley & Sons, New York. ISBN 978-0-471-29195-4.

[isPANN]

Issue Quality Check — Rule (Re-check)

Check	Result	Details
Usefulness	✅ Pass	No existing path HamiltonianCircuit → QuadraticAssignment
Non-trivial	✅ Pass	Constructs cost/distance matrices from graph adjacency
Correctness	❌ Fail	Wrong paper citation; reduction algorithm doesn't match Sahni-Gonzalez 1976; bound is wrong
Well-written	❌ Fail	Non-existent size field names; internal contradictions; example contains inline corrections and wrong bound

Overall: 2 passed, 0 warnings, 2 failed

---

Usefulness

Pass. No existing reduction path from HamiltonianCircuit to QuadraticAssignment in the reduction graph. This would be a novel connection. Motivation is substantive — explains QAP's significance as "hardest of the hard" and cites Sahni-Gonzalez's inapproximability result.

Non-trivial

Pass. The reduction constructs two n×n matrices (cost and distance) from the graph structure and encodes the Hamiltonian circuit constraint into the QAP objective. This involves genuine structural transformation, not mere relabeling.

Correctness

Fail. Multiple serious errors:

1. Wrong paper citation. The issue references:

   [Sahni and Gonzalez, 1976]: T. Gonzalez and S. Sahni (1976). "Open shop scheduling to minimize finish time". JACM 23, pp. 665–679.

   The actual paper is: S. Sahni and T. Gonzalez (1976). "P-Complete Approximation Problems". Journal of the ACM 23(3), pp. 555–565. DOI: 10.1145/321958.321975. The cited title and page numbers are completely wrong.

2. Reduction algorithm doesn't match the original paper. The actual Sahni-Gonzalez construction (p. 561 of the paper) is:

   • C = cycle adjacency (c_{i,j} = 1 iff j = i+1 or i=n,j=1)
   • D = graph-based with penalty (d_{k,l} = 1 if (k,l) ∈ E, ω otherwise)
   • Cost = n iff G has a Hamiltonian circuit

   The issue has C and D swapped: C = graph adjacency, D = cycle adjacency. This is a fundamentally different construction that doesn't produce the claimed results.

3. Bound B = 2n is wrong. Python brute-force validation confirms:

   • With the penalty distance matrix (M=6): optimal QAP cost for Hamiltonian circuit permutations is 48, not 12. The 72 optimal permutations correspond exactly to the 6 undirected Hamiltonian circuits (with rotations/reflections).
   • With the "corrected" 0/1 distance matrix: minimum QAP cost is 4 (not 12), achieved by 216 permutations, most of which are NOT Hamiltonian circuits. The 0/1 version is broken as a reduction.

4. Garfinkel & Nemhauser (1972) reference — Verified correct: "Integer Programming", John Wiley & Sons, ISBN 978-0471291954.

Well-written

Fail. Multiple issues:

1. Size overhead table uses non-existent field names. The table references matrix_size, num_cost_entries, num_distance_entries — none of these are registered size fields on QuadraticAssignment. The actual getter methods are num_facilities() and num_locations() (and size_fields is currently empty in the registry).

2. Internal contradictions. The algorithm (Step 2) specifies d_{kl} = M for non-adjacent positions, but the example then discovers this doesn't work and "corrects" to d_{kl} = 0. The algorithm and example are inconsistent with each other.

3. Example contains inline debugging and corrections. Instead of a clean worked example, it includes passages like:

   "wait, this would add to the cost"
   "Need to re-examine"
   "Revised: with f(4) = 6..."
   "Corrected distance matrix D (0/1 adjacency on cycle)"

   This reads as an unfinished draft, not a publishable example.

4. Decision vs optimization mismatch. The issue describes the G&J decision version (with bound B ∈ Z⁺), but the codebase QuadraticAssignment is an optimization problem (Minimize total cost). No discussion of how to bridge this gap — the reduction should construct a QAP instance and check whether the optimal cost meets a threshold, but this is not explained.

5. Symbols inconsistency. M is introduced in the algorithm but then abandoned in the "corrected" example. The overhead table uses num_vertices (from HamiltonianCircuit) as an expression variable, which is correct, but the target field names are wrong.

Example Validation (Python brute-force)

• Source graph: 6 vertices, 9 edges (prism graph) ✓
• Cost matrix C matches graph adjacency ✓
• Claimed Hamiltonian circuit 1→2→3→6→5→4→1 is valid ✓
• 6 distinct undirected Hamiltonian circuits found (12 directed)
• D_penalty (M=6): optimal QAP cost = 48 (achieved by exactly 72 permutations = all HC rotations/reflections). The penalty construction actually works as a reduction, but B should be 48 (or equivalently 2 * num_edges * 1 + 2 * (n*(n-1)/2 - num_edges) * 0 for the cycle-mapped edges), not 2n = 12.
• D_binary (0/1): optimal QAP cost = 4, achieved by 216 permutations including many non-Hamiltonian ones. This version is broken as a reduction.

Recommendations

• Rewrite the reduction algorithm to match the actual Sahni-Gonzalez construction: C = cycle adjacency, D = graph-based with penalty ω. This produces cost = n for HC instances and cost ≥ n + ω - 1 otherwise.
• Fix the reference to "P-Complete Approximation Problems", JACM 23(3):555–565.
• Clean up the example — remove inline debugging, provide a single clean worked walkthrough.
• Address the decision-vs-optimization gap — explain that the satisfaction problem (HC) reduces to the optimization problem (QAP) by checking whether the minimum cost equals n.
• Fix the overhead table to use actual getter method names from QuadraticAssignment (num_facilities, num_locations).

[isPANN]

Fix-issue changelog

• Fixed wrong paper citation: "Open shop scheduling to minimize finish time" → "P-Complete Approximation Problems", JACM 23(3):555–565, DOI:10.1145/321958.321975
• Rewrote reduction algorithm to match actual Sahni-Gonzalez (1976) construction: C = directed cycle adjacency, D = graph-based with penalty ω (previously C and D roles were swapped)
• Fixed bound: B = 2n → optimal cost = n (with optimization framing)
• Added optimization framing note: explained how the sat → opt reduction works (optimal QAP cost = n iff HC exists)
• Fixed size overhead field names: matrix_size/num_cost_entries/num_distance_entries → num_facilities/num_locations (actual getter methods)
• Rewrote example from scratch: removed inline debugging/corrections; clean worked example with prism graph (6V, 9E), verified by Python brute-force (optimal cost 6 achieved by exactly 72 HC permutations out of 720 total)
• Added suboptimal assignment to example for comparison (cost 18 vs optimal 6)

Applied by /fix-issue.