Open problems

Here is a list of some open problems that I like. It is not a complete list by any means, for example, it misses many obvious problems, such as "Can treewidth be computed exactly in \(2^{O(k)} n\) time." See also the last chapter of my PhD thesis for additional open problems.

1. Complexity of independent set on graphs excluding grid induced minor

A graph \(G\) contains a graph \(H\) as an induced minor if \(H\) can be obtained from \(G\) by vertex deletions and edge contractions. Let \(\mathcal{C}_k\) be the class of graphs that do not contain the \(k \times k\)-grid as an induced minor. Is the maximum independent set problem polynomial-time solvable on \(\mathcal{C}_k\) for every constant \(k\)? Or quasipolynomial-time solvable?

(This was asked by Clément Dallard, Martin Milanič, and Kenny Štorgel in https://arxiv.org/abs/2111.04543v1. It has also been asked by Peter Gartland and Daniel Lokshtanov.)

2. ETH lower bound for computing treewidth

It follows from known reductions that assuming the Exponential Time Hypothesis (ETH), the treewidth of an \(n\)-vertex graph cannot be computed in time \(2^{o(\sqrt{n})}\). Can this lower bound be improved to \(2^{o(n)}\)?

Update: Solved by Édouard Bonnet https://arxiv.org/abs/2406.11628.

3. Dynamic treewidth in polylogarithmic time

In https://arxiv.org/abs/2304.01744 we gave an amortized subpolynomial-time algorithm for maintaining tree decompositions of bounded width in the fully dynamic setting. Can this be improved to amortized polylogarithmic time?

Update: Solved by me https://arxiv.org/abs/2504.02790.

4. Can dynamic programming for independent set be automated?

Many dynamic programming algorithms for the maximum weight independent set problem (MWIS) compute the answer by only using the \(max\) and \(+\) operations on the weights, and using them in an order that depends only on the graph, not on the weights. This kind of structure for a graph \(G\) is called a tropical circuit for MWIS on the graph \(G\), see https://arxiv.org/abs/2102.06901. Let \(\tau(G)\) denote the size of a smallest tropical circuit for MWIS on \(G\). Given a weighted graph \(G\) as an input, can we solve MWIS in (quasi)polynomial time in \(\tau(G)\)?

5. Single-exponential time algorithms parameterized by clique-width without \(k\)-expression

When a \(k\)-expression witnessing that a graph has clique-width at most \(k\) is given, many NP-hard graph problems can be solved in time \(2^{O(k)} n^{O(1)}\). Can we obtain such algorithms parameterized by clique-width without the assumption that a \(k\)-expression is given as an input? Oum, Sæther, and Vatshelle gave \(2^{O(k \log k)} n^{O(1)}\) time algorithms in https://arxiv.org/abs/1311.0224.