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