# 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 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)}$$?

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

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