On coarse tree decompositions and coarse balanced separators

Prelegent(ci)

Jadwiga Czyżewska

Język referatu

angielski

Termin

25 kwietnia 2025 14:15

Pokój

p. 5060

Seminarium

Seminarium "Algorytmika"

---

It is known that there is a linear dependence between the treewidth of a graph and its balanced
separator number: the smallest integer k such that for every weighing of the vertices, the graph
admits a balanced separator of size at most k. We investigate whether this connection can be lifted
to the setting of coarse graph theory, where both the bags of the considered tree decompositions
and the considered separators should be coverable by a bounded number of bounded-radius balls.
As the first result, we prove that if an n-vertex graph G admits balanced separators coverable
by k balls of radius r, then G also admits tree decompositions T1 and T2 such that:
• in T1 , every bag can be covered by O(k log n) balls of radius r; and
• in T2 , every bag can be covered by O(k 2 log k) balls of radius r(log k + log log n + O(1)).
As the second result, we show that if we additionally assume that G has doubling dimension at
most m, then the functional equivalence between the existence of small balanced separators and of
tree decompositions of small width can be fully lifted to the coarse setting.

---