Publications
2026
-
Induced Minors and Coarse Tree Decompositions Preprint· [paper]
Let G be a graph, S ⊆ V(G) be a vertex set in G and r be a positive integer. The distance r-independence number of S is the size of the largest subset I ⊆ S such that no pair u, v of vertices in I have a path on at most r edges between them in G. It has been conjectured [Chudnovsky et al., arXiv, 2025] that for every positive integer t there exist positive integers c, d such that every graph G that excludes both the complete bipartite graph Kt,t and the grid ⊞t as an induced minor has a tree decomposition in which every bag has (distance 1) independence number at most c(log n)d. We prove a weaker version of this conjecture where every bag of the tree decomposition has distance 16(log n + 1)-independence number at most c(log n)d. On the way we also prove a version of the conjecture where every bag of the decomposition has distance 8-independence number at most 2c (log n)1-(1/d).
-
Parameterized Approximation of Rectangle Stabbing Submitted to ESA· [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 kO(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.
-
(Treewidth, Clique)-Boundedness and Poly-logarithmic Tree-Independence Submitted to IJM· [paper]
An independent set in a graph G is a set of pairwise non-adjacent vertices. A tree decomposition of G is a pair (T, χ) where T is a tree and χ: V(T) → 2V(G) is a function satisfying the following two axioms: for every edge uv in E(G), there is an x in V(T) such that {u, v} ⊆ χ(x), and for every vertex u in V(G), the set {x in V(T) : u in χ(x)} induces a non-empty and connected subtree of T. The sets χ(x) for x in V(T) are called the bags of the tree decomposition. The tree-independence number of G is the minimum, over all tree decompositions of G, of the size of the maximum independent set of the graph induced by a bag of the decomposition.
The study of graph classes with bounded tree-independence number has attracted much attention in recent years, in part due to its important algorithmic implications. A conjecture of Dallard, Milanič, and Storgel, connecting tree-independence number to the classical notion of treewidth, was one of the motivating problems in the area. This conjecture was recently disproved, but here we prove a slight variant that retains much of the algorithmic significance. As part of the proof, we introduce the notion of independence-containers, which can be viewed as a generalization of the set of all maximal cliques of a graph, and is of independent interest.
-
A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs SOSA 2026Mihai Pătrașcu Best Paper Award
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 nO(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· [paper]
Efficient query evaluation in databases and solving constraint satisfaction problems (CSPs) are crucial for improving performance in many real-world applications, from large-scale data management to decision-making systems. These problems naturally admit hypergraph representations, and are efficiently solvable using hypertree decomposition techniques, when the decomposition width is small. However, these techniques require finding small-width decompositions efficiently. This remains a significant challenge despite research from both the database and theory communities.
In this work we present Ralph (Randomized Approximation using Linear Programming for Hypertree-Decompositions), a fast algorithm to compute low width fractional and generalized hypertree decompositions for input hypergraphs, as well as lower bounds for these widths. We build on the recent breakthrough by Korchemna et al. (FOCS 2024), which introduced the first polynomial-time approximation algorithm for fractional (generalized) hypertree width. Our approach combines this theoretical advancement with practical heuristic improvements utilizing (mixed-integer) linear programs. Along the way, we present new algorithms with strong theoretical guarantees. Through empirical evaluation on nearly 3700 instances of HyperBench, a well-established benchmark suite for hypertree decompositions, we find near-optimal decompositions for all previously solved instances and low-width decompositions for all 500 previously unsolved instances, effectively pushing state-of-the-art.
-
Beyond Exact Fairness: Envy-Free Incomplete Connected Fair Division FSTTCS 2025
We study the problem of Envy-Free Incomplete Connected Fair Division, where exactly p vertices of an undirected graph must be allocated to agents such that each agent receives a connected share and does not envy another agent’s share. Focusing on agents with additive valuations, we show that the problem remains computationally hard when parameterized by p and the number of agents. This result holds even for star graphs and with the input numbers given in unary representation, thereby resolving an open problem posed by Gahlawat and Zehavi (FSTTCS 2023).
In stark contrast, we show that if one is willing to tolerate even the slightest amount of envy, then the problem becomes efficient with respect to the natural parameters. Specifically, we design an Efficient Parameterized Approximation Scheme parameterized by p and the number of agent types. Our algorithm works on general graphs and remains efficient even when the input numbers are provided in binary representation.