[Rule] HAMILTONIAN CIRCUIT to RURAL POSTMAN

[isPANN]

---

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

Source: HAMILTONIAN CIRCUIT
Target: RURAL POSTMAN
Motivation: Establishes NP-completeness of RURAL POSTMAN via polynomial-time reduction from HAMILTONIAN CIRCUIT. The Rural Postman problem is a fundamental arc-routing problem generalizing both the Chinese Postman Problem (polynomial when E' = E) and the Traveling Salesman Problem (when E' = ∅ with required vertices). This reduction shows that selecting which edges to traverse — even with unit lengths — is inherently intractable.

Reference: Garey & Johnson, Computers and Intractability, ND27, p.213

GJ Source Entry

[ND27] RURAL POSTMAN
INSTANCE: Graph G=(V,E), length l(e)∈Z_0^+ for each e∈E, subset E'⊆E, bound B∈Z^+.
QUESTION: Is there a circuit in G that includes each edge in E' and that has total length no more than B?
Reference: [Lenstra and Rinnooy Kan, 1976]. Transformation from HAMILTONIAN CIRCUIT.
Comment: Remains NP-complete even if l(e)=1 for all e∈E, as does the corresponding problem for directed graphs.

Reduction Algorithm

Summary:
Given a HamiltonianCircuit instance G = (V, E) with n = |V| vertices and m = |E| edges, construct a Rural Postman instance (G', E'_req, l, B) as follows:

1. Vertex splitting: For each vertex v_i ∈ V (i = 0, ..., n−1), create two vertices v_i^a and v_i^b. Set V' = {v_i^a, v_i^b : v_i ∈ V}, so |V'| = 2n.

2. Required edges (vertex-representing): For each vertex v_i ∈ V, add an edge {v_i^a, v_i^b} with length 1. These form the required edge set: E'_req = {{v_i^a, v_i^b} : v_i ∈ V}, so |E'_req| = n. Each required edge enforces that the corresponding original vertex must be "visited."

3. Connectivity edges (edge-representing): For each edge {v_i, v_j} ∈ E, add edges {v_i^b, v_j^a} and {v_j^b, v_i^a}, each with length 0. These optional routing edges allow the circuit to move between vertex gadgets. Total: 2m connectivity edges.

4. Overall graph: G' = (V', E') where E' = E'_req ∪ E'_conn, |E'| = n + 2m.

5. Bound: Set B = n.

Correctness:

• (HC → RPP): If G has a Hamiltonian circuit v_{π(0)} → v_{π(1)} → ... → v_{π(n−1)} → v_{π(0)}, construct a Rural Postman circuit in G': v_{π(0)}^a → v_{π(0)}^b → v_{π(1)}^a → v_{π(1)}^b → ... → v_{π(n−1)}^a → v_{π(n−1)}^b → v_{π(0)}^a. This circuit traverses all n required edges (cost 1 each) and n zero-cost connectivity edges, for total length n = B.

• (RPP → HC): If G' has a circuit including all required edges with total length ≤ B = n, it traverses at least n required edges (cost n). Since the budget is exactly n, the circuit uses no additional cost-1 edges (i.e., each required edge is traversed exactly once). Between consecutive required edges, only zero-cost connectivity edges are used. The sequence of vertex-gadgets visited, in order, gives a Hamiltonian circuit in G: each vertex is visited exactly once, and consecutive vertices correspond to edges in the original graph.

Vertex count: 2n
Edge count: n + 2m

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	2 * num_vertices
num_edges	num_vertices + 2 * num_edges
num_required_edges	num_vertices

Derivation:

• Vertices: each of the n original vertices is split into two → 2n
• Edges: n required edges (one per vertex gadget) + 2m connectivity edges (two per original edge) → n + 2m
• Required edges: one per original vertex → n

Validation Method

• Closed-loop test: reduce a small HamiltonianCircuit instance G to Rural Postman (G', E'_req, l, B), solve G' with BruteForce, then verify that a feasible Rural Postman circuit (cost ≤ B covering all required edges) exists if and only if G has a Hamiltonian circuit.
• Test with a graph known to have a Hamiltonian circuit (e.g., cycle C_6) and verify the RPP instance has a feasible solution with cost B = 6.
• Test with a graph known to have no Hamiltonian circuit (e.g., K_{1,5} with some extra edges but no HC) and verify no RPP solution of cost ≤ B exists.
• Verify vertex and edge counts: |V'| = 2n, |E'| = n + 2m, |E'_req| = n.
• Verify that each required edge is traversed exactly once in any optimal solution (no budget for repeats).

Example

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

• Edges: {0,1}, {1,2}, {2,0}, {3,4}, {4,5}, {5,3}, {0,3}, {1,4}, {2,5}
• n = 6, m = 9
• Hamiltonian circuit exists: 0 → 1 → 4 → 3 → 5 → 2 → 0

Constructed target instance (Rural Postman):
Graph G' = (V', E'):

• V' = {0^a, 0^b, 1^a, 1^b, 2^a, 2^b, 3^a, 3^b, 4^a, 4^b, 5^a, 5^b} — 12 vertices
• Required edges E'_req (length 1 each):
  • {0^a, 0^b}, {1^a, 1^b}, {2^a, 2^b}, {3^a, 3^b}, {4^a, 4^b}, {5^a, 5^b} — 6 edges
• Connectivity edges (length 0 each):
  • From {0,1}: {0^b, 1^a}, {1^b, 0^a}
  • From {1,2}: {1^b, 2^a}, {2^b, 1^a}
  • From {2,0}: {2^b, 0^a}, {0^b, 2^a}
  • From {3,4}: {3^b, 4^a}, {4^b, 3^a}
  • From {4,5}: {4^b, 5^a}, {5^b, 4^a}
  • From {5,3}: {5^b, 3^a}, {3^b, 5^a}
  • From {0,3}: {0^b, 3^a}, {3^b, 0^a}
  • From {1,4}: {1^b, 4^a}, {4^b, 1^a}
  • From {2,5}: {2^b, 5^a}, {5^b, 2^a}
    — 18 connectivity edges
• Total: 6 + 18 = 24 edges
• B = 6

Solution mapping (Hamiltonian circuit 0→1→4→3→5→2→0):
Rural Postman circuit:
0^a →(required, cost 1)→ 0^b →(conn, cost 0)→ 1^a →(required, cost 1)→ 1^b →(conn, cost 0)→ 4^a →(required, cost 1)→ 4^b →(conn, cost 0)→ 3^a →(required, cost 1)→ 3^b →(conn, cost 0)→ 5^a →(required, cost 1)→ 5^b →(conn, cost 0)→ 2^a →(required, cost 1)→ 2^b →(conn, cost 0)→ 0^a

• Total cost: 6 × 1 (required) + 6 × 0 (connectivity) = 6 = B ✓
• All 6 required edges traversed ✓
• All 12 vertices visited ✓

References

• [Lenstra and Rinnooy Kan, 1976]: [Lenstra1976] Jan K. Lenstra and A. H. G. Rinnooy Kan (1976). "On general routing problems". Networks 6, pp. 273–280.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	Both source and target are new problems not in the codebase; novel reduction
Non-trivial	✅ Pass	Vertex-splitting gadget with required/optional edge separation
Correctness	✅ Pass	Reference verified; reduction algorithm is sound
Well-written	⚠️ Warn	Minor issues with target metric and symbol usage

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

Neither HamiltonianCircuit nor RuralPostman exist in the current codebase (24 problem types implemented). This reduction would add two new problem nodes and a novel edge to the reduction graph. The motivation is well-articulated: it establishes NP-completeness of Rural Postman via polynomial-time reduction from Hamiltonian Circuit, and correctly notes that RPP generalizes both the Chinese Postman Problem and TSP.

No existing path between these problems exists (neither problem is implemented), so this is a novel reduction. Pass.

Non-trivial

The reduction involves a genuine structural transformation — a vertex-splitting gadget that creates two vertices per original vertex with a required edge between them, plus zero-cost connectivity edges encoding the original graph structure. This is not a variable substitution, subtype coercion, or identity reduction. The construction creates new graph structure (2n vertices, n required edges, 2m connectivity edges) from an n-vertex, m-edge input. Pass.

Correctness

Reference verification:

• Garey & Johnson, ND27, p.213: This is a well-known reference — Computers and Intractability (1979). The book's entry for ND27 (Rural Postman) correctly states: "Transformation from HAMILTONIAN CIRCUIT" with reference to Lenstra and Rinnooy Kan (1976). This matches the issue's claims. The book is already in the project bibliography (garey1979 in references.bib).

• Lenstra and Rinnooy Kan (1976): Verified via Wiley Online Library — "On general routing problems," Networks 6, pp. 273–280 (1976). The paper exists with matching title, authors, year, and venue. This paper established the NP-completeness of the Rural Postman Problem.

Reduction algorithm analysis:

The proposed vertex-splitting construction is sound:

• Forward direction (HC -> RPP): A Hamiltonian circuit on G maps to a Rural Postman circuit of cost exactly n by alternating required edges (cost 1) and connectivity edges (cost 0). All n required edges are traversed.
• Backward direction (RPP -> HC): With B = n and n required edges each costing 1, the budget is exactly exhausted by required edges. Each required edge is traversed exactly once (a second traversal would exceed the budget). The connectivity edges used between required edges correspond to edges in the original graph, and visiting all n vertex gadgets exactly once yields a Hamiltonian circuit.

The overhead expressions are consistent with the construction: 2n vertices, n + 2m edges, n required edges. Pass.

Note: The issue references the reduction described in Garey & Johnson but presents its own vertex-splitting construction rather than reproducing the original Lenstra-Rinnooy Kan construction verbatim. The construction appears to be a valid independent formulation of the reduction.

Well-written

4a — Information Completeness: All required sections are present and substantive (Source, Target, Motivation, Reference, Reduction Algorithm, Size Overhead, Validation Method, Example). OK.

4b — Algorithm Completeness: The reduction algorithm is detailed, step-by-step, and implementable. The correctness argument covers both directions. OK.

4c — Symbol and Notation Consistency:

• Symbols are mostly well-defined: n = |V|, m = |E|, V', E'_req, E'_conn are all defined before use.
• The overhead table uses num_vertices and num_edges which are standard getter names, but also lists num_required_edges — this is a field that would need to exist on the target RuralPostman type. Since RuralPostman does not yet exist, this cannot be verified against actual getter methods. Minor concern — ensure the model implementation uses this exact field name.
• The GJ Source Entry section defines the bound as B in Z^+ (positive integers), but the algorithm uses length-0 edges. The GJ entry says l(e) in Z_0^+ (non-negative integers), so length 0 is valid — but this is worth noting since the GJ comment says "remains NP-complete even if l(e)=1 for all e in E," which suggests a simpler construction might exist with all unit lengths.

4d — Example Quality: The example uses a triangular prism (6 vertices, 9 edges) which is non-trivial and small enough to verify by hand. The worked solution traces the full Rural Postman circuit with costs. The vertex/edge counts check out: 12 vertices, 24 edges (6 required + 18 connectivity), B = 6. Good.

Warn — overall well-written with only minor notation concerns.

Recommendations

• Both HamiltonianCircuit and RuralPostman need to be implemented as models before this rule can be added. Consider filing [Model] issues for both.
• The GJ entry notes that RPP "remains NP-complete even if l(e)=1 for all e in E." This suggests an alternative, potentially simpler reduction where all edges have unit length (avoiding length-0 edges). The current construction with zero-length edges is valid but the alternative might be worth exploring for implementation simplicity.
• The num_required_edges metric name should be confirmed once the RuralPostman model is designed.