Open problems

Here is an incomplete list of open problems that I like.

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 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)}\)?

3. Dynamic treewidth in polylogarithmic time

In 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?

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 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