[Model] RuralPostman

[isPANN]

---

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

Motivation

RURAL POSTMAN (P103) from Garey & Johnson, A2 ND27. A fundamental NP-complete arc-routing problem that generalizes the Chinese Postman Problem (polynomial when all edges are required) and is closely related to the Traveling Salesman Problem. It models the practical scenario of a delivery agent who must traverse a specified subset of roads in a network while minimizing total travel distance. The problem is a target of the following reduction:

• R48: HAMILTONIAN CIRCUIT → RURAL POSTMAN (ND27, Lenstra and Rinnooy Kan, 1976)

Definition

Name: RuralPostman

Canonical name: RURAL POSTMAN (also: Rural Postman Problem, RPP)
Reference: Garey & Johnson, Computers and Intractability, A2 ND27

Mathematical definition:

INSTANCE: Graph G = (V,E), length l(e) ∈ ℤ⁺₀ (non-negative integers) for each e ∈ E, subset E' ⊆ E, bound B ∈ ℤ⁺ (positive integer).
QUESTION: Is there a circuit in G that includes each edge in E' and that has total length no more than B?

Variables

• Count: |E| variables (one per edge in E), encoding the traversal count for each edge.
• Per-variable domain: For required edges (e ∈ E'): {1, 2, ..., K} where K is an upper bound on traversal count. For non-required edges (e ∈ E \ E'): {0, 1, ..., K}. In practice, K can be bounded by 2|E| since no optimal circuit needs to traverse any edge more than 2|E| times.
• Meaning: Variable x_e represents the number of times edge e is traversed in the circuit. A valid assignment satisfies: (1) x_e ≥ 1 for all e ∈ E', (2) the edges with x_e > 0 form a connected Eulerian multigraph (every vertex has even degree), and (3) the total cost Σ_e x_e · l(e) ≤ B.

Schema (data type)

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

Field	Type	Description
graph	G	The undirected graph G = (V, E)
edge_lengths	Vec<W>	Length l(e) for each edge e ∈ E (indexed by edge index, non-negative)
required_edges	Vec<usize>	Edge indices of the subset E' ⊆ E of required edges
bound	i32	Upper bound B on total circuit length

Getter methods: num_vertices(), num_edges(), num_required_edges() (used in declare_variants! complexity strings and #[reduction(overhead)] expressions).

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• When E' = E, the problem reduces to the Chinese Postman Problem (polynomial-time solvable via T-join / matching).
• When E' = ∅ and required vertices are specified instead, the problem reduces to the Traveling Salesman Problem.
• Remains NP-complete with unit edge lengths (l(e) = 1 for all e).
• The directed variant is also NP-complete (GJ comment).

Complexity

• Best known exact algorithm: Dynamic programming over subsets of required edges: O(n² · 2^r) where n = |V| is the number of vertices and r = |E'| is the number of required edges. This is an adaptation of the Held-Karp algorithm (Held and Karp, 1962) to the required-edge setting: the DP state tracks (current vertex, subset of required edges covered so far), with transitions via precomputed all-pairs shortest paths between required-edge endpoints (computed in O(n³) via Floyd-Warshall). The DP iterates over 2^r subsets with O(n) transitions per state. When r = |E| (Chinese Postman), the problem is polynomial. For general r, the problem is strongly NP-hard.
• declare_variants! complexity string: "num_vertices ^ 2 * 2 ^ num_required_edges" (Held-Karp adaptation)
• NP-completeness: NP-complete (Lenstra and Rinnooy Kan, 1976; originally in "On general routing problems").
• Approximation: The RPP admits a 3/2-approximation using a Christofides-type heuristic for metric instances (Frederickson, 1979).
• References:
  • M. Held and R. M. Karp (1962). "A dynamic programming approach to sequencing problems." Journal of SIAM 10(1):196–210.
  • J. K. Lenstra and A. H. G. Rinnooy Kan (1976). "On general routing problems." Networks 6:273–280.
  • G. N. Frederickson (1979). "Approximation algorithms for some postman problems." Journal of the ACM 26(3):538–554.
  • A. Corberán and G. Laporte (eds.) (2015). Arc Routing: Problems, Methods, and Applications. SIAM MOS-SIAM Series on Optimization.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), length l(e) ∈ Z_0^+ (non-negative integers) for each e ∈ E, subset E' ⊆ E, bound B ∈ Z^+ (positive integer).
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.

How to solve

• It can be solved by (existing) bruteforce — enumerate all possible closed walks covering the required edges and check feasibility + total length.
• It can be solved by reducing to integer programming — standard ILP formulation with integer edge-traversal variables and Eulerian constraints.
• Other: DP over subsets of required edges in O(n² · 2^r) time (Held-Karp adaptation); branch-and-cut algorithms (Corberán et al., 2003); 3/2-approximation for metric instances (Frederickson, 1979).

Example Instance

Instance 1 (has feasible circuit):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 8 edges:

• Edges with lengths: {0,1}:1, {1,2}:1, {2,3}:1, {3,4}:1, {4,5}:1, {5,0}:1, {0,3}:2, {1,4}:2
• Required edges E' = {{0,1}, {2,3}, {4,5}} (3 required edges)
• B = 6
• Feasible circuit: 0 →{0,1}:1→ 1 →{1,2}:1→ 2 →{2,3}:1→ 3 →{3,4}:1→ 4 →{4,5}:1→ 5 →{5,0}:1→ 0
• Total length: 6 × 1 = 6 = B ✓
• All 3 required edges traversed ✓
• Answer: YES
• Exhaustive enumeration: search space 3⁸ = 6,561. Exactly 1 feasible circuit (the hexagon cycle). (Used in find_all_satisfying test)

Instance 2 (no feasible circuit with given bound):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 7 edges:

• Edges with lengths: {0,1}:1, {1,2}:1, {2,3}:1, {3,0}:1, {3,4}:3, {4,5}:1, {5,3}:3
• Required edges E' = {{0,1}, {4,5}} (2 required edges)
• B = 4
• To traverse both {0,1} and {4,5}, the circuit must travel from the {0,1,2,3} component to vertex 4 and back. The shortest path from any endpoint of {0,1} to vertex 4 goes through vertex 3 via edge {3,4} of length 3. Minimum circuit cost: 1 (for {0,1}) + path to 4 (length ≥ 3) + 1 (for {4,5}) + path back (length ≥ 3) = 8 > 4 = B.
• Answer: NO
• Exhaustive enumeration: search space 3⁷ = 2,187. 0 feasible circuits. (Used in find_all_satisfying empty test)

Instance 3 (Chinese Postman special case, E' = E):
Graph G with 4 vertices {0, 1, 2, 3} and 4 edges (cycle C_4):

• Edges with lengths: {0,1}:1, {1,2}:1, {2,3}:1, {3,0}:1
• Required edges E' = {{0,1}, {1,2}, {2,3}, {3,0}} (all edges required)
• B = 4
• Circuit: 0 → 1 → 2 → 3 → 0, total length 4 = B ✓
• This is the Chinese Postman special case: an Eulerian circuit exists since all vertices have even degree.
• Answer: YES

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in the reduction graph; concrete reduction from Hamiltonian Circuit planned
Non-trivial	✅ Pass	Distinct feasibility constraints from TravelingSalesman and other existing problems
Correctness	⚠️ Warn	DP complexity O(n² · 2^r) and parameterized O(4^d · n³) not independently verified; main references confirmed
Well-written	⚠️ Warn	Several minor issues: naming convention, schema design, variable section clarity

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. The problem RuralPostman does not exist in the codebase (pred show RuralPostman fails). It is a classic NP-complete arc-routing problem (Garey & Johnson ND27) that generalizes the Chinese Postman Problem and is structurally distinct from the existing TravelingSalesman. The issue identifies a planned reduction from Hamiltonian Circuit, which would connect it to the reduction graph. The motivation is clear: it models practical delivery/routing scenarios and occupies a well-studied position in the NP-completeness landscape.

Non-trivial

Pass. The Rural Postman Problem has genuinely different feasibility constraints from all 24 existing problems. While TravelingSalesman requires visiting every vertex exactly once (Hamiltonian cycle), Rural Postman requires traversing a subset of edges at least once (closed walk covering E'). The solution structure is fundamentally different: TSP solutions are permutations of vertices, while RPP solutions are sequences of edge traversals that may revisit vertices and edges. This is not a variant of any existing problem.

Correctness

Warn. Partial verification of claims:

• Lenstra and Rinnooy Kan (1976), "On general routing problems," Networks 6:273–280 — ✅ Verified. Paper exists at Wiley Online Library. Correct authors, year, journal, and page range. This paper established NP-completeness of RPP via reduction from Hamiltonian Circuit.

• Corberán and Laporte (2015), Arc Routing: Problems, Methods, and Applications, SIAM — ✅ Verified. Book exists at SIAM Publications. Correct authors, year, and publisher.

• Sorge, van Bevern, Niedermeier, Weller (2012), "A new view on Rural Postman based on Eulerian Extension and Matching," Journal of Discrete Algorithms 16:12–33 — ✅ Verified. Paper exists at ScienceDirect. However, the issue claims "O(4^d · n³) time where d = |W*| − |R| is the number of deadheading edges." The paper's main result is parameterization by the number of weakly connected components in the required-edge subgraph, not by deadheading edges. The specific O(4^d · n³) bound attributed to this paper could not be confirmed — this may be from a different paper or a misattribution.

• DP complexity O(n² · 2^r) — ⚠️ Not independently verified. While a DP over subsets of required edges is a natural approach (analogous to Held-Karp for TSP), the specific O(n² · 2^r) bound is not attributed to any specific paper in the issue. A citation for this claim would strengthen the issue.

• 3/2-approximation — ⚠️ The claim of a 3/2-approximation "using Christofides-type approaches for metric instances" is plausible but no specific citation is provided.

Well-written

Warn. The issue is generally thorough with multiple well-worked examples and clear mathematical definition. However, several items need attention:

4a: Information Completeness — All required sections are present and substantive. Good.

4b: Definition Completeness — The formal definition is clear and matches Garey & Johnson's formulation. The decision problem formulation with bound B is appropriate for a satisfaction problem. Good.

4c: Symbol and Notation Consistency:

• The issue uses Z_0^+ which should be clarified as non-negative integers (it could mean positive integers excluding zero in some conventions).
• The Variables section is confusingly written. It mixes two different formulations (sequence-based vs DP-based) without clearly separating them. The "Count" and "Per-variable domain" fields should describe the actual implementation variables (binary assignment), not the abstract solution structure.

4d: Naming Convention:

• The proposed name RuralPostman does not follow the project's naming conventions. Per CLAUDE.md, satisfaction problems use no prefix, which is fine. However, if this is modeled as an optimization problem (minimize total circuit length), the name should be MinimumRuralPostman or similar. The issue says Metric = bool (satisfaction), which is consistent with the decision-problem formulation, but many practical uses want the optimization version. The issue should clarify this choice.

4e: Schema Design Issues:

• required_edges as Vec<(usize, usize)> — should these be edge indices into the graph's edge list instead of vertex pairs? Using vertex pairs requires validation that each pair is actually an edge in the graph.
• edge_lengths as Vec<i32> — the definition says l(e) ∈ Z_0^+ (non-negative), but i32 allows negative values. Consider using u32 or adding a note about non-negativity enforcement.
• The bound field as i32 is fine for a satisfaction problem, but again allows negative values.

4f: Example Quality — Good. Three examples are provided covering: a feasible instance, an infeasible instance, and the Chinese Postman special case. The examples are small enough to verify by hand and the worked solutions are detailed. Instance 2 has a clear explanation of why no feasible circuit exists.

Recommendations

• Add a specific citation for the O(n² · 2^r) DP algorithm (possibly Held-Karp adaptation or Frederickson 1979).
• Verify the O(4^d · n³) attribution to Sorge et al. 2012 — this specific bound may come from a different paper in the series.
• Clarify the Variables section to describe the actual binary variable encoding for implementation.
• Consider whether required_edges should store edge indices rather than vertex pairs for consistency with graph representation.