Chinese Postman Problem, in depth: covering every edge with Euler circuits, odd-vertex matching, directed min-cost flow and NP-hard variants

Euler and the parity of degrees

A closed walk using every edge exactly once is an Eulerian circuit, and a connected graph has one exactly when every vertex has even degree. If the graph already satisfies that, the answer is the total edge weight and any Eulerian circuit is optimal; Hierholzer's algorithm finds one in linear time.

Otherwise some vertices have odd degree, and there is always an even number of them: the degrees sum to twice the edge count, so the odd degrees must pair off. A walk that enters and leaves an odd vertex must reuse some edge there. Reusing an edge is equivalent to adding a parallel copy of it, and the task becomes: add copies of existing edges, as cheaply as possible, so that every degree becomes even. The answer is the total original weight plus the weight of the copies.

The algorithm

Copies form paths between odd vertices. Every added path flips the parity of its two endpoints and leaves interior vertices unchanged, so the added edges must decompose into paths that pair up the odd vertices. The cheapest path between two odd vertices is a shortest path, and the cheapest set of paths is the pairing with minimum total shortest-path distance. That gives the algorithm for a connected undirected graph with non-negative weights:

1. Find the set O of odd-degree vertices. If it is empty, skip to the last step.
2. Compute shortest-path distances between every pair of vertices in O, for example with Dijkstra from each odd vertex.
3. Build the complete graph on O with those distances and find a minimum-weight perfect matching.
4. For each matched pair, add a copy of every edge on its shortest path.
5. Find an Eulerian circuit in the augmented multigraph; its weight is the answer.

Matching is the heart of it, and it is the general (non-bipartite) kind, because any odd vertex can pair with any other. Edmonds' blossom algorithm solves minimum-weight perfect matching in polynomial time, O(n^3) for n odd vertices in good implementations; see maximum matching in general graphs for how blossoms work. A useful structural fact: an optimal solution never needs more than one extra copy of any edge, because two copies could both be removed while keeping all parities even and connectivity intact, lowering the cost.

Worked example: where greedy pairing fails

Take five vertices with edges A-B 2, B-C 1, C-D 2, B-E 3 and C-E 3, total weight 11. Degrees are A 1, B 3, C 3, D 1 and E 2, so O = {A, B, C, D}. Shortest distances among them are A-B 2, B-C 1, C-D 2, A-C 3, B-D 3 and A-D 5.

A greedy approach pairs the closest odd vertices first: B-C at 1, leaving A-D at 5, for 6 extra. There are only three perfect matchings on four vertices: {A-B, C-D} costs 4, {A-C, B-D} costs 6, and {A-D, B-C} costs 6. The minimum is 4, so the optimal tour has weight 15 while greedy gives 17. Greedy fails because taking the cheapest pair can strand the remaining vertices far apart, which is why the problem needs a real matching algorithm.

Duplicate A-B and C-D. Now A and D have degree 2 and B and C have degree 4. One Eulerian circuit is A, B, E, C, D, C, B, A, with weight 2 + 3 + 3 + 2 + 2 + 1 + 2 = 15. Every edge appears, and only the two duplicated edges appear twice.

A tested implementation

The implementation below is exact and self-contained. It uses Dijkstra for distances, a bitmask dynamic program for the minimum perfect matching, and iterative Hierholzer for the circuit. The matching DP always pairs the lowest-numbered unmatched vertex, so it explores (k-1)(k-3)... pairings through 2^k memoized states, practical up to about 20 odd vertices. Beyond that, substitute a blossom-based matcher.

import heapq
from collections import defaultdict
from functools import lru_cache

def dijkstra(adj, src):
    dist, prev, pq = {src: 0}, {}, [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if d + w < dist.get(v, float("inf")):
                dist[v], prev[v] = d + w, (u, w)
                heapq.heappush(pq, (d + w, v))
    return dist, prev

def euler_circuit(edges, start):
    adj = defaultdict(list)
    for i, (u, v, _) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    used, stack, out = [False] * len(edges), [start], []
    while stack:
        u = stack[-1]
        while adj[u] and used[adj[u][-1][1]]:
            adj[u].pop()
        if adj[u]:
            v, i = adj[u].pop()
            used[i] = True
            stack.append(v)
        else:
            out.append(stack.pop())
    return out[::-1]

def chinese_postman(edges, start):
    """edges: (u, v, w) undirected, connected, w >= 0. Returns (cost, closed walk)."""
    adj = defaultdict(list)
    for u, v, w in edges:
        adj[u].append((v, w))
        adj[v].append((u, w))
    odd = sorted(x for x in adj if len(adj[x]) % 2)
    sp = {o: dijkstra(adj, o) for o in odd}

    @lru_cache(maxsize=None)
    def match(mask):                      # min cost to pair the odd vertices in mask
        if mask == 0:
            return 0, ()
        i = (mask & -mask).bit_length() - 1
        rest, best, m = mask & ~(1 << i), (float("inf"), ()), mask & ~(1 << i)
        while m:
            j = (m & -m).bit_length() - 1
            m &= m - 1
            cost, pairs = match(rest & ~(1 << j))
            cost += sp[odd[i]][0].get(odd[j], float("inf"))
            if cost < best[0]:
                best = (cost, ((odd[i], odd[j]),) + pairs)
        return best

    extra, pairs = match((1 << len(odd)) - 1)
    if extra == float("inf"):
        raise ValueError("graph is not connected")
    multi = list(edges)
    for a, b in pairs:                    # copy each edge on the shortest a-b path
        prev, x = sp[a][1], b
        while x != a:
            y, w = prev[x]
            multi.append((y, x, w))
            x = y
    return sum(w for _, _, w in edges) + extra, euler_circuit(multi, start)

E = [("A", "B", 2), ("B", "C", 1), ("C", "D", 2), ("B", "E", 3), ("C", "E", 3)]
cost, walk = chinese_postman(E, "A")
assert cost == 15 and len(walk) == len(E) + 2 + 1

Test it beyond the example: on random small graphs, compare the cost with a brute force over all multisets of duplicated edges, and check that the returned walk is closed, uses every original edge, and has the claimed weight. Those three assertions catch nearly every implementation bug.

The directed postman problem

On a directed graph, such as one-way streets or the transitions of a state machine, the condition for an Eulerian circuit is that every vertex has equal in-degree and out-degree and the graph is strongly connected. Without strong connectivity there may be no covering walk at all. A vertex with more incoming than outgoing edges needs extra outgoing traversals; one with more outgoing needs extra incoming ones. Choosing which paths to repeat is a transportation problem, solved exactly by min-cost flow with each vertex's imbalance as its supply or demand and edge weights as costs; the flow on each edge is how many extra times to traverse it. Unlike the undirected case, an edge may need several extra passes.

A concrete use is conformance testing. Model a protocol or user interface as a state machine whose edges are transitions, each weighted by the time it takes to drive. A directed postman tour is then the shortest single test sequence that exercises every transition at least once, starting and ending in the reset state. Suppose a login flow has transitions Idle to Form, Form to Error, Error to Form, Form to Home and Home to Idle, each of cost 1. Every state has equal in-degree and out-degree (Form has two of each), so the five transitions form a closed walk of cost 5 with no repeats. Add a second exit, Error to Idle, and Error now has out-degree 2 against in-degree 1 while Idle has in-degree 2 against out-degree 1. Flow must carry one unit from Idle back to Error, along Idle, Form, Error at cost 2, so the tour costs 6 plus 2, or 8. The code below computes exactly that repeat cost.

from collections import defaultdict
import networkx as nx

def directed_postman_extra(edges):
    """edges: (u, v, w) directed, strongly connected, integer w. Returns extra cost, flows."""
    G = nx.DiGraph()
    for u, v, w in edges:                 # parallel edges: keep the cheapest for repeats
        if not G.has_edge(u, v) or w < G[u][v]["weight"]:
            G.add_edge(u, v, weight=w)
    out_deg, in_deg = defaultdict(int), defaultdict(int)
    for u, v, _ in edges:
        out_deg[u] += 1
        in_deg[v] += 1
    for x in G:                           # negative demand = sends flow
        G.nodes[x]["demand"] = out_deg[x] - in_deg[x]
    flow = nx.min_cost_flow(G)            # no capacity attribute = unbounded
    return nx.cost_of_flow(G, flow), flow

Variants and complexity

Failure modes and real routing

Greedy pairing. As the example shows, pairing nearest odd vertices first is not optimal; it is a fine heuristic only when you also report the gap to a matching lower bound. Matching on edges instead of paths. Odd vertices are rarely adjacent, so the matching must use shortest-path distances on a complete graph, then expand each pair back into its path. Disconnected input. Unreachable pairs show up as infinite distances; check connectivity first and report components. Isolated vertices and self-loops. A self-loop adds two to a degree and never changes parity; isolated vertices should be dropped before checking connectivity. Negative weights. The model assumes non-negative costs; a negative edge would be traversed endlessly. Directed graphs that are not strongly connected. Min-cost flow reports infeasibility, which is the correct answer, so surface it rather than retrying.

In real routing, the abstract graph is the easy part. Turn penalties, U-turn bans, street sides for kerbside collection and time windows all break the clean model. A common approach is to encode turns into a line graph, solve the clean postman problem to get a lower bound and a starting route, then improve it with local search under the real constraints. The vertex-covering counterpart, the travelling salesman problem, is a useful contrast: covering every edge is polynomial, covering every vertex is NP-hard.

What to do next

1. Model your network as a graph and decide whether it is undirected, directed or mixed; that single decision sets the complexity.
2. Check connectivity (strong connectivity if directed) and drop isolated vertices.
3. List the odd vertices or degree imbalances; if there are none, run Hierholzer and stop.
4. For undirected graphs, compute shortest paths between odd vertices and solve an exact minimum perfect matching; use the bitmask DP for small sets and a blossom implementation for large ones.
5. For directed graphs, solve min-cost flow on the imbalances with integer weights.
6. Expand the pairs or flows into duplicated edges, find the Eulerian circuit, and assert coverage, closure and total weight.
7. If real constraints apply, treat this answer as a lower bound and starting route for a constrained local search.