At the meeting of the Steering Committee of WG 2017, it was decided to install the WG Test of Time award so as to honour papers that appeared in a past WG and that have proven to be very influential afterward and, moreover, to honour their authors.
For 2024 the committee, consisting of Daniel Paulusma, Jan Arne Telle and Dimitrios Thilikos, decided to concentrate on the papers that appeared at WG in the years 1988-1991. The committee unanimously agreed on a paper from the seventeenth Workshop on Graph Theoretic Concepts in Computer Science, which took place from 17-19 June 1991 in Fischbachau in Germany.
The paper that wins the fourth WG Test of Time award is
WG 1991: Approximating treewidth, pathwidth, and minimum elimination tree height written by Hans L. Bodlaender, John R. Gilbert, Ton Kloks and Hjálmtyr Hafsteinsson.
Many congratulations to the authors.
The paper has been the first systematic study of the approximation complexity of important graph parameters such as treewidth and pathwidth. These two parameters have been pivotal in deep results in modern combinatorics such as the Graph Minors Series but also have important and long-standing applications in algorithm design. The paper introduced a set of insightful tools on how balanced separators can be used in the computation of treewidth and other width parameters. The main result is a polynomial algorithm that provides a O(log n) approximation of the treewidth of an n-vertex graph. This, in turn, implies a O(log² n) approximation for pathwidth. Moreover it is proved that, for both parameters, a constant-additive approximation cannot be attained unless P=NP. The techniques of the paper were highly influential in modern graph algorithm design and have been extended in many ways and directions.
The awarded paper appeared later in "Journal of Algorithms Volume 18, Issue 2, March 1995, pages 238-255". The importance of the paper is also reflected by it has received over 500 citations and is a worthy winner of the 2024 WG Test of Time award.
At the meeting of the Steering Committee of WG 2017, it was decided to install the WG Test of Time award so as to honour papers that appeared in a past WG and that have proven to be very influential afterward and, moreover, to honour their authors. The first two awards were handed out in 2018 and 2019 and were concentrated on papers that appeared during the years up to 1983. In 2020, 2021, and 2022 WG was held mainly online and no awards were given.
For 2023 the newly appointed committee consisting of Daniel Paulusma, Jan Arne Telle and Dimitrios Thilikos decided to concentrate on the papers that appeared at WG in the years 1984-1987. The committee unanimously agreed on a paper from the thirteenth Workshop on Graph Theoretic Concepts in Computer Science, which took place from 29 June to 1 July 1987 in Kloster Banz/Staffelstein in Germany.
The paper that wins the third WG Test of Time award is
WG 1987: Approximate counting, uniform generation and rapidly mixing Markov chains written by Alistair Sinclair and Mark Jerrum.
Many congratulations to the authors.
The paper studies effective approximate solutions to combinatorial counting and uniform generation problems and links these two classes of problems in a remarkable way. For self-reducible structures, it is shown that randomized approximate counting within an arbitrary polynomial factor in polynomial time leads to almost uniform generation in polynomial time. The main proof technique introduced is the rapid convergence for a broad class of finite ergodic Markov chains based on the structural properties of the underlying graph. The results are used to give an almost uniform generating procedure for labeled graphs with a given degree sequence.
The awarded paper appeared later in “Information and Computation Volume 82, Issue 1, July 1989, Pages 93-133” and had an important influence on a long line of advances around randomized approximation schemes and sampling techniques for counting problems. The importance of the paper is also reflected by it has received close to 900 citations. It is a worthy winner of the 2023 WG Test of Time award. We are proud that WG has produced papers that so evidently stood the test of time.
At the meeting of the Steering Committee of WG 2017, it was decided to install the WG Test of Time award, to honour papers that appeared in a past WG, and that have proven to be very influential afterwards, and, with the paper, also to honour the authors.
The winner of the second WG Test of Time award was decided by a committee consisting of Hans Bodlaender, Rolf Möhring, and Gerhard Woeginger. This time, the award committee mainly concentrated on the papers that appeared during the years 1978-1983. The committee selected several papers that stood the test of time in a remarkable way, discussed their merits, and then unanimously agreed on a paper from the ninth Workshop on Graph Theoretic Concepts in Computer Science that took place in 1983 in Haus Ohrbeck near Osnabrück, Germany.
The paper that wins the second WG Test of Time award is:
A local-ratio theorem for approximating the weighted vertex cover problem written by Reuven Bar-Yehuda and Shimon Even.
Many congratulations to the authors.
In their paper, the authors derive a polynomial time approximation algorithm for the vertex cover problem. A vertex cover for a vertex-weighted graph is a subset of the vertices, such that each edge has at least one end- point in the subset. An approximation algorithm has performance guarantee R, if for every input graph it returns a vertex cover whose weight is at most R times as large as the weight of the cheapest possible vertex cover. Many approximation algorithms with performance guarantee R = 2 have been constructed for vertex cover over the years, some of which appeared before the paper by Bar-Yehuda and Even, some of which appeared later, and nowadays there is evidence that the value R = 2 actually can not be beaten.
The main contribution of Bar-Yehuda and Even is not in the concrete value of their performance bound, but in the underlying method that their paper introduces: The local-ratio method. The technical main idea is to decompose the vertex weights in an optimal solution and in an approximate solution, and to establish connections between these two decompositions. The technique is remarkably simple and elegant, and can be applied to a variety of fundamental optimization problems, including all kinds of covering and packing problems in network design, scheduling theory, graph algorithms, etc. For instance, Bafna, Narayanan and Ravi applied the technique in 1996 to the feedback vertex set problem, and Fujito applied it in 1998 to approximate certain vertex-deletion problems in graphs.
The local-ratio method has triggered a long sequence of applications, variations and strengthenings. It has become a central tool in the development of approximation algorithms, and its impact goes far beyond graph theory. Google scholar (accessed on May 25, 2019) lists 495 citations to the award paper, and there are hundreds of further citations to the follow-up papers that applied and extended the technique to other problems.
The award paper started an entire branch of approximation algorithms and hence is a worthy winner of the 2019 WG Test of Time award. We are proud that WG has produced papers that so evidently stood the test of time.
At the meeting of the Steering Committee of WG 2017, it was decided to install the WG Test of Time award, to honour papers that appeared in a past WG, and have proven to be very influential afterwards, and, with the paper, also honour the authors of these papers.
The winner of the first WG Test of Time award was decided by a committee, existing of Rolf Möhring, Gerhard Woeginger and Hans Bodlaender. We have this year the 44th Workshop on Graph Theoretic Concepts in Computer Science. The workshop has been held each year since its early beginning, and thus, the first WG was organized in 1975. The award committee looked at the papers that appeared in the first seven years of WG. From these, the committee selected papers that stood the test of time in a remarkable way, discussed the relative merits, and then, unanimously decided on a paper from the sixth Workshop on Graph Theoretic Concepts in Computer Science.
The paper that wins the first WG Test of Time award is:
Bounding the bandwidth of NP-complete problems, written by Burkhard Monien and Ivan Hal Sudborough.
Many congratulations to the authors.
In this paper, the authors study the complexity of a number of graph problems, and other problems, when the graph has bounded bandwidth. A graph has bandwidth at most k, if we can number the vertices from 1 to n, such that for each edge, the difference between the numbers of its endpoints is at most k. The authors show for several well-known NP-complete graph problems, that these become polynomial solvable when the bandwidth of the graph is bounded by a constant, and study the relative complexity of these problems. Also, for problems like Satisfiability, they obtain a similar result when looking at the bandwidth of the graph that can be obtained by the connections between clauses and variables.
The result was the first in a long and important development in algorithmic graph theory. A few years after the appearance of this WG paper, and its companion paper by Monien and Sudborough at STOC 1981, generalizations of this result were obtained. In the midst of the 1980s, several groups of authors, often independently, invited graph parameters associated to tree-like structures that allowed many NP-hard problems to be solved in polynomial time. Later, the equivalence of these concepts was observed, and the terminology was taken from the graph minors work by Robertson and Seymour, with the central concepts and terms being treewidth and tree-decomposition. These notions now play a central role in many graph theoretic investigations, but also are used in practical applications. The number of papers were these concepts play a role is to be written with five digits; Google scholar lists over 18000 papers containing the word treewidth.
Graphs of bounded bandwidth have bounded treewidth. Thus, the award paper stands at the cradle of these developments, with the central insight that when the graph has a special structure with small separators everywhere allows dynamic programming and thus fast algorithmic solutions to otherwise hard problems there, on the typewriter written pages, of the WG 1980 proceedings.
As WG community, we can be proud that our series of meetings contains this paper that so evidently stood the test of time. But of course, most proud can be the authors of the paper, with having about 40 years ago ideas that had such large impact.