Publications

2026

• Induced-Minor-Closed Classes have Linear, Square-Root, or Sub-Polynomial Tree-Independence Submitted SODA

  with Maria Chudnovsky, Julien Codsi, and Daniel Lokshtanov

  [tl;dr] · [paper]

  We classify induced-minor-closed graph classes by tree-independence number. Classes containing K_t,t and W_t×t as induced minors for every t need linear tree-independence; classes forbidding K_t,t for some t have square-root tree-independence; and classes forbidding both K_t,t and W_t×t for some t have sub-polynomial tree-independence — this last bound is our main contribution. The bound yields 2^no(1)-time algorithms for many problems on {K_t,t, W_t×t}-induced minor free graphs, and partially resolves a conjecture of Chudnovsky, E S, and Lokshtanov [arXiv, 2025].

• Induced Minors and Coarse Tree Decompositions Submitted JGT

  with Maria Chudnovsky, Julien Codsi, and Daniel Lokshtanov

  [tl;dr] · [paper]

  We show that graphs forbidding both K_t,t and a wall W_t×t as induced minors, for some t, have a tree decomposition in which every bag has poly-logarithmic distance-16(log n)-independence number, along with a tree decomposition in which every bag has sub-polynomial distance-8-independence number. These are relaxations of a conjecture of Chudnovsky, E S, and Lokshtanov [arXiv, 2025]. Along the way, we also prove a coarse analogue of Menger's theorem for these graphs.

• (Treewidth, Clique)-Boundedness and Poly-logarithmic Tree-Independence Accepted IJM

  with Maria Chudnovsky and Daniel Lokshtanov

  [tl;dr] · [paper]

  The Dallard–Milanič–Štorgel conjecture proposed that if a hereditary graph class has treewidth bounded by some function of clique number, then it has bounded tree-independence number. This conjecture was recently disproved. We prove a poly-logarithmic variant: treewidth bounded by a polynomial in (clique number × log n) is equivalent to tree-independence number bounded by a poly-logarithmic function of n alone. This retains many of the algorithmic implications of the original conjecture. Along the way, we introduce independence-containers, a generalization of the set of all maximal cliques of a graph, which we believe is of independent interest.

• Parameterized Approximation of Rectangle Stabbing ESA 2026

  with Huairui Chu, Daniel Lokshtanov, Anikait Mundhra, Thomas Schibler,
  Xiaoyang Xu, and Jie Xue

  [tl;dr] · [paper]

  In the Rectangle Stabbing problem, we are given a set of axis-parallel rectangles in the plane and a parameter k, and the goal is to find a set of at most k axis-parallel lines that stab all rectangles. The problem admits a polynomial-time 2-approximation, and under standard complexity assumptions it is unlikely to admit an FPT exact algorithm or an FPT approximation scheme. We give the first parameterized approximation algorithm for Rectangle Stabbing with ratio strictly better than 2: our algorithm computes a solution of size at most 7k/4 in time k^O(k)(|L||R|)^O(1). We complement this with a hardness result showing that, unless FPT = W[1], no parameterized algorithm can achieve a (5/4 − ε)-approximation for any ε > 0.

• A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs SOSA 2026

  with Robert Ganian, Daniel Lokshtanov, Vaishali Surianarayanan

  Mihai Pătrașcu Best Paper Award

  [tl;dr] · [paper] · [slides]

  A graph G is a circle graph if it is an intersection graph of chords of a unit circle. We give an algorithm that takes as input an n-vertex circle graph G, runs in time at most n^{O(log n)}, and finds a proper 3-coloring of G, if one exists. As a consequence, we obtain an algorithm with the same running time to determine whether a given ordered graph (G, ≺) has a 3-page book embedding. This gives a partial resolution to the open problem of Dujmović and Wood (Discret. Math. Theor. Comput. Sci. 2004), Eppstein (2014), and Bachmann, Rutter, and Stumpf (J. Graph Algorithms Appl. 2024) of whether 3-Coloring on circle graphs admits a polynomial-time algorithm.

2025

• Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized SIGMOD 2025

  with Daniel Lokshtanov, Anikait Mundhra, Vaishali Surianarayanan

  [tl;dr] · [paper]

  Many real-world problems, such as database query evaluation and constraint satisfaction, benefit from a low-width hypertree decomposition of the underlying hypergraph, but computing such decompositions efficiently remains hard in practice. We present Ralph, a fast algorithm for computing low-width fractional and generalized hypertree decompositions (and lower bounds on their width), building on the recent polynomial-time approximation algorithm of Korchemna et al. (FOCS 2024) and combining it with practical LP/MILP-based heuristics. On nearly 3700 HyperBench instances, Ralph finds near-optimal decompositions for all previously solved instances and low-width decompositions for all 500 previously unsolved ones, pushing the state of the art.

• Beyond Exact Fairness: Envy-Free Incomplete Connected Fair Division FSTTCS 2025

  with Daniel Lokshtanov

  [tl;dr] · [paper] · [slides]

  We study Envy-Free Incomplete Connected Fair Division, where exactly p vertices of an undirected graph must be allocated to agents so that each agent gets a connected share and envies no one. For agents with additive valuations, we show the problem stays computationally hard when parameterized by p and the number of agents, even for star graphs with unary input numbers, resolving an open problem of Gahlawat and Zehavi (FSTTCS 2023). In stark contrast, tolerating even the slightest amount of envy makes the problem efficient: we give an Efficient Parameterized Approximation Scheme parameterized by p and the number of agent types, working on general graphs and remaining efficient even with binary input numbers.