论文标题
列表同构问题的细粒度复杂性：反馈顶点集和切口
Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth
论文作者
论文摘要
对于图形，$ g，h $，从$ g $到$ h $的同态性是一个边缘保存映射，从$ v（g）$到$ v（h）$。在由\ textsc {lhom}（$ h $）表示的同构问题的列表中，我们获得了一个图形$ g $，并列出了$ l：v（g）\ to 2^{v（h）} $，我们要求从$ g $到$ h $的同型同性恋，这是$ h $ coss the $ h $。 最近，Okrasa，Pigiyk和Rzą梦Ski [ESA 2020]定义了一个不变的$ i^*（h）$，并在Seth $ \ Mathcal {o}^*\ left（i^**（i^*（i^*（h）由treewidth $ \ textrm {tw}（g）的参数化，实例图$ g $。我们研究了在远程参数化下问题的复杂性。作为第一个结果，我们表明，如果参数是$ g $的最小反馈顶点集的大小，则$ i^*（h）$也是正确的复杂性基础。 然后，我们将注意力转移到$ g $的Cutwidth $ \ textrm {ctw}（g）$的参数化上。 Jansen和Nederlof〜 [ESA 2018]表明\ textsc {list $ k $ -coloring}（即，可以在时间$ \ mathcal {o}^*\ left（c^\ wher（c^{cttrm {cttwherm）中，可以在时间$ \ mathcal {O}^{ $ k $。詹森（Jansen）问这种行为是否扩展到图形同构。作为论文的主要结果，我们以负面的方式回答这个问题。我们定义了一个新图不变$ mim^*（h）$，并证明\ textsc {lhom}（$ h $）问题无法在时间$ \ mathcal {o}^*\ left（（mim^**（h） - \ varepsilon）^{\ varepsilon）^{\ textrm {除非塞思失败。这意味着没有$ c $，因此对于每个奇数循环，问题的非列表版本都可以在时间$ \ mathcal {o}^*\ left（c^{\ textrm {ctw}（g）}（g）} \ right）$中解决。 最后，我们概括了Jansen和Nederlof的算法，因此可以使用每个图$ H $来求解\ textsc {lhom}（$ h $）;它的复杂性取决于$ \ textrm {ctw}（g）$和$ h $的另一个不变性，这对于集团来说是恒定的。
For graphs $G,H$, a homomorphism from $G$ to $H$ is an edge-preserving mapping from $V(G)$ to $V(H)$. In the list homomorphism problem, denoted by \textsc{LHom}($H$), we are given a graph $G$ and lists $L: V(G) \to 2^{V(H)}$, and we ask for a homomorphism from $G$ to $H$ which additionally respects the lists $L$. Very recently Okrasa, Piecyk, and Rzążewski [ESA 2020] defined an invariant $i^*(H)$ and proved that under the SETH $\mathcal{O}^*\left (i^*(H)^{\textrm{tw}(G)}\right)$ is the tight complexity bound for \textsc{LHom}($H$), parameterized by the treewidth $\textrm{tw}(G)$ of the instance graph $G$. We study the complexity of the problem under dirretent parameterizations. As the first result, we show that $i^*(H)$ is also the right complexity base if the parameter is the size of a minimum feedback vertex set of $G$. Then we turn our attention to a parameterization by the cutwidth $\textrm{ctw}(G)$ of $G$. Jansen and Nederlof~[ESA 2018] showed that \textsc{List $k$-Coloring} (i.e., \textsc{LHom}($K_k$)) can be solved in time $\mathcal{O}^*\left (c^{\textrm{ctw}(G)}\right)$ where $c$ does not depend on $k$. Jansen asked if this behavior extends to graph homomorphisms. As the main result of the paper, we answer the question in the negative. We define a new graph invariant $mim^*(H)$ and prove that \textsc{LHom}($H$) problem cannot be solved in time $\mathcal{O}^*\left ((mim^*(H)-\varepsilon)^{\textrm{ctw}(G)}\right)$ for any $\varepsilon >0$, unless the SETH fails. This implies that there is no $c$, such that for every odd cycle the non-list version of the problem can be solved in time $\mathcal{O}^*\left (c^{\textrm{ctw}(G)} \right)$. Finally, we generalize the algorithm of Jansen and Nederlof, so that it can be used to solve \textsc{LHom}($H$) for every graph $H$; its complexity depends on $\textrm{ctw}(G)$ and another invariant of $H$, which is constant for cliques.
