论文标题
列表同态问题的复杂性在遗传图中
Complexity of the list homomorphism problem in hereditary graph classes
论文作者
论文摘要
从图$ g $到图$ h $的同构映射是从$ v（g）$到$ v（h）$的边缘保留映射。对于固定的图形$ h $，在列表同构问题中，由lhom表示（$ h $），我们得到了一个图$ g $，每个顶点$ v $都配备了列表$ l（v）\ subseteq v（h）$。我们询问是否存在从$ g $到$ h $的同构$ f $，其中$ f（v）\ in L（v）$ in V（g）$中的每个$ v \ in l（v）$。费德尔，地狱和黄[JGT〜2003]证明，如果$ h $是双arc-arc-graph，则LHOM（$ h $）是多项式时间溶剂，否则NP完整。 我们对图形中LHOM（$ H $）问题的复杂性感兴趣，不包括一些固定图$ F $的副本作为诱导子图。众所周知，如果$ f $已连接，不是路径，也不是细分的爪子，那么对于每个非BI-ARC图，LHOM（$ H $）问题是NP完整的，除非ETH失败，否则无法在次指定时间内解决。我们考虑连接图$ f $的剩余案例。 如果$ f $是一条路，我们将展示完整的二分法。我们定义了一个名为“ Predious Graphs”的类，并表明如果$ H $不占主导地位，那么对于固定的$ t $，lhom（$ h $）问题都可以在quasi-polynomial时间中解决$ p_t $ - free-free-free图。另一方面，如果$ h $是巨大的，则存在$ t $，因此在$ p_t $ - free-free-free Graphs中无法以次指定时间解决lhom（$ h $）。 如果$ f $是一个细分的爪子，我们在两个重要情况下显示出完整的二分法：对于$ h $具有反射性（即没有循环），对于$ h $，则反射为反射（即每个顶点都有一个循环）。除非ETH失败，否则对于Inreflexive $ h $，LHOM（$ h $）问题可以在图形中以次指数时间解决，当时不包括固定的细分爪，并且仅当$ h $是无预定且无三角形的。如果$ h $是反身的，则每当$ h $不是双arc-arc图时，lhom（$ h $）就无法在次指数时间内解决。
A homomorphism from a graph $G$ to a graph $H$ is an edge-preserving mapping from $V(G)$ to $V(H)$. For a fixed graph $H$, in the list homomorphism problem, denoted by LHom($H$), we are given a graph $G$, whose every vertex $v$ is equipped with a list $L(v) \subseteq V(H)$. We ask if there exists a homomorphism $f$ from $G$ to $H$, in which $f(v) \in L(v)$ for every $v \in V(G)$. Feder, Hell, and Huang [JGT~2003] proved that LHom($H$) is polynomial time-solvable if $H$ is a bi-arc-graph, and NP-complete otherwise. We are interested in the complexity of the LHom($H$) problem in graphs excluding a copy of some fixed graph $F$ as an induced subgraph. It is known that if $F$ is connected and is not a path nor a subdivided claw, then for every non-bi-arc graph the LHom($H$) problem is NP-complete and cannot be solved in subexponential time, unless the ETH fails. We consider the remaining cases for connected graphs $F$. If $F$ is a path, we exhibit a full dichotomy. We define a class called predacious graphs and show that if $H$ is not predacious, then for every fixed $t$ the LHom($H$) problem can be solved in quasi-polynomial time in $P_t$-free graphs. On the other hand, if $H$ is predacious, then there exists $t$, such that LHom($H$) cannot be solved in subexponential time in $P_t$-free graphs. If $F$ is a subdivided claw, we show a full dichotomy in two important cases: for $H$ being irreflexive (i.e., with no loops), and for $H$ being reflexive (i.e., where every vertex has a loop). Unless the ETH fails, for irreflexive $H$ the LHom($H$) problem can be solved in subexponential time in graphs excluding a fixed subdivided claw if and only if $H$ is non-predacious and triangle-free. If $H$ is reflexive, then LHom($H$) cannot be solved in subexponential time whenever $H$ is not a bi-arc graph.
