The tree-independence number of a graph is the minimum, over all tree-decompositions of the graph, of the maximum size of an independent set contained in a bag. Graph classes of bounded tree-independence number have strong structural and algorithmic properties, but the parameter can be unbounded even in quite restricted classes. In particular, the presence of an induced biclique K_{𝓁,𝓁} forces tree-independence number at least 𝓁. This leads to the question whether large induced bicliques are the only obstruction to bounded tree-independence number in natural hereditary classes. A conjecture of Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht states that for all positive integers t and 𝓁, {P_t,K_{𝓁,𝓁}}-free graphs have bounded tree-independence number. We prove this conjecture for t = 5 by showing that every {P₅,K_{𝓁,𝓁}}-free graph has tree-independence number at most 4𝓁. We also obtain related bounds for the weaker parameter of α-degeneracy.

We prove that given any α-approximation LOCAL algorithm for Minimum Dominating Set (MDS) on planar graphs, we can construct an f(g)-round (3α + 1)-approximation LOCAL algorithm for MDS on graphs embeddable in a given Euler genus-g surface. Heydt et al. [European Journal of Combinatorics (2025)] gave an algorithm with α = 11 + ϵ, from which we derive a (34 + ϵ)-approximation algorithm for graphs of genus g, therefore improving upon the current state of the art of 24g + O(1) due to Amiri et al. [ACM Transactions on Algorithms (2019)]. It also improves the approximation ratio of 91 + ϵ due to Czygrinow et al. [Theoretical Computer Science (2019)] in the particular case of orientable surfaces.

We show that graphs excluding K2,t as a minor admit a f(t)-round 50-approximation deterministic distributed algorithm for Minimum Dominating Set. The result extends to Minimum Vertex Cover. Though fast and approximate distributed algorithms for such problems were already known for H-minor-free graphs, all of them have an approximation ratio depending on the size of H. To the best of our knowledge, this is the first example of a large non-trivial excluded minor leading to fast and constant-approximation distributed algorithms, where the ratio is independent of the size of H. A new key ingredient in the analysis of these distributed algorithms is the use of asymptotic dimension.

A non-crossing spanning tree of a set of points in the plane is a spanning tree whose edges pairwise do not cross. Avis and Fukuda in 1996 proved that there always exists a flip sequence of length at most $2n-4$ between any pair of non-crossing spanning trees (where $n$ denotes the number of points). Hernando et al. proved that the length of a minimal flip sequence can be of length at least $\frac 32 n$. Two recent results of Aichholzer et al. and Bousquet et al. improved the Avis and Fukuda upper bound by proving that there always exists a flip sequence of length respectively at most $2n - \log n$ and $2n - \sqrt{n}$. We improve the upper bound by a linear factor for the first time in 25 years by proving that there always exists a flip sequence between any pair of non-crossing spanning trees $T_1,T_2$ of length at most $c n$ where $c \approx 1.95$. Our result is actually stronger since we prove that, for any two trees $T_1,T_2$, there exists a flip sequence from $T_1$ to $T_2$ of length at most $c |T_1 \setminus T_2|$. We also improve the best lower bound in terms of the symmetric difference by proving that there exists a pair of trees $T_1,T_2$ such that a minimal flip sequence has length $\frac 53 |T_1 \setminus T_2|$, improving the lower bound of Hernando et al. by considering the symmetric difference instead of the number of vertices. We generalize this lower bound construction to non-crossing flips (where we close the gap between upper and lower bounds) and rotations.

A graph is Ok-free if it does not contain k pairwise vertex-disjoint and non-adjacent cycles. We show that MAXIMUM INDEPENDENT SET and 3-COLORING in Ok-free graphs can be solved in quasi-polynomial time. As a main technical result, we establish that “sparse” (here, not containing large complete bipartite graphs as subgraphs) Ok-free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is proven sharp as there is an infinite family of O2-free graphs without K3,3-subgraph and whose treewidth is (at least) logarithmic. Other consequences include that most of the central NP-complete problems (such as MAXIMUM INDEPENDENT SET, MINIMUM VERTEX COVER, MINIMUM DOMINATING SET, MINIMUM COLORING) can be solved in polynomial time in sparse Ok-free graphs, and that deciding the Ok-freeness of sparse graphs is polynomial time solvable. * This work was supported by the ANR projects DISTANCIA (ANR-17-CE40-0015), DIGRAPHS (ANR-19-CE48-0013-01), and TWIN-WIDTH (ANR-21-CE48-0014-01), by the LabEx PERSYVAL-lab (ANR-11-LABX-0025), and by the Vanier Canada Graduate Scholarships program. † The full version of the paper can be accessed at https://arxiv.org/abs/2206.00594

We show that there is a deterministic local algorithm (constant-time distributed graph algorithm) that finds a 5-approximation of a minimum dominating set on outerplanar graphs. We show there is no such algorithm that finds a $(5-\varepsilon)$-approximation, for any $\varepsilon>0$. Our algorithm only requires knowledge of the degree of a vertex and of its neighbors, so that large messages and unique identifiers are not needed.