NSU scientists Rene van Bevern, Head of the Algorithmics Laboratory at the NSU Mechanics and Mathematics Department(MMD) and Oksana Tsidulko, Junior Researcher at the Laboratory, and Vsevolod Afanasyev, MMD sophomore co-authored an article published in “Operations Research Letters” that is part of Q2 on Scopus. The article explores hierarchical Chinese Postman Problems. These Problems require finding the shortest path along the edges of a graph in which the edges are divided into classes and there are precedent constraints between the classes such as an edge can be traversed only when all edges in the classes preceding this class are traversed.
In the Chinese Postman Problem you need to find the shortest path along all the edges of the graph:
The problem got its name because it was first studied by the Chinese mathematician Kwon Mei-Ko in 1960. In the early 1970s, mathematicians in the West and in Novosibirsk started investigating the Problem.
Afanasyev talked about their research,
It all started with an analysis of articles on these Problems. Then Professor van Bevern suggested we look at a specific version of the Problem and the process began. We read articles on the topic, built and tested some hypotheses, and every 1–2 weeks we got together for a brainstorming session on a particular subject. For example, we came up with approximate algorithms, that is, algorithms that, in a sense, exchange accuracy for speed in certain formulations of the Problem. After that, we prepared and presented our results in an article.
For example, to clear snow you want the shortest route but first you must clear snow fr om the main road. A better example is metal cutting. Let's say you want to cut the letter O from a sheet of metal. You must first cut out the inner circle (hole), then the outer one. If you first cut out the outer circle, then the cut disk will fall out of the sheet and we will no longer be able to cut a hole in it.
van Bevern explained why this is worth pursuing,
Chinese Postman Problem variants are interesting because they are on the borderline between easy and difficult problem solving. This distinguishes them from the Traveling Salesman Problem, in which you need to find the shortest walk around the vertices (not edges) of the graph. This is almost always difficult. A Chinese Postman Problem wh ere you want to find the shortest traversal of all edges (not vertices) of a graph, is easily solved. However, if you only need to traverse a given subset of edges? Then it is a Rural Postman Problem and it is suddenly NP-hard that means there are no efficient algorithms for it, if not P = NP. However, if the edges in the subset split into a small number of disconnected components then the Problem is effectively solvable.
In 2014, I contributed to a book on shortest path traversal problems, an overview of the computational complexity of these problems. We identified many open questions. Since then, we, along with a team in London, have been actively working to close these gaps independently of each other. As for hierarchical Chinese Postman Problems, it was only known that they are effectively solvable if the edges in each class form a connected subgraph and the classes are ordered linearly. That means, first you need to go around all the edges of level 1, then level 2, then level 3, and so on. It was also recognized that the problem is NP-hard if the classes are not related.
The scientists obtained a somewhat surprising result that the slightest deviation from the linear ordering of classes leads to an NP-hard problem. Let's say the edges in each class are connected, but in addition to the linearly ordered classes there is another class of edges so you can pass them whenever you want. In this case, the problem turned out to be NP-hard! However, they also got positive results if the classes were linearly ordered so in principle it is not that scary to abandon the edges connectedness in each class. The article’s authors have proven that in this case a minimum of good approximate solutions can be found. They also demonstrated that if the edges in each class form a small number of disconnected components, then the problem is still effectively solvable.
van Bevern summed up their results,
To get positive results we captured an even more general result, that all algorithms for the exact solution to a Rural Postman Problem are transferred to the Chinese Postman Problem with linearly ordered (but not necessarily related) classes. We already know almost everything about the Rural Postman Problem. Unfortunately, we still have one open question, is the Chinese Postman Problem with three associated classes effectively solvable or is it NP-hard?
