论文标题
近似于有界双宽度的图表上的高度不适当的问题
Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width
论文作者
论文摘要
对于任何$ \ varepsilon> 0 $，我们给出一个多项式时间$ n^\ varepsilon $ -Approximation算法，用于最大独立设置，以$ O（1）$ - 序列给出有界双宽度的图形。该结果源自以下时间及时折衷：我们建立了一个$ o（1）^{2^q-1} $ - 近似算法在时间$ \ exp（o_q（n^{2^{ - q}}}}}}）$中，对于每个整数$ q \ q \ geqslant 0 $。在同一框架的指导下，我们获得了针对最小着色和最大诱导匹配的相似近似算法。总的来说，所有这些问题都是高度不适合的：对于任何$ \ varepsilon> 0 $，一个多项式时间$ n^{1- \ varepsilon} $ - 对于任何一个中的任何一个都会暗示p $ = $ = $ np [hastad hastad，focs '96; 96; Zuckerman，TOC '07； Chalermsook等人，苏打水'13]。我们将最大独立集的算法和最大感应匹配概括为任何固定连接的图形$ H $的独立（引起）填料。相比之下，我们表明，在$ o（1）$ - 序列的界图上保证了这种近似保证，对于最小独立主导集，序列不太可能，而对于最长的路径和最长的诱导路径，则不太可能有些不可能。关于存在更好近似算法的存在，有一个（非常）的光证明，最大独立集的$ n^\ varepsilon $所获得的近似因子可能是最好的。这是对有限双宽度图中问题的近似性的第一次深入研究。在本文之前，从本质上讲，唯一的结果是〜多项式$ o（1）$ - 最小统治集的近似算法[Bonnet等人，ICALP '21]。
For any $\varepsilon > 0$, we give a polynomial-time $n^\varepsilon$-approximation algorithm for Max Independent Set in graphs of bounded twin-width given with an $O(1)$-sequence. This result is derived from the following time-approximation trade-off: We establish an $O(1)^{2^q-1}$-approximation algorithm running in time $\exp(O_q(n^{2^{-q}}))$, for every integer $q \geqslant 0$. Guided by the same framework, we obtain similar approximation algorithms for Min Coloring and Max Induced Matching. In general graphs, all these problems are known to be highly inapproximable: for any $\varepsilon > 0$, a polynomial-time $n^{1-\varepsilon}$-approximation for any of them would imply that P$=$NP [Hastad, FOCS '96; Zuckerman, ToC '07; Chalermsook et al., SODA '13]. We generalize the algorithms for Max Independent Set and Max Induced Matching to the independent (induced) packing of any fixed connected graph $H$. In contrast, we show that such approximation guarantees on graphs of bounded twin-width given with an $O(1)$-sequence are very unlikely for Min Independent Dominating Set, and somewhat unlikely for Longest Path and Longest Induced Path. Regarding the existence of better approximation algorithms, there is a (very) light evidence that the obtained approximation factor of $n^\varepsilon$ for Max Independent Set may be best possible. This is the first in-depth study of the approximability of problems in graphs of bounded twin-width. Prior to this paper, essentially the only such result was a~polynomial-time $O(1)$-approximation algorithm for Min Dominating Set [Bonnet et al., ICALP '21].
