Golomb rulers and algorithmics of structural graph parameters

One sentence summary: A cool mathematical structure called Golomb ruler (or Sidon set) can help when designing hardness reductions for structural graph parameters.

In this paper we studied a routing problem where we want to route vehicles through a graph such that their routes meet in as few edges as possible. My highlight of the paper is the hardness reduction that shows that the problem is hard to solve even on graphs that are very tree-like, that is, the problem is W[1]-hard with respect to the treewidth parameter.

In such a reduction we have to create graphs which basically consist only of small separators. So the different gadgets in the graph will have to communicate with each other via some signals which are extraneous to the small separators between them, because each separator is small and so cannot encode much information itself. In this reduction we realized the signal via the number of paths we can route through a gadget. More concretely, we reduce from the problem of finding a clique in a graph $H$, we assign each vertex in H some number, and the vertex-selection gadget allows us to route some number of paths without sharing much edges if and only this number was assigned to some vertex of $H$.

After constructing the vertex-selection gadgets, we need to verify that the vertices selected in different gadgets correspond to neighboring vertices. That’s where Golomb rulers come in: A Golomb ruler is a set of nonnegative integers such that each sum (and, equivalently, difference) of two integers in the set is unique. It is easy to see that any subset of $1, 2, 4, 8, 16, ...$ is a Golomb ruler. It is a bit harder to see that, if we want to have a Golomb ruler with $m$ integers, say, then there is one whose largest integer is roughly $m^3$. And what’s more: such a ruler can be computed in polynomial time [1].

It turns out that there is some gadget which has two inputs, and through which we can route specific numbers of routes $a$ and $b$ through the two inputs if and only if $a + b$ is contained in some pre-specified set. Thus, all that was left to make sure that each pair of selected vertices are adjacent was the following: Select the numbers that represent vertices according to some Golomb ruler and make an edge-verification gadget for each pair of vertices with the two inputs above, that only allowed numbers $a + b$ which correspond to an edge between two vertices. Since the vertex numbers correspond to a Golomb ruler, any sum of two numbers will uniquely correspond to an edge or nonedge. Read the full details here: [2].

A more general structure, captured by so-called $B_k$-sets, has previously been used to show that in the classical Bin Packing problem, a running time with exponential dependency on the number of bins is unavoidable [3]. Golomb rulers have later also been used to show hardness for a Subset Sum-type problem, i.e. checking whether a subset of a given set of mathematical objects sums up to a given target [4].

1. Analysis of the Golomb Ruler and the Sidon Set Problems, and Determination of Large, Near-Optimal Golomb Rulers, Dimitromanolakis, A. (2002).
2. The Parameterized Complexity of the Minimum Shared Edges Problem, Fluschnik, T., Kratsch, S., Niedermeier, R., Sorge, M. Journal of Computer and System Sciences. 106, 23–46 (2019).
3. Bin Packing with Fixed Number of Bins Revisited, Jansen, K., Kratsch, S., Marx, D., Schlotter, I. Journal of Computer and System Sciences. 79, 39–49 (2013).
4. On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem, Ganian, R., Klute, F., Ordyniak, S. In: Niedermeier, R. and Vallée, B. (eds.) 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). pp. 33:1–33:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018).