Chinese postman problem

<h2 id="undirected-solution-and-t-joins">Undirected solution and T-joins</h2>
The undirected route inspection problem can be solved in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> by an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> based on the concept of a T-join.
Let T be a set of vertices in a graph. An edge set J is called a T-join if the collection of vertices that have an odd number of incident edges in J is exactly the set T. A T-join exists whenever every connected component of the graph contains an even number of vertices in T. The T-join problem is to find a T-join with the minimum possible number of edges or the minimum possible total weight.
For any T, a smallest T-join (when it exists) necessarily consists of 
 
 
 
 
 
 
 1
 2
 
 
 
 
 |
 
 T
 
 |
 
 
 
 {\displaystyle {\tfrac {1}{2}}|T|}
 
 paths that join the vertices of T in pairs. The paths will be such that the total length or total weight of all of them is as small as possible. In an optimal solution, no two of these paths will share any edge, but they may have shared vertices. A minimum T-join can be obtained by constructing a <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> on the vertices of T, with edges that represent shortest paths in the given input graph, and then finding a <a href="/facts/Matching_(graph_theory)/s0pUJ7hd">minimum weight perfect matching</a> in this complete graph. The edges of this matching represent paths in the original graph, whose union forms the desired T-join.
Both constructing the complete graph, and then finding a matching in it, can be done in O(n3) computational steps.
For the route inspection problem, T should be chosen as the set of all odd-degree vertices. By the assumptions of the problem, the whole graph is connected (otherwise no tour exists), and by the <a href="/facts/Handshaking_lemma/z51Dg4R5">handshaking lemma</a> it has an even number of odd vertices, so a T-join always exists. Doubling the edges of a T-join causes the given graph to become an Eulerian multigraph (a connected graph in which every vertex has even degree), from which it follows that it has an <a href="/facts/Euler_tour/4l2G67c7">Euler tour</a>, a tour that visits each edge of the multigraph exactly once. This tour will be an optimal solution to the route inspection problem.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<h2 id="directed-solution">Directed solution</h2>
On a directed graph, the same general ideas apply, but different techniques must be used. If the directed graph is Eulerian, one need only find an Euler cycle. If it is not, one must find T-joins, which in this case entails finding paths from vertices with an in-<a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> greater than their out-<a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> to those with an out-<a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> greater than their in-<a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> such that they would make in-degree of every vertex equal to its out-degree. This can be solved as an instance of the <a href="/facts/Minimum-cost_flow_problem/bkYsFJa9">minimum-cost flow problem</a> in which there is one unit of supply for every unit of excess in-degree, and one unit of demand for every unit of excess out-degree. As such it is solvable in O(|V|2|E|) time. A solution exists if and only if the given graph is <a href="/facts/Strongly_connected/P6rBqb7W">strongly connected</a>.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a><a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>

<h2 id="applications">Applications</h2>
Various combinatorial problems have been reduced to the Chinese Postman Problem, including finding a <a href="/facts/Maximum_cut/9rulcdeW">maximum cut</a> in a planar graph 
and a minimum-mean length circuit in an undirected graph.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>

<h2 id="variants">Variants</h2>
A few variants of the Chinese Postman Problem have been studied and shown to be <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

<ul><li>The windy postman problem is a variant of the route inspection problem in which the input is an undirected graph, but where each edge may have a different cost for traversing it in one direction than for traversing it in the other direction. In contrast to the solutions for directed and undirected graphs, it is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a><a class="footnote-ref" id="fnref:14" href="#fn:14">14</a></li>
<li>The <a href="/facts/Mixed_Chinese_postman_problem/v56cXjqt">Mixed Chinese postman problem</a>: for this problem, some of the edges may be directed and can therefore only be visited from one direction. When the problem calls for a minimal traversal of a digraph (or multidigraph) it is known as the "New York Street Sweeper problem."<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a></li>
<li>The k-Chinese postman problem: find k cycles all starting at a designated location such that each edge is traversed by at least one cycle. The goal is to minimize the cost of the most expensive cycle.</li>
<li>The "Rural Postman Problem": solve the problem with some edges not required.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a></li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Travelling_salesman_problem/2WEKVLnV">Travelling salesman problem</a></li>
<li><a href="/facts/Arc_routing/pM9Aj6g3">Arc routing</a></li>
<li><a href="/facts/Mixed_Chinese_postman_problem/v56cXjqt">Mixed Chinese postman problem</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a>, <a href="https://mathworld.wolfram.com/ChinesePostmanProblem.html">"Chinese Postman Problem"</a>, <a href="/facts/MathWorld/yc1jodbq">MathWorld</a></li>
<li> Media related to Route inspection problem at Wikimedia Commons</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), CRC Press, pp. 640–642, ISBN 9781420099829 <a href="9781420099829" target="_blank">9781420099829</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Edmonds, J.; Johnson, E.L. (1973), "Matching Euler tours and the Chinese postman problem" (PDF), Mathematical Programming, 5: 88–124, doi:10.1007/bf01580113, S2CID 15249924 <a href="http://www.eecs.umich.edu/%7Epettie/matching/Edmonds-Johnson-chinese-postman.pdf" target="_blank">http://www.eecs.umich.edu/%7Epettie/matching/Edmonds-Johnson-chinese-postman.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">"The Travelling Salesman Problem" (PDF). <a href="http://staff.ustc.edu.cn/~xujm/Graph21.pdf" target="_blank">http://staff.ustc.edu.cn/~xujm/Graph21.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Kwan, Mei-ko (1960), "Graphic programming using odd or even points", Acta Mathematica Sinica (in Chinese), 10: 263–266, MR 0162630. Translated in Chinese Mathematics 1: 273–277, 1962. <a href="/wiki/Meigu_Guan" target="_blank">/wiki/Meigu_Guan</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Pieterse, Vreda; Black, Paul E., eds. (September 2, 2014), "Chinese postman problem", Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology, retrieved 2016-04-26 <a href="https://xlinux.nist.gov/dads/HTML/chinesePostman.html" target="_blank">https://xlinux.nist.gov/dads/HTML/chinesePostman.html</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Grötschel, Martin; Yuan, Ya-xiang (2012), "Euler, Mei-Ko Kwan, Königsberg, and a Chinese postman" (PDF), Optimization stories: 21st International Symposium on Mathematical Programming, Berlin, August 19–24, 2012, Documenta Mathematica, Documenta Mathematica Series, Extra: 43–50, doi:10.4171/dms/6/10, ISBN 978-3-936609-58-5, MR 2991468. <a href="978-3-936609-58-5" target="_blank">978-3-936609-58-5</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Lawler, E.L. (1976), Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Edmonds, J.; Johnson, E.L. (1973), "Matching Euler tours and the Chinese postman problem" (PDF), Mathematical Programming, 5: 88–124, doi:10.1007/bf01580113, S2CID 15249924 <a href="http://www.eecs.umich.edu/%7Epettie/matching/Edmonds-Johnson-chinese-postman.pdf" target="_blank">http://www.eecs.umich.edu/%7Epettie/matching/Edmonds-Johnson-chinese-postman.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Edmonds, J.; Johnson, E.L. (1973), "Matching Euler tours and the Chinese postman problem" (PDF), Mathematical Programming, 5: 88–124, doi:10.1007/bf01580113, S2CID 15249924 <a href="http://www.eecs.umich.edu/%7Epettie/matching/Edmonds-Johnson-chinese-postman.pdf" target="_blank">http://www.eecs.umich.edu/%7Epettie/matching/Edmonds-Johnson-chinese-postman.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Eiselt, H. A.; Gendreau, Michel; Laporte, Gilbert (1995), "Arc Routing Problems, Part 1: The Chinese Postman Problem", Operations Research, 43 (2): 231–242, doi:10.1287/opre.43.2.231, hdl:11059/14013 <a href="/wiki/Operations_Research_(journal)" target="_blank">/wiki/Operations_Research_(journal)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">A. Schrijver, Combinatorial Optimization, Polyhedra and Efficiency, Volume A, Springer. (2002). <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G, A compendium of NP optimization problems, KTH NADA, Stockholm, retrieved 2008-10-22 <a href="/wiki/Marek_Karpinski" target="_blank">/wiki/Marek_Karpinski</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn: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 0754427. <a href="/wiki/Meigu_Guan" target="_blank">/wiki/Meigu_Guan</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Lenstra, J.K.; Rinnooy Kan, A.H.G. (1981), "Complexity of vehicle routing and scheduling problems" (PDF), Networks, 11 (2): 221–227, doi:10.1002/net.3230110211 <a href="http://ageconsearch.umn.edu/record/272191/files/erasmus119.pdf" target="_blank">http://ageconsearch.umn.edu/record/272191/files/erasmus119.pdf</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), CRC Press, pp. 642–645, ISBN 9781420099829 <a href="9781420099829" target="_blank">9781420099829</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Lenstra, J.K.; Rinnooy Kan, A.H.G. (1981), "Complexity of vehicle routing and scheduling problems" (PDF), Networks, 11 (2): 221–227, doi:10.1002/net.3230110211 <a href="http://ageconsearch.umn.edu/record/272191/files/erasmus119.pdf" target="_blank">http://ageconsearch.umn.edu/record/272191/files/erasmus119.pdf</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
</ol>

Chinese postman problem open-in-new

Chinese postman problem