On the windy postman problem (Q800837)

The windy postman problem (WPP) is: find a shortest postman route in a connected undirected graph G(V,E), such that for every edge (x,y) the distance from x to y can be different from the distance from y to x. The author proves that WPP is NP-hard. Further, the WPP is restated as follows: let \(G_ 1(V,A)\) be a symmetric directed graph, where for every edge \(e=(x,y)\) in E there are two arcs \(a'=(x,y)\) and \(a''=(y,x)\) in A with a non-negative length \(\ell (a')\) and \(\ell(a'')\). The problem is to find a shortest directed closed path p in \(G_ 1\), such that for every \(e\in E\) at least a' or a'' belong to p. A polynomial bounded algorithm is given for solving WPP if the following condition Q is fulfilled: for every cycle C in G the corresponding cycles C' and C'' obtained from C with the two possible directions have the same length, i.e. \(\ell(C')=\ell(C'').\) Theorem 3 makes the procedure proving condition Q simpler. The author considers also the case when condition Q is ''nearly'' satisfied. G satisfies condition \(Q_ 1\), if for any cycle C in G and any edge \(e\in C\), \(| \ell(C')-\ell(C'')| <\ell(a')+\ell(a'').\) Theorem 5. If there exists a real number \(\epsilon\geq 0\) and a spanning tree T of G, such that (a) for every fundamental cycle \(C_ i\), \(| \ell (C'_ i)-\ell (C''_ i)| \leq \epsilon /s\) (s is the cyclomatic number of G), (b) for every edge e of G, \(\ell(a')+\ell(a'')>\epsilon\), then condition \(Q_ 1\) is satisfied. If G satisfies conditions (a) and (b) of Theorem 5, a polynomial bounded algorithm \((\bar A)\) is given for solving WPP approximately. Theorem 6. Let \(p_ 1\) be the shortest postman route of the WPP on G, and p be the postman route obtained by algorithm \(\bar A.\) Then \(| \ell (p_ 1)\)-\(\ell (p)| <s\epsilon\) (s and \(\epsilon\) are meant as in Theorem 5).