Mixed Chinese Postman Problem¶
Find a least-cost closed walk covering every link of a weighted graph with undirected edges and directed arcs.
Core Idea¶
The mixed Chinese postman problem (MCPP) asks for a minimum-weight closed walk that traverses every required link of a mixed graph at least once. A mixed graph has undirected edges, which can be traversed either way, and directed arcs, which must be traversed in their assigned direction. The walk may repeat links when needed to return to its starting point and cover the whole network. The cost of those repetitions counts in the objective.[1][2]
The characteristic difficulty lies in choosing traversals of flexible undirected edges while respecting fixed arc directions and maintaining a closed route. A mixed-graph formulation can include purely directed or purely undirected special cases, but those do not exhibit the full interaction. Under standard nonnegative-weight formulations, the pure forms have polynomial-time solution methods; the standard decision version of the genuinely mixed problem is NP-complete, while its optimization form is NP-hard.[1][2] Computational difficulty is a result about the problem, not its definition.
Structural Signature¶
Sig role-phrases:
- Weighted mixed-graph input — Vertices are joined by direction-constrained arcs and direction-flexible edges, each with a nonnegative traversal weight. A particular input may degenerate to a pure special case.
- Complete link coverage — Every listed arc and edge must be traversed at least once. Visiting every vertex is insufficient.
- Direction-respecting closed walk — The route returns to its start, follows each arc forward, and may repeat links. An open service route is a different variant.
- Minimum total weight — Among feasible coverage walks, choose the one with least sum of traversed-link weights, counting repeats.
- Feasibility precondition — Standard formulations assume a strongly connected mixed graph with arc directions respected; otherwise some required links may not be coverable by one closed walk.[2]
What It Is Not¶
- Not a traveling-salesperson problem. A vertex-visiting tour can omit edges; MCPP requires servicing every link.
- Not a route itself. One route is a candidate solution to an instance; the abstraction is the reusable input, feasibility and objective specification.
- Not an algorithm. Integer programming, heuristics and approximations are possible methods for solving or estimating solutions, not the identity of the problem.[1]
- Not made “mixed” by cost heterogeneity alone. The distinguishing input has directional arcs and undirected edges; different weights on one link type do not create the mixed traversal rule.
Scope of Application¶
The formal problem models arc routing when service is required along links rather than solely at locations. One-way and two-way street segments can be represented as arcs and undirected edges for a postal, sweeping or refuse-collection route, after checking that the graph model captures real turns, closures, depot assumptions and service requirements. Ralphs uses postal and trash-hauling contexts to motivate the general Chinese postman family.[1] The model also applies to abstract networks with the same mixed direction and coverage constraints; an actual municipal route is not necessary for the identity.
Clarity¶
Three distinctions prevent conflation. First, “cover” means traverse every edge and arc, not merely reach each vertex. Second, an undirected edge offers an orientation choice in a tour, whereas a directed arc cannot be reversed. Third, a feasible route and an optimal route are different claims: a closed walk may service every link and still contain avoidable repeats. Strong connectivity is a feasibility assumption, not a guarantee that the shortest tour is easy to find.[2]
Manages Complexity¶
A street map or abstract network has many possible route sequences. MCPP compresses the task into an explicit graph input, a coverage condition, a closed-walk constraint and one cost criterion. That reduction exposes what can be delegated to a solver and what remains a modeling decision. A link omitted from the required set, a one-way street coded as two-way, or a turn restriction omitted from the graph can invalidate an apparently optimal route without changing the mathematics of the solved instance.
Abstract Reasoning¶
For a candidate route, first verify that every required link appears and every directed arc is followed correctly. Verify closure next; only then compare total weights, including repeats. An undirected edge's chosen traversal direction can affect how the walk returns to earlier vertices, so locally cheap choices need not minimize the whole tour. A lower bound is the sum of weights of all required links; if a feasible closed walk uses every unit-weight required link exactly once, it reaches that bound and is optimal for that instance. The same reasoning does not imply that all mixed instances have Eulerian tours.[1]
Knowledge Transfer¶
The formal specification transfers between different arc-service applications by mapping real segments to edges or arcs, preserving directional legality, declaring which links need service and defining traversal cost. A change from snow removal to refuse collection may change vehicle constraints or which segments are required while leaving the core arc-routing question recognizable. The broader feasible-set-plus-objective skeleton belongs to Optimization Problem; MCPP's mixed graph and link-coverage demands do not turn into a cross-domain prime merely because graph models are widely useful.
Examples¶
Three-vertex mixed cycle¶
Take vertices A, B and C, a unit-cost arc A→B, and unit-cost undirected edges B—C and C—A. The closed walk A→B→C→A covers all three links while respecting the arc's direction. Its cost is three, equal to the sum of the three required unit costs, so no cheaper feasible walk exists. This is a constructed mathematical instance, not a claim about a documented street network.
Mapped back: Weighted mixed graph → one arc and two edges; complete link coverage → all three used; closed walk → return from C to A; direction rule → A→B never reversed; objective → cost three meets the obvious lower bound.
One-way and two-way street-service model¶
In a modeled district, encode one-way street segments as directed arcs and serviceable two-way streets as undirected edges. A sweeper's depot-returning route must cover each required segment; repeated travel contributes cost. Before applying MCPP, check whether turning restrictions, depot access and travel costs have been modeled faithfully. This is an application schema, not an observed optimized route.[1]
Mapped back: Weighted mixed graph → street network with one-way and two-way links; complete coverage → service each required segment; closed walk → depot return; direction rule → respect one-way streets; objective → minimize modeled distance or another declared travel cost.
Structural Tensions¶
- Required service versus extra travel. Every link must be traversed, but the cheapest closed route may need repeats to connect the service traversals. Omitting a link saves cost by making the answer invalid; accepting unnecessary repeats makes it suboptimal. Diagnostic: Which repeat traversals are necessary to achieve one legal closed walk?[1]
- Direction constraints versus orientation flexibility. Arcs fix one direction, while each undirected edge can be used either way. Choosing its locally convenient direction may force costly later returns. Diagnostic: Does the selected orientation permit a low-cost balanced closed traversal of the whole network?[1]
Structural–Framed Character¶
MCPP is strongly structural as a formal graph problem: graph, permitted traversals, required coverage and objective determine whether a proposed tour is feasible or optimal. Its evaluative weight is limited to a declared cost criterion; “best” does not mean safest or fairest outside the model. Its human-practice dependence appears when roads, service obligations and costs are encoded, while the mathematical relation can be studied without a real city. Its institutional origin in operations research names a problem family rather than legislating road directions. Its vocabulary travels between abstract graphs and street-service models when the same arc/edge and coverage roles are present. Import versus recognition therefore requires a role-preserving graph mapping, not just a route that looks postal.
The portable skeleton is the live Optimization Problem genus: feasible alternatives under an objective. The mixed graph and all-link closed-tour condition are narrower. Its character: a reusable, mathematically precise routing abstraction whose broad modeling utility does not erase its graph-theoretic domain boundary.
Structural Core vs. Domain Accent¶
Skeletal relation. A set of feasible alternatives is ranked by total cost and an optimum is sought. This is exactly the role supplied by Optimization Problem, the strict parent.
Domain-bound conditions. The alternatives are direction-respecting closed walks of a mixed graph; every edge and arc must be covered, and repeat traversals affect cost. Whether the links stand for roads, inspection lines or purely formal edges is an accent. Remove link coverage or arc directionality and the named mixed postman identity changes.
Prime bar. Optimization transfers across many substrates, but MCPP does not literally describe arbitrary resource allocation or every vehicle-routing problem. Its cross-application power comes from the graph model in settings that preserve its roles. The prime-level reach belongs higher in the DAG, not to the mixed postman child.
Instantiates / Related Primes¶
This entry is a kind of Optimization Problem.
The strict parent Optimization Problem supplies decision alternatives, feasibility and an objective. The live prime Optimization is a broader relation but need not be added as a direct edge when the specific problem-type parent is available. The live Routing entry concerns communication-network forwarding and is only lexically/topically adjacent; it does not subsume closed traversal of required physical or abstract links.
Relationships to Other Abstractions¶
Current abstraction Mixed Chinese Postman Problem Domain-specific
Parents (1) — more general patterns this builds on
-
Mixed Chinese Postman Problem is a kind of Optimization Problem Domain-specific
The mixed Chinese postman problem has a feasible set of closed coverage walks and a minimum traversal-cost objective.Each graph instance specifies permitted direction-respecting closed walks that cover all required arcs and edges. Their total weights are ordered and the minimum is sought. These instantiate Optimization Problem's feasible-set and objective structure, while the mixed arc/edge input and required-link coverage distinguish this specific graph-optimization child.
Hierarchy path (1) — routes to 1 parentless root
- Mixed Chinese Postman Problem → Optimization Problem → Optimization
Neighborhood in Abstraction Space¶
Mixed Chinese Postman Problem sits in a sparse region of the domain-specific corpus (76th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Graph Structures & Combinatorial Objects (44 abstractions)
Nearest neighbors
- Edge Covering Number — 0.85
- Comparability Graph — 0.83
- A-star algorithm — 0.83
- Geodetic Graph — 0.83
- Graph Embedding — 0.83
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
In a pure undirected Chinese postman instance, all links can be traversed either direction; in a pure directed instance, all are arcs. Both are special cases of a mixed-graph formulation but lack the interaction of both link types. A traveling-salesperson tour visits selected vertices rather than every required link. A rural postman variant requires only a subset of links.[3] None should be merged into MCPP merely because each asks for a short tour.
References¶
[1] T. K. Ralphs, “On the Mixed Chinese Postman Problem”, original research paper, 8 June 1993, PDF pp. 1–2 directly checked for problem statement, graph definitions and complexity comparison. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h
[2] Gregory Gutin, Mark Jones and Magnus Wahlström, “Structural Parameterizations of the Mixed Chinese Postman Problem”, original research preprint, 2014, Introduction and formal MCPP definition directly checked. registry ↩a ↩b ↩c ↩d
[3] “Algorithms for the Rural Postman Problem”, Computers & Operations Research, original research article, publisher abstract checked for the required-subset distinction. registry ↩