论文标题
在$ c _ {> t} $中查找大型诱导的稀疏子图 - quasipolynomial时间的免费图形
Finding large induced sparse subgraphs in $C_{>t}$-free graphs in quasipolynomial time
论文作者
论文摘要
对于整数$ t $，如果$ g $不包含超过〜$ t $ pertices的任何诱导周期，则将图$ g $称为{\ em {$ c _ {> t} $ - free}}。我们证明了以下陈述：对于每对整数$ d $和$ t $和a cmso $ _2 $语句〜$ ϕ $，存在一种算法，给定一个$ n $ vertex $ c _ {> t} $ - time $ n^$ n^$ n^4 n n n^4 n n n^4 n） $ g [s] $最多有$ d $，并且满足$ ϕ $。可以将运行时间提高到$ n^{o（\ log^2 n）} $，假设$ g $是$ p_t $ - free，即，$ g $不包含$ t $ dertices上的诱导路径。这扩展了作者在{\ sc {sc {最大重量独立套件}}问题上的最新结果[将出现在2020和SOSA 2021]上，这是两个方向上$ p_t $ - free图上的问题：通过涵盖$ c _ {> t} $的更通用的范围，以及最大程度地{或{\ sc {最大权重诱导平面图}}。
For an integer $t$, a graph $G$ is called {\em{$C_{>t}$-free}} if $G$ does not contain any induced cycle on more than~$t$ vertices. We prove the following statement: for every pair of integers $d$ and $t$ and a CMSO$_2$ statement~$ϕ$, there exists an algorithm that, given an $n$-vertex $C_{>t}$-free graph $G$ with weights on vertices, finds in time $n^{O(\log^4 n)}$ a maximum-weight vertex subset $S$ such that $G[S]$ has degeneracy at most $d$ and satisfies $ϕ$. The running time can be improved to $n^{O(\log^2 n)}$ assuming $G$ is $P_t$-free, that is, $G$ does not contain an induced path on $t$ vertices. This expands the recent results of the authors [to appear at FOCS 2020 and SOSA 2021] on the {\sc{Maximum Weight Independent Set}} problem on $P_t$-free graphs in two directions: by encompassing the more general setting of $C_{>t}$-free graphs, and by being applicable to a much wider variety of problems, such as {\sc{Maximum Weight Induced Forest}} or {\sc{Maximum Weight Induced Planar Graph}}.
