Cheap balanced separator conjecture for graphs with polynomial expansion

About 6 years old · traced to

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 t≥1t\geq 1 and q≥0q\geq 0, a set C⊆V(G)C\subseteq V(G) is (ρ/t)(\rho/t)-cheap with qq outliers if there is a set C′⊆CC'\subseteq C with ∣C′∣≤q|C'|\leq q and

ρ(C∖C′)≤ρ(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:N→Nq:\mathbb{N}\to\mathbb{N} such that, for every graph GG with expansion bounded by pp and every cost assignment ρ\rho, each integer t≥1t\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.

References

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.