Sharper Tour Bounds for the Chinese Postman Problem

Definitions and mathematical statement

A graph is $2$-edge-connected if it is connected and remains connected after deletion of any single edge. Under the usual undirected interpretation of the Chinese postman problem, a postman tour is a closed walk traversing every edge at least once, with repeated traversals permitted. Its objective is to minimize total traversal cost, or the number of traversals in the unweighted setting. The supplied record does not specify which cost setting or graph conventions are intended; these descriptions therefore explain the terminology without selecting the missing hypotheses.

Source question. For the Chinese postman problem on a $2$-edge-connected graph, sharpen the upper and lower bounds for tours discussed in the cited Oberwolfach report, particularly when its ear parameter $k$ is large and its lower bound is weak. Seek improvements that are useful in that regime.

Unresolved formulation. The record supplies neither the definition of $k$ nor the bounds to be improved. It also does not specify whether the bounds concern the minimum tour cost, the cost of a particular construction, or another tour quantity. Consequently, no definite quantified inequality or improvement target can be extracted from this record alone. The meanings of "large," "weak," and "useful" remain unspecified. A precise mathematical formulation requires the report's graph and cost assumptions, ear conventions, baseline inequalities, and intended comparison criterion.

Short English statement

The question asks for better Chinese postman tour bounds on $2$-edge-connected graphs, especially when an ear parameter $k$ is large. The supplied record omits the definition of $k$ and the original inequalities, so the intended improvement cannot yet be stated as a precise mathematical claim.

Sources

• Local UnsolvedMath registry, permanent ID $30002725$, source problem code catalogue entry, title "Sharper Tour Bounds for the Chinese Postman Problem." The supplied record lists proposed year $2014$ and names no individual proposer.
• Supplied report citation: Combinatorial Optimization (2015), Oberwolfach Reports, DOI 10.4171/owr/2014/51, pp. 2873--2932. https://doi.org/10.4171/owr/2014/51. The background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. No problem-specific page or passage is supplied.
• Supplied literature source, labeled "Later uniform-cover bounds": https://arxiv.org/abs/1707.05387. No authors, title, or precise result are supplied for this link.
• Literature assessment dated 2026-08-21: the supplied curation labels the problem open, describes the report bounds as a baseline, reports improvements to related uniform-cover bounds in later tour work, and states that no general resolution of the useful-bound question was found. This is supplied dated curation, not independently verified literature assessment. The source explicitly requests independent verification of time-sensitive status and cited claims.
• The supplied registry labels the statement corrected_verified and reports manual semantic, typographic, and LaTeX review of a meaning-preserving cleanup. These are supplied editorial assertions; they do not resolve the formulation gaps identified here or establish the mathematical status.