Twin-width can be exponential in treewidth

Abstract: For any small positive real

v a r e p s i l o n

and integer

t > f r a c 1 v a r e p s i l o n

, we build a graph with a vertex deletion set of size

t

to a tree, and twin-width greater than

2^{(1 - v a r e p s i l o n) t}

. In particular, this shows that the twin-width is sometimes exponential in the treewidth, in the so-called oriented twin-width and grid number, and that adding an apex may multiply the twin-width by at least

2 - v a r e p s i l o n

. Except for the one in oriented twin-width, these lower bounds are essentially tight.

Review text

A trigraph is a graph with some edges colored black, and some colored red. A (vertex) contraction consists of merging two non-necessarily adjacent) vertices, say, \(u, v\) into a vertex \(w\), and keeping every edge \(wz\) black if and only if \(uz\) and \(vz\) were previously black edges. The other edges incident to \(w\) become red (if not already), and the rest of the trigraph remains the same. A contraction sequence of an \(n\)-vertex graph \(G\) is a sequence of trigraphs \(G = G_n, \dots, G_1 = K_1\) such that \(G_i\) is obtained from \(G_{i+1}\) by performing one contraction. A \(d\)-sequence is a contraction sequence in which every vertex of every trigraph has at most \(d\) red edges incident to it. The twin-width of \(G\), denoted by \(tww(G)\), is then the minimum integer \(d\) such that \(G\) admits a \(d\)-sequence. In this paper, the authors obtain the following result: For every real \(0< \varepsilon\leq 1/2\) and integer \(t > 1/\varepsilon\), there is a graph \(G_{t,\varepsilon}\) with a feedback vertex set of size \(t\) and such that \(tww(G_{t,\varepsilon}) > 2^{(1-\varepsilon)t}\). In particular, their result shows that the twin-width is sometimes exponential in the treewidth, in the so-called oriented twin-width and grid number, and that adding an apex may multiply the twin-width by at least \(2-\varepsilon\). Except for the one in oriented twin-width, these lower bounds are essentially tight.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Twin-width can be exponential in treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038574)