# Open problems

Here is an incomplete list of open problems that I like. See also the last chapter of my

PhD thesis for additional open problems related to the thesis.

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

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