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.)
Update: Solved (with a negative answer) by Édouard Bonnet and Yeonsu Chang using GPT-6 Pro. https://arxiv.org/abs/2609.11285. This solution opens up new directions, for example, the problem on graph classes excluding \(K_{t,t}\)-subgraph for a constant \(t\) is still open and interesting.
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?
Update: Solved by me https://arxiv.org/abs/2504.02790.
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.
In https://arxiv.org/abs/2601.04756 we gave a \(2^{O(k^2)} n^{O(1)}\)-time algorithm for computing the branchwidth of a connectivity function represented by an oracle. What is the best possible function \(f\) such that an \(f(k) n^{O(1)}\)-time algorithm exists? Note that the oracle-setting allows proving unconditional lower bounds, for example, it is easy to prove an unconditional information-theoretic lower bound that \(f(k) \le 2^{o(k)}\) is not possible.
Given a dynamic forest undergoing edge insertions and deletions we wish to explicitly maintain an orientation of its edges so that the out-degree of each vertex is upper bounded by a constant. Brodal and Fagerberg [WADS 1999] gave an algorithm with amortized \(O(\log n)\) update time. Can this be improved to sublogarithmic, or can a superconstant lower bounds be proven?
The input is an undirected graph whose edges are labeled with colors (it does not matter if this is a proper coloring or not). The task is to find a cycle with the least number of different colors. We showed in https://arxiv.org/abs/2211.04797 that this problem is quasipolynomial-time solvable. Show either a polynomial-time algorithm, or rule out a polynomial-time algorithm under complexity-theoretic assumptions, such as the ETH.