[Model] MixedChinesePostman

[isPANN]

---

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

Motivation

CHINESE POSTMAN FOR MIXED GRAPHS (P101) from Garey & Johnson, A2 ND25. A fundamental problem in combinatorial optimization on mixed graphs (graphs containing both directed arcs and undirected edges). While the Chinese Postman Problem is polynomial-time solvable on purely undirected or purely directed graphs, the mixed case is NP-complete (Papadimitriou, 1976). It is a target in the reduction from 3SAT (R46).

Associated rules:

• R46: 3SAT -> CHINESE POSTMAN FOR MIXED GRAPHS (incoming)

Definition

Name: MixedChinesePostman
Canonical name: CHINESE POSTMAN FOR MIXED GRAPHS (also: Mixed Chinese Postman Problem, MCPP)
Reference: Garey & Johnson, Computers and Intractability, A2 ND25

Mathematical definition:

INSTANCE: Mixed graph G = (V, A, E), where A is a set of directed edges (arcs) and E is a set of undirected edges on V, length l(e) ∈ Z_0+ for each e ∈ A∪E, bound B ∈ Z+.
QUESTION: Is there a closed walk in G that traverses each arc in its specified direction and each undirected edge in at least one direction, possibly traversing some arcs/edges multiple times, with total length ≤ B?

Variables

• Count: |E| binary variables — one per undirected edge, representing the chosen traversal direction.
• Per-variable domain: {0, 1} — 0 = forward direction (u → v), 1 = reverse direction (v → u), for each undirected edge {u, v}.
• Meaning: A configuration fixes the orientation of every undirected edge. Given fixed orientations, the graph becomes purely directed and the minimum-cost Chinese Postman tour on this directed graph can be computed in polynomial time (via min-cost flow to balance vertex degrees). The configuration is satisfying if this minimum directed CPP cost is ≤ B.

Dims

[2; num_edges] — one binary variable per undirected edge.

Schema (data type)

Type name: MixedChinesePostman
Variants: weight type (W)

Prerequisite type: MixedGraph — a new graph topology type representing a graph with both directed arcs and undirected edges. Stores num_vertices: usize, arcs: Vec<(usize, usize)> (directed), and edges: Vec<(usize, usize)> (undirected). Lives under src/models/graph/.

Field	Type	Description
graph	MixedGraph	The mixed graph G = (V, A, E)
arc_weights	Vec<W>	Length for each arc in A (parallel to graph.arcs)
edge_weights	Vec<W>	Length for each undirected edge in E (parallel to graph.edges)
bound	W	The total length bound B

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• MixedGraph is a new topology type (not parameterized by G). The problem struct is MixedChinesePostman<W>.
• The cycle must traverse every arc in its specified direction and every undirected edge in at least one direction, possibly traversing some arcs/edges multiple times.
• Given fixed edge orientations, the problem reduces to a directed Chinese Postman: find minimum-cost additional arc copies to make the directed graph Eulerian (balanced in-degree equals out-degree at every vertex), solvable via min-cost flow in O(V³).
• Polynomial-time solvable when A = ∅ (undirected Chinese Postman, solved by T-join/matching) or E = ∅ (directed Chinese Postman, solved by min-cost flow).

Size fields

Getter	Description
num_vertices	Number of vertices |V|
num_arcs	Number of directed arcs |A|
num_edges	Number of undirected edges |E|
bound	Total length bound B

Complexity

• Best known exact algorithm: Brute-force enumeration over all 2^|E| orientations of undirected edges. For each orientation, solve the resulting directed Chinese Postman Problem via min-cost flow in O(V³). Total: O(2^|E| · |V|³).
• Complexity expression: "2^num_edges * num_vertices^3"
• NP-completeness: NP-complete (Papadimitriou, 1976, "On the complexity of edge traversing"). Remains NP-complete even if all edge lengths are equal (unit lengths), G is planar, and the maximum vertex degree is 3.
• Special cases: Polynomial-time solvable when A = ∅ (Edmonds and Johnson, 1973) or E = ∅ (standard min-cost flow).
• Approximation: A 3/2-approximation algorithm exists for the optimization version (Frederickson, SIAM J. Discrete Math.).
• References:
  • C.H. Papadimitriou (1976). "On the complexity of edge traversing." Journal of the ACM, 23(3):544–554.
  • J. Edmonds and E.L. Johnson (1973). "Matching, Euler tours, and the Chinese postman." Mathematical Programming, 5:88–124.

Extra Remark

Full book text:

INSTANCE: Mixed graph G = (V,A,E), where A is a set of directed edges and E is a set of undirected edges on V, length l(e) ∈ Z0+ for each e ∈ A∪E, bound B ∈ Z+.
QUESTION: Is there a cycle in G that includes each directed and undirected edge at least once, traversing directed edges only in the specified direction, and that has total length no more than B?

Reference: [Papadimitriou, 1976b]. Transformation from 3SAT.
Comment: Remains NP-complete even if all edge lengths are equal, G is planar, and the maximum vertex degree is 3. Can be solved in polynomial time if either A or E is empty (i.e., if G is either a directed or an undirected graph) [Edmonds and Johnson, 1973].

How to solve

• It can be solved by (existing) bruteforce.
• It can be solved by reducing to integer programming — formulate as ILP to find minimum-cost additional edge/arc duplications making the mixed graph Eulerian.
• Other: For each of the 2^|E| orientations of undirected edges, solve the resulting directed CPP via min-cost flow. Return YES if any orientation yields total cost ≤ B.

Example Instance

Instance 1 (YES — postman tour within bound):

Mixed graph G with 5 vertices {0, 1, 2, 3, 4}:

• Arcs A (directed): (0→1, length 2), (1→2, length 3), (2→3, length 1), (3→0, length 4)
• Edges E (undirected): {0,2, length 2}, {1,3, length 3}, {0,4, length 1}, {4,2, length 2}
• Bound B = 24

Base traversal cost (sum of all arc/edge lengths): 2 + 3 + 1 + 4 + 2 + 3 + 1 + 2 = 18.

Optimal orientation: edge {0,2} as 2→0, edge {1,3} as 3→1, edge {0,4} as 0→4, edge {4,2} as 4→2.

With this orientation, the directed graph has arcs:

• Original arcs: 0→1(2), 1→2(3), 2→3(1), 3→0(4)
• Oriented edges: 2→0(2), 3→1(3), 0→4(1), 4→2(2)

Degree imbalance d(v) = out_degree − in_degree:

• d(0) = 2 − 2 = 0
• d(1) = 1 − 2 = −1 (deficit: needs 1 more outgoing)
• d(2) = 2 − 3 = −1 (deficit: needs 1 more outgoing)
• d(3) = 2 − 1 = +1 (surplus: needs 1 more incoming)
• d(4) = 1 − 1 = 0

To balance: duplicate arcs along shortest path from surplus to deficit vertices. Duplicate 1→2(3) and 2→3(1), cost = 4. This routes the surplus at vertex 3 through 1→2→3, balancing all degrees.

Total cost = 18 (base) + 4 (duplications) = 22 ≤ 24 = B. ✅

Tour (Eulerian circuit on balanced graph): 0 → 1 → 2 → 3 → 0 → 4 → 2 → 3 → 1 → 2 → 0, total length = 22.

Suboptimal feasible solutions: Two additional orientations yield cost 24 (≤ B), providing suboptimal feasible solutions. For example, orienting {0,2} as 2→0, {1,3} as 1→3, {0,4} as 0→4, {4,2} as 4→2 gives balancing cost 6, total = 24.

Answer: YES

Expected Outcome: The optimal orientation achieves cost 22 ≤ 24 = B, with duplicated arcs 1→2 and 2→3. Two suboptimal orientations also feasible at cost 24.

---

Instance 2 (NO — postman tour exceeds bound):

Mixed graph G with 6 vertices {0, 1, 2, 3, 4, 5}:

• Arcs A: (0→1, length 1), (1→0, length 1), (2→3, length 1)
• Edges E: {0,2, length 1}, {1,3, length 1}, {3,4, length 5}, {4,5, length 5}, {5,2, length 5}
• Bound B = 10

Base traversal cost: arcs = 1 + 1 + 1 = 3, edges = 1 + 1 + 5 + 5 + 5 = 17, total = 20.

Since the base cost alone (20) already exceeds B = 10, and any feasible tour must traverse every arc and edge at least once (total length ≥ 20), no tour can have total length ≤ 10.

Answer: NO

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph
Non-trivial	✅ Pass	Distinct from all existing problems (edge-traversing on mixed graphs)
Correctness	✅ Pass	Both references verified; NP-completeness claim correct
Well-written	⚠️ Warn	Several issues with naming, variables, complexity, and example quality

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

The problem does not exist in the codebase (pred show ChinesePostmanForMixedGraphs returns "Unknown problem"). It fills a gap in the reduction graph for edge-traversing problems on mixed graphs. The issue mentions an incoming reduction from 3SAT (R46 from Garey & Johnson), which would connect it to the existing graph. Pass.

Non-trivial

This is genuinely distinct from all 24 existing problems:

• vs TravelingSalesman: TSP visits vertices exactly once; MCPP traverses edges at least once. Fundamentally different constraints.
• vs graph problems (MIS, MaxCut, etc.): Those optimize over vertex/edge subsets; MCPP finds an Eulerian-like tour.
• Input structure: Mixed graphs (directed arcs + undirected edges) are not used by any existing problem.

Pass.

Correctness

References verified:

1. Papadimitriou (1976), "On the complexity of edge traversing," JACM 23(3):544–554 — Confirmed real. The paper proves NP-completeness of the mixed Chinese postman problem, matching the issue's claim. Volume, pages, and year are all correct.

2. Edmonds and Johnson (1973), "Matching, Euler tours and the Chinese postman," Mathematical Programming 5:88–124 — Confirmed real. The paper solves the undirected Chinese postman in polynomial time via matching, matching the issue's claim about the A = ∅ special case.

3. Garey & Johnson, A2 ND25 — Consistent with the known classification in Computers and Intractability.

NP-completeness claim is correct: the mixed case is NP-complete even with unit lengths, planarity, and degree ≤ 3 (Papadimitriou 1976).

Complexity section weakness: No specific exact algorithm time bound is given — just "ILP with branch-and-bound." For the declare_variants! macro, a concrete worst-case complexity expression is required. The issue should cite a specific algorithm with a time bound (e.g., a brute-force bound like 2^(num_arcs + num_edges) for enumerating edge orientations, or a better result if one exists).

Pass (references are all correct), but see recommendation below.

Well-written

4a — Information Completeness:
All template sections are present and substantive. No placeholders in required fields.

4b — Naming Convention:
The proposed name ChinesePostmanForMixedGraphs is quite long and inconsistent with the project's naming style. Compare: TravelingSalesman (not TravelingSalesmanProblem), BinPacking (not BinPackingProblem). A name like MixedChinesePostman would be more consistent and concise.

4c — Variables Section Issues:

• The variable domain is listed as {1, 2, 3, ...} (unbounded integers), but the Problem trait requires dims() to return a finite domain per variable. An unbounded domain cannot be represented in the current trait system. The issue needs to address how to encode this as a finite-domain problem (e.g., as a binary decision problem with a fixed configuration space, or by bounding the traversal multiplicity).
• The variable count |A| + |E| with per-variable domain "number of traversals" does not map cleanly to the satisfaction problem formulation. For a decision problem (Metric = bool), the configuration space should encode candidate solutions — for example, orientation choices for undirected edges (binary) plus duplication counts (bounded).

4d — Complexity Section:

• No concrete time bound is provided for declare_variants!. The complexity section says "ILP formulations with branch-and-bound" but does not give a worst-case expression like 2^num_edges or similar. This is required for implementation.

4e — Example Quality:

• Instance 1 is reasonable but very simple — it's a single alternating cycle where every edge is traversed exactly once, making the Eulerian condition trivially satisfied. A more illustrative example would require actual edge duplications to achieve an Eulerian tour.
• Instance 2 claims the minimum traversal cost is 15 (3 arcs + 4 edges at their base costs), but this ignores that additional duplications might enable a valid tour at lower total cost than the sum of base edges plus duplications. The "NO" answer reasoning is too hand-wavy — a rigorous argument is needed to show no feasible tour exists within the bound.

4f — Schema:

• The brute-force checkbox is unchecked, meaning BruteForce solver won't work directly. The dims() implementation is unclear given the unbounded variable domain issue above.

Recommendations

1. Rename to MixedChinesePostman for consistency with project naming conventions.
2. Fix the variable encoding. For a satisfaction problem, define a finite configuration space. One approach: binary variables for the orientation of each undirected edge (|E| binary variables), then check if a valid Eulerian tour of cost ≤ B exists given those orientations (the directed Chinese Postman on the resulting directed graph is polynomial). This gives dims() = [2; num_edges].
3. Add a concrete complexity bound. E.g., brute-force over orientations gives 2^num_edges * poly(num_vertices). Or cite a better bound if one exists.
4. Improve Example 1 to require edge duplications (the interesting part of the problem).
5. Strengthen Example 2 with a rigorous proof that no tour within the bound exists, or replace with a simpler verifiable NO instance.
6. Enable brute-force solving by fixing the variable encoding — this is needed for closed-loop reduction testing.

[zazabap]

Issue Quality Check — Model (Updated)

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph
Non-trivial	✅ Pass	Distinct from all existing problems (edge-traversing on mixed graphs)
Correctness	✅ Pass	Both references verified; NP-completeness claim correct
Well-written	❌ Fail	Unimplementable variable encoding; missing complexity bound; weak examples

Overall: 3 passed, 1 failed, 0 warnings

---

Usefulness

The problem does not exist in the codebase (pred show ChinesePostmanForMixedGraphs returns "Unknown problem"). It fills a gap in the reduction graph for edge-traversing problems on mixed graphs. The issue mentions an incoming reduction from 3SAT (R46 from Garey & Johnson), which would connect it to the existing graph. Pass.

Non-trivial

This is genuinely distinct from all 24 existing problems:

• vs TravelingSalesman: TSP visits vertices exactly once; MCPP traverses edges at least once. Fundamentally different constraints.
• vs graph problems (MIS, MaxCut, etc.): Those optimize over vertex/edge subsets; MCPP finds an Eulerian-like tour.
• Input structure: Mixed graphs (directed arcs + undirected edges) are not used by any existing problem.

Pass.

Correctness

References verified:

1. Papadimitriou (1976), "On the complexity of edge traversing," JACM 23(3):544–554 — Confirmed real. The paper proves NP-completeness of the mixed Chinese postman problem, matching the issue's claim. Volume, pages, and year are all correct.

2. Edmonds and Johnson (1973), "Matching, Euler tours and the Chinese postman," Mathematical Programming 5:88–124 — Confirmed real. The paper solves the undirected Chinese postman in polynomial time via matching, matching the issue's claim about the A = ∅ special case.

3. Garey & Johnson, A2 ND25 — Consistent with the known classification in Computers and Intractability.

NP-completeness claim is correct: the mixed case is NP-complete even with unit lengths, planarity, and degree ≤ 3 (Papadimitriou 1976).

Pass.

Well-written

4a — Naming Convention:
The proposed name ChinesePostmanForMixedGraphs is inconsistent with the project's naming style. Compare: TravelingSalesman (not TravelingSalesmanProblem), BinPacking (not BinPackingProblem). A name like MixedChinesePostman would be more concise and consistent.

4b — Variables Section (FAIL):
The variable domain is listed as {1, 2, 3, ...} (unbounded integers), but the Problem trait requires dims() to return a finite domain per variable. An unbounded domain cannot be represented in the current trait system. The issue does not address how to encode this as a finite-domain problem. Without a valid variable encoding, dims() and evaluate() cannot be implemented, making this issue not actionable.

A workable approach: use |E| binary variables for the orientation of each undirected edge. Given fixed orientations, the resulting directed Chinese Postman is solvable in polynomial time via min-cost flow, so evaluate() checks whether the minimum-cost tour under that orientation is ≤ B. This gives dims() = [2; num_edges].

4c — Complexity Section (FAIL):
No concrete worst-case time bound is provided. The declare_variants! macro requires a specific expression (e.g., "2^num_edges * num_vertices^3"). "ILP with branch-and-bound" is not a complexity bound. At minimum, a brute-force bound over edge orientations (2^num_edges * poly(num_vertices)) should be stated.

4d — Example Quality (FAIL):

• Instance 1 is trivially satisfiable — it forms a single alternating cycle where every element is traversed exactly once, so the Eulerian condition is automatic. A good example should require edge duplications (the core difficulty of the problem).
• Instance 2 claims "NO" with reasoning that the base cost of all edges is 15 > 10, but this ignores that the question is about a cycle covering all edges, not the sum of edge lengths. The argument needs to account for required edge duplications to achieve Eulerian balance. The reasoning is not rigorous enough to verify by hand.

4e — Brute-force Solver:
The brute-force checkbox is unchecked, but brute-force solving is critical for closed-loop reduction testing. Fixing the variable encoding (4b) would enable brute-force.

Recommendations

1. Rename to MixedChinesePostman for consistency.
2. Fix the variable encoding: Use |E| binary variables for undirected edge orientations. Then evaluate() solves a directed Chinese Postman (polynomial via min-cost flow) and checks cost ≤ B. This gives finite dims() and enables brute-force.
3. Add a concrete complexity bound: e.g., "2^num_edges * num_vertices^3" for brute-force over orientations with min-cost flow per orientation.
4. Replace Example 1 with an instance requiring edge duplications to achieve an Eulerian tour.
5. Replace or fix Example 2 with a rigorous NO-instance proof.
6. Check the brute-force box once the variable encoding is fixed.

[isPANN]

Issue Quality Check — Model (re-check)

Check	Result	Details
Usefulness	✅ Pass	Novel problem not in codebase; incoming reduction from 3SAT
Non-trivial	✅ Pass	Distinct edge-traversal on mixed graphs, unlike any existing problem
Correctness	⚠️ Warn	References correct; Example 2 has arithmetic error in reasoning
Well-written	❌ Fail	Unimplementable variable encoding; missing Dims/Size fields; no complexity bound; trivial example

Overall: 2 passed, 1 failed, 1 warning

---

Usefulness

pred show ChinesePostmanForMixedGraphs → "Unknown problem." Novel problem filling a gap in edge-traversal problems. Incoming reduction from 3SAT (R46 per Garey & Johnson) connects it to the existing graph. Pass.

Non-trivial

Genuinely distinct from all existing problems:

• vs TravelingSalesman: TSP visits vertices exactly once; MCPP traverses edges at least once
• vs graph problems (MIS, MaxCut, etc.): vertex/edge selection vs Eulerian tour
• Input structure: mixed graphs (directed arcs + undirected edges) not used by any existing problem

Pass.

Correctness

References verified (3/3):

1. Papadimitriou (1976), "On the complexity of edge traversing," JACM 23(3):544–554 — Confirmed. NP-completeness of mixed CPP verified. Hardness under unit lengths, planarity, degree ≤ 3 also confirmed.
2. Edmonds & Johnson (1973), "Matching, Euler tours and the Chinese postman," Math. Prog. 5:88–124 — Confirmed. Polynomial-time solution for undirected CPP via matching verified.
3. Garey & Johnson, A2 ND25 — Consistent with secondary sources (HandWiki, Wikipedia).

Example arithmetic error: Instance 2 claims "base cost = 3 + 12 = 15" but actual edge lengths sum to 1+1+5+5+5 = 17, giving base cost = 3 + 17 = 20. The NO answer is still correct (min tour cost = 22 > 10), but the reasoning contains a factual error.

Recommendation: A 3/2-approximation algorithm exists (Frederickson, SIAM J. Discrete Math.). No dedicated exact algorithm with explicit time bound exists beyond ILP — brute force over edge orientations gives O(2^|E| · poly(|V|)).

Pass (references correct), Warn (example reasoning error).

Well-written

4a — Missing required sections:

• Dims: Not present. Required for Problem::dims() implementation.
• Size fields: Not present. Required for overhead expressions and declare_variants!.

4b — Variable encoding (FAIL):
Variable domain is {1, 2, 3, ...} (unbounded). The Problem trait requires dims() to return finite domains. This makes the issue unimplementable as written.

Workable approach: |E| binary variables for undirected edge orientations. Given fixed orientations, the directed CPP is polynomial (min-cost flow), so evaluate() solves directed CPP per orientation and checks cost ≤ B. This gives dims() = [2; num_edges].

4c — Complexity (FAIL):
No concrete time bound for declare_variants!. "ILP with branch-and-bound" is not a complexity expression. At minimum: "2^num_edges * num_vertices^3" (brute-force over orientations with min-cost flow per orientation).

4d — Example quality (FAIL):

• Instance 1 is trivially Eulerian — the graph with correct edge orientations needs zero duplications. Only 1 feasible orientation exists (out of 8). Zero suboptimal feasible solutions. A good example should require edge duplications.
• Instance 2 has correct NO answer but wrong arithmetic: claims edge sum = 12, actual = 17.

4e — Naming:
ChinesePostmanForMixedGraphs is verbose. Project convention prefers concise names: MixedChinesePostman would be more consistent (cf. TravelingSalesman, BinPacking).

Recommendations

1. Rename to MixedChinesePostman
2. Add Dims section: [2; num_edges] (binary orientation per undirected edge)
3. Add Size fields section: num_vertices, num_arcs, num_edges, bound
4. Fix variable encoding: binary orientation variables, polynomial evaluate() via directed CPP
5. Add complexity bound: "2^num_edges * num_vertices^3"
6. Replace Example 1 with an instance requiring edge duplications (non-trivial Eulerian balancing)
7. Fix Example 2 arithmetic: edge sum = 17, not 12
8. Check brute-force box once encoding is fixed