What it is
You're thinking of the Chinese Postman Problem, otherwise known as the route inspection problem or postman tour.
What it does
The problem asks for the shortest/minimal-cost tour of a graph which visits each edge at least once. This is called the Chinese Postman Tour (CPT) Solving this problem allows you to, among other applications:
Find the optimal route for a school bus or mail delivery, wherein all streets must be visited to pick up passengers/drop off mail, and the bus is not constrained to visit streets only once. Other examples are snow plow routing, highway departments painting lines down streets, or police cars trying to visit every street on a beat.
Characterize a machine's complexity and/or optimally test that machine. For instance, pressing buttons on a phone is like taking a directed edge between states. Menus come up and menus close. If you know all of the states the phone can be in, then solving the CPP gives you an optimal plan for testing all state transitions. The length of this plan is measure of the machine's complexity. For instance, a Nokia 2110 mobile phone has a menu subsystem of 88 menu-items and 273 actions. The CPT of this system has a length of 515 button presses. [1]
Undirected Graph
This is the original problem, as introduced by Mei-Ko Kwan in 1960. His paper was translated to English in 1962. [2] Shortly thereafter, it was shown that the problem could be reduced to matching and was therefore solvable in polynomial time using linear programming. [3] Grötschel et al. give a nice little history of this. [5]
To solve the problem note that the graph must be a single connected component.
If the graph is a single connect component and all nodes have even degree, then the graph has a Eulerian path. This path may be found in O(|E|) time using Hierholzer's algorithm. If not all of the nodes have even degree, then we need a more powerful algorithm.
Observe that if a graph has two nodes of odd degree, adding additional edges connecting them will result in a multigraph in which every node has even degree. Per the above, such a graph has an easily-findable Eulerian path. Further: whichever route is taken, the edges which must be traversed more than once will connect the two nodes of odd degree. It's easy to see why: adding an edge to one of the odd-degree nodes makes it even degree, but makes the other node incident on the edge have odd degree. The only way to obtain a graph with only even-degree nodes is to make a path between the two odd-degree nodes. In order to minimize the cost of the Eulerian path on the multigraph, we should add additional edges along the minimum-cost path between the two odd-degree nodes. This could be found with, say, Dijkstra's algorithm.
Now, imagine that we have 2n odd nodes. With some thought on the foregoing, you can convince yourself that you will need n distinct, non-overlapping paths connecting pairs of these vertices. Knowing this, one way to solve the problem is to use the Floyd-Warshall algorithm to calculate the all-pairs shortest paths between the odd-degree nodes in O(|V|³) time. A maximum weighted matching can then be found in O(|E|*|V| log |V|) time. [4]
Michaels has a simple write-up about this along with some intuitive proofs. [6] Laporte offers a more technical description, casting the matching problem as a linear integer program. [7] Eiselt et al. give another technical description along with a fairly extensive review of related problems (see below). [8]
Some other variants
Since we're always just one thought away from making algorithms problems harder, here are some variants which may be of interest:
Entirely directed graph: A solution exists here only if the graph is strongly connected (there are fast tests for this). To find the solution, find in O(|E|) time the difference between each vertex's in- and out-degree is calculated. Then a multiple finite source network problem is solved: each node produces or consumes flow according to its in-out difference. The problem is solved for the least-weight max flow in O(|V|² |E|) time. The amount of flow along an edge is the number of parallel edges which must be inserted alongside it into order to make the graph Eulerian. The Euler tour can then be found in O(|E|) time using Hierholzer's algorithm. Harold Thimbleby provides a well-documented Java implementation (see [1], but also his website).
Graph with both directed and undirected edges: This problem is NP-Complete. It remains so even if the graph is planar, with nodes having total degree at most 3, and all edges having costs equal to 1. Which is to say that the mixed graph is a hard problem even in severely constrained situations. [9]
Undirected tree graph: Each edge of the tree is visited twice. There are quick ways to determine if a graph is a tree: see this wiki page.
Graph with a Eulerian tour: The Eulerian tour is the CPT. There are quick ways to determine if a graph is Eulerian: see this wiki page.
Graphs in which edges must be visited according to a priority: This is the hierarchical CPP. It is not always solvable. When it is, it can be NP-complete. But, under certain conditions, there is an O(N⁵) algorithm. [10]
Graphs with time windows: In this formulation each edge is associated with a range of times [le,ue] during which the edge must be completed. Such a problem arises when, say, street sweepers are cleaning streets and certain streets are required to be car free during different times. This problem is NP-hard and can be solved exactly via constraint programming. [11]
You don't need to visit all the edges: This is known as the rural postman problem. This problem is NP-hard for both the directed and undirected cases. Instances with both directed and undirected edges (the stacker crane problem) are also NP-hard. See [12] for a review.
The cost of edges is different depending on the direction of traversal: This is known as the windy postman problem. This problem is NP-complete. [13]
[1] Thimbleby, H. 2003. The directed Chinese Postman Problem. Softw: Pract. Exper., 33: 1081–1096. doi:10.1002/spe.540
[2] Kwan, Mei-Ko. 1962. Graphic programming using odd or even points, Chinese Mathematics 1, pp. 273–277.
[3] Edmonds, J., Johnson, E.L., 1973. Matching, Euler tours and the Chinese postman. Mathematical programming 5, 88–124.
[4] Galil, Z., Micali, S., Gabow, H. 1986. An O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs. SIAM J. Comp. 15, 120-130.
[5] Grötschel, M., Yuan, Y., 2012. Euler, Mei-ko Kwan, Königsberg, and a Chinese Postman. Optimization Stories 43.
[6] Michaels, J.G., 1991. Chapter 20: The Chinese Postman Problem, in: Applications of Discrete Mathematics. McGraw-Hill Higher Education, pp. 354–364.
[7] Laporte, G., 2014. Chapter 3: The Undirected Chinese Postman Problem, in: Arc Routing. pp. 53–64.
[8] Eiselt, H.A., Gendreau, M., Laporte, G., 1995. Arc routing problems, part I: The chinese postman problem. Operations research 43, 399–414.
[9] Papadimitriou, C.H., 1976. On the complexity of edge traversing. Journal of the ACM (JACM) 23, 544–554. (If this Papadimitriou's name looks familiar, it may be that you recognize him as a character from Logicomix).
[10] Dror, M., Stern, H. and Trudeau, P. (1987), Postman tour on a graph with precedence relation on arcs. Networks, 17: 283–294. doi:10.1002/net.3230170304
[11] U. F. AMINU AND R. W. EGLESE, A constraint programming approach to the Chinese postman problem with time windows, Computers & Operations Research, 33 (2006), pp. 3423–3431.
[12] Eiselt, H.A., Gendreau, M., Laporte, G., 1995. Arc routing problems, part II: The rural postman problem. Operations research 43, 399–414.
[13] Guan, Meigu (1984), "On the windy postman problem", Discrete Applied Mathematics, 9 (1): 41–46, doi:10.1016/0166-218X(84)90089-1, MR 754427.
