Cheap balanced separator conjecture for graphs with polynomial expansion

Let GG be a graph and let pp be a polynomial such that the expansion of GG is bounded by pp. A cost assignment is a function

ρ:V(G)R0+.\rho:V(G)\to\mathbb{R}_0^+.

For integers t1t\geq 1 and q0q\geq 0, a set CV(G)C\subseteq V(G) is (ρ/t)(\rho/t)-cheap with qq outliers if there is a set CCC'\subseteq C with Cq|C'|\leq q and

ρ(CC)ρ(G)/t.\rho(C\setminus C')\leq \rho(G)/t.

Here, a balanced separator is a vertex set whose deletion leaves components satisfying the balance condition used in the paper. Cheap balanced separator conjecture. For every polynomial pp, there exists a function q:NNq:\mathbb{N}\to\mathbb{N} such that, for every graph GG with expansion bounded by pp and every cost assignment ρ\rho, each integer t1t\geq 1 admits a balanced separator that is (ρ/t)(\rho/t)-cheap with q(t)q(t) outliers. This is a weakening of the conjecture that graphs with polynomial expansion are fractionally treewidth-fragile; the conclusion is therefore known for every class known to be fractionally treewidth-fragile, but the stated conjecture is not resolved in general.

Sources & referencesView supporting material

Primary source

Zdeněk Dvořák, “On weighted sublinear separators”, arXiv:2007.11853 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.