On the Complexity of Graph Covering Problems
On the Complexity of Graph Covering Problems
复制标题
关于图覆盖问题的复杂性
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
J. A. Telle
中科院分区：
文献类型：
--
作者：
Jan Kratochvíl;A. Proskurowski;J. A. Telle
对于一个固定的图H，H-覆盖问题询问输入图G是否允许一个度保持映射f：V（G）→ V（H）使得对于每个G ∈ V（G），f（NG（NG））= NH（f（NG））。在本文中，我们设计有效的算法，某些图覆盖问题根据两个基本技术。第一个是基于部分减少到2-SAT问题。第二种技术利用将图划分为1-因子和2-因子的充分必要条件。对于其他无限类的图覆盖问题，我们通过图着色问题的约化得到了NP-完全性结果。我们说明了这种方法，通过分类的复杂性定义的简单图H至多6顶点的所有H-覆盖问题。
For a fixed graph H, the H-cover problem asks whether an input graph G allows a degree preserving mapping f : V(G) → V(H) such that for every υ ∈ V(G), f(NG(υ)) = NH(f(υ)). In this paper we design efficient algorithms for certain graph covering problems according to two basic techniques. The first is based in part on a reduction to the 2-SAT problem. The second technique exploits necessary and sufficient conditions for the partition of a graph into 1-factors and 2-factors. For other infinite classes of graph covering problems we derive NP- completeness results by reductions from graph coloring problems. We illustrate this methodology by classifying the complexity of all H-cover problems defined by simple graphs H with at most 6 vertices.