The call for papers for WG 2014 is out.

Let me say that I really like the WG series. Not only because WG'08 was my first conference (and now WG'14 the first one I'm in a PC), but mainly because there is always a nice bunch of papers with cute combinatorics, and you always travel back home from WG with a full sack of cool open problems to think on.

Speaking of these, I went through my private "open problem list" and found a few problems that, in my opinion, may nicely suit WG. Hey, there are still a few months till the deadline, so why not solve some of the problems and go for a trip to this lovely castle in France?

The problems are from parameterized complexity, since I mostly work in this area. To the best of my knowledge, there are currently open. On all of them I spent some significant time somewhere in the past.

Maybe a small disclaimer is in place: although I found these problems interesting and nice, the techniques to solve them may turn out to be boring, other PC members of WG 2014 may have different opinions on their importance, etc. So, in any sense you should not treat this as some promise that a solution will get into WG. I just wanted to inspire some research, and see solutions to some nice problems I thought about and didn't succeed, and that is the sole motivation for this post 🙂

Cutting short paths. In this paper the authors study (among others) the following problem: given a (directed or undirected) graph with source and sink , and integers and , cut at most edges of so that a shortest path from to is of length larger than . They show an FPT algorithm, parameterized by both and . The question is: does this problem admit a polynomial kernel with respect to this parameterization?

Constrained bipartite vertex cover. The minimum vertex cover problem in bipartite graphs is solvable in polynomial time. What about the following variant: given a bipartite graph with fixed bipartition , and integers and , find a vertex cover of the graph with at most vertices in and vertices in . This is NP-hard. There is a simple reduction rule: a vertex from of degree larger than needs to be included in a solution, and symmetrically the same holds for a vertex in of degree larger than . After this reduction is exhaustively applied, note that a solution may cover at most edges, so we have a kernel of this size. Can you do better with respect to the number of vertices in the kernel? The classical vertex cover problem in arbitrary graphs has a kernel with linear number of vertices.

Imbalance minimization. Given an undirected graph , and an ordering of its vertices, the imbalance of in this ordering equals

that is, the absolute value of the difference between the number of neighbours of before and after in the ordering. The imbalance of the ordering is the sum of the imbalances of all vertices. Here the authors prove that the problem of finding an ordering of imbalance at most , parameterized by , is FPT. Does this problem admit a polynomial kernel?

Max-leaf outbranching, parameterized by treewidth. In a directed graph, an outbranching is a subgraph that is a rooted tree, where each arc is directed downwards. In the max-leaf outbranching problem we seek for an outbranching in the given graph with maximum number of leaves. We are interested in solving this problem, when we are given a tree decomposition of of width , that is, we study treewidth DPs. Here we have shown an -time randomized algorithm, but we could not get a matching lower bound (as we did for most other problems studied there). Is the optimal base of the exponent? (Of course, assuming Strong ETH). Or maybe you can do better?