2
$\begingroup$

The Windy Postman Problem seeks the cheapest tour in a complete undirected graph, that traverses each edge at least once; the cost of traversing an edge is positive and may depend on the direction, in which an edge is traversed.
It can be assumed that the graph is complete.

Zaw Win has proved that the problem is solvable in polynomial time if the graph is eulerian and NP-hard otherwise.

Now, as the graph is complete, it is eulerian, iff the number of vertices is odd and a complete non-eulerian graph can be rendered eulerian by removing the edges of a perfect matching, which leads to the following

Questions:

  • in an optimal solution to a non-eulerian Windy Postman Problem of a complete graph the set of edges that are traversed more than once constitute to a perfect matching and each of those edges is traversed exactly twice?
  • what is the performance of the heuristic of taking as the edges of the perfect matching the ones whose weight-sum over both directions of traversal is minimal and then adding the edges of the shortest euler tour through the other edges?
  • Is the minimum weight matching the best choice of edges to traverse twice?

the rationale behind the heuristic is that the postman would move along the euler tour and whenever a vertex is encountered that is adjacent to matching edge that hasn't been traversed yet, traverse it and return along it again, essentially treating the matching edges as deadend streets.

As both parts of the heuristic, determining an optimal general perfect matching and determining the optimal solution to the restriction of the Windy Postman Problem to an eulerian spanner, are polynomial and so is the suggested heuristic.


Added 2019-11-06:

if all directional edgeweights in a non-eulerian Windy Postman Problem are strictly positive, then the multiset of edges resembling the optimal eulerian tour that visits each edge at least once, must be of minimal cardinality because otherwise the length of the tour could be reduced by removing a two-regular directed subgraph of positive weightsum while preserving the existence of an eulerian tour.

The smallest possible cardinality of an eulerian tour through the graph of the problem instance is however achieved by bidirectional traversal of the edges of a perfect matching of the odd-degree vertices of the undirected graph.

Therefore the "structure" of the optimal solution must be the same as the one suggested for the heuristic.
Thus the heuristic is a relaxed version of a correct algorithm, the relaxation being the not necessarily optimal choice of the minimum weight matching as the edges that shall be traversed bidirectionally on an eulerian tour.

$\endgroup$
2
  • 1
    $\begingroup$ I want to see a convincing proof that the optimal matching can be determined in polynomial time. A challenge instance would have at least three or four nodes which are cheap to visit from any other node. Gerhard "This Isn't Matching My Expectations" Paseman, 2019.09.14. $\endgroup$ Sep 14 '19 at 15:51
  • $\begingroup$ @GerhardPaseman I'm completely with you; what I suggested is essentially a greedy heuristic: optimizing two parts separately and then combining them doesn't guarantee combined optimality. $\endgroup$ Sep 14 '19 at 16:01
0
$\begingroup$

Regarding the 3rd question as to whether the minimum weight matching is the best choice of edges to be traversed twice, I meanwhile found a counterexample based on the following observation:

Every choice of the edgeset of a vertex-covering forest in which each node has odd degree yields a valid selection of bidirectional traversal for the edges in the forest and unidirectional transversal of the edges that are not in the forest; perfect matchings are just a special vertex-covering forests with minimal cardinality of the edgeset.

A concrete counterexample to the optimality of traversing the edges of a matching twice is the following:

$V:=\lbrace A,\,B,\,C,\,D\rbrace$

$\left|(A,B)\right|=\left|(B,C)\right|=\left|(C,A)\right|=3;$
$\left|(B,A)\right|=\left|(A,C)\right|=\left|(C,B)\right|=3+x;$

$\left|(A,D)\right|=\left|(B,D)\right|=\left|(C,D)\right|=1;$
$\left|(D,A)\right|=\left|(D,B)\right|=\left|(D,C)\right|=1+x;$

In that case traversing the edges of a matching twice costs $8+2x$,
whereas traversing the edges adjacent to $D$ twice costs $6+3x$.

Whenever $x<2$ the matchings aren't the optimal choice.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.