论文标题
双宽度VIII：描述和双赢
Twin-width VIII: delineation and win-wins
论文作者
论文摘要
我们介绍了描述的概念。如果$ \ Mathcal c $的每个遗传封闭$ \ MATHCAL D $ $ \ MATHCAL C $，则说明$ \ mathcal c $的图形$ \ MATHCAL C $，则认为$ \ Mathcal d $在$ \ Mathcal d $中限制了$ \ Mathcal d $。 An effective strengthening of delineation for a class $\mathcal C$ implies that tractable FO model checking on $\mathcal C$ is perfectly understood: On hereditary closures $\mathcal D$ of subclasses of $\mathcal C$, FO model checking is fixed-parameter tractable (FPT) exactly when $\mathcal D$ has bounded twin-width.有效的图形[BGODMSTT，Stoc '22]和排列图[BKTW，JACM '22]有效地划定了，而亚基图则没有。一方面，我们证明了间隔图，甚至还划定了根的有向路径图。另一方面，我们表明未划定段图，有向路径图和简单多边形的可见性图。为了绘制间隔图（被描绘）和轴平行的两个长度段图（不是不是）之间的描绘前沿（未），我们研究了受限段交叉点类的双宽度。众所周知，（不含三角形的）纯轴平行的单元段图具有无界的双宽度[BGKTW，SODA '21]。我们表明$ k_ {t，t} $ - 免费段图和Axis-Parallel $ h_t $ -Free单元段图具有有限的双宽度，其中$ h_t $是高度$ t $的半读或梯子。相比之下，轴平行$ H_4 $ -Free两长度段图具有无界的双宽度。我们的新结果，结合了用于FO模型的已知FPT算法，以$ O（1）$ - 序列给出的图形进行检查，导致了双赢的参数。例如，我们在1.5D地形的可见性图上为$ k $掠夺的fpt算法和$ k $独立于简单多边形的可见度图中的fpt算法。
We introduce the notion of delineation. A graph class $\mathcal C$ is said delineated if for every hereditary closure $\mathcal D$ of a subclass of $\mathcal C$, it holds that $\mathcal D$ has bounded twin-width if and only if $\mathcal D$ is monadically dependent. An effective strengthening of delineation for a class $\mathcal C$ implies that tractable FO model checking on $\mathcal C$ is perfectly understood: On hereditary closures $\mathcal D$ of subclasses of $\mathcal C$, FO model checking is fixed-parameter tractable (FPT) exactly when $\mathcal D$ has bounded twin-width. Ordered graphs [BGOdMSTT, STOC '22] and permutation graphs [BKTW, JACM '22] are effectively delineated, while subcubic graphs are not. On the one hand, we prove that interval graphs, and even, rooted directed path graphs are delineated. On the other hand, we show that segment graphs, directed path graphs, and visibility graphs of simple polygons are not delineated. In an effort to draw the delineation frontier between interval graphs (that are delineated) and axis-parallel two-lengthed segment graphs (that are not), we investigate the twin-width of restricted segment intersection classes. It was known that (triangle-free) pure axis-parallel unit segment graphs have unbounded twin-width [BGKTW, SODA '21]. We show that $K_{t,t}$-free segment graphs, and axis-parallel $H_t$-free unit segment graphs have bounded twin-width, where $H_t$ is the half-graph or ladder of height $t$. In contrast, axis-parallel $H_4$-free two-lengthed segment graphs have unbounded twin-width. Our new results, combined with the known FPT algorithm for FO model checking on graphs given with $O(1)$-sequences, lead to win-win arguments. For instance, we derive FPT algorithms for $k$-Ladder on visibility graphs of 1.5D terrains, and $k$-Independent Set on visibility graphs of simple polygons.
