Finding vertex-surjective graph homomorphisms

被引:0
作者
Petr A. Golovach
Bernard Lidický
Barnaby Martin
Daniël Paulusma
机构
[1] Durham University,Science Laboratories, School of Engineering and Computing Sciences
[2] Charles University,Faculty of Mathematics and Physics
[3] University of Illinois,Department of Mathematics
来源
Acta Informatica | 2012年 / 49卷
关键词
Complete Graph; Vertex Cover; Hamiltonian Path; Tree Decomposition; Graph Class;
D O I
暂无
中图分类号
学科分类号
摘要
The Surjective Homomorphism problem is to test whether a given graph G called the guest graph allows a vertex-surjective homomorphism to some other given graph H called the host graph. The bijective and injective homomorphism problems can be formulated in terms of spanning subgraphs and subgraphs, and as such their computational complexity has been extensively studied. What about the surjective variant? Because this problem is NP-complete in general, we restrict the guest and the host graph to belong to graph classes \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal G}}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal H}}$$\end{document}, respectively. We determine to what extent a certain choice of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal G}}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal H}}$$\end{document} influences its computational complexity. We observe that the problem is polynomial-time solvable if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal H}}$$\end{document} is the class of paths, whereas it is NP-complete if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal G}}$$\end{document} is the class of paths. Moreover, we show that the problem is even NP-complete on many other elementary graph classes, namely linear forests, unions of complete graphs, cographs, proper interval graphs, split graphs and trees of pathwidth at most 2. In contrast, we prove that the problem is fixed-parameter tractable in k if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal G}}$$\end{document} is the class of trees and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal H}}$$\end{document} is the class of trees with at most k leaves, or if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal G}}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal H}}$$\end{document} are equal to the class of graphs with vertex cover number at most k.
引用
收藏
页码:381 / 394
页数:13
相关论文
共 25 条
[1]  
Bodirsky M.(2012)The complexity of surjective homomorphism problems—a survey Discrete Appl. Math. 160 1680-1690
[2]  
Kára J.(2000)Upper bounds to the clique width of graphs Discrete Appl. Math. 101 77-114
[3]  
Martin B.(2010)Retractions to pseudoforests SIAM J. Discrete Math. 24 101-112
[4]  
Courcelle B.(2008)Locally constrained graph homomorphisms—structure, complexity, and applications Comput. Sci. Rev. 2 97-111
[5]  
Olariu S.(2011)Parameterized complexity of coloring problems: treewidth versus vertex cover Theor. Comput. Sci. 412 2513-2523
[6]  
Feder T.(2005)A complete complexity classification of the role assignment problem Theor. Comput. Sci. 349 67-81
[7]  
Hell P.(1987)An application of simultaneous diophantine approximation in combinatorial optimization Combinatorica 7 49-65
[8]  
Jonsson P.(1990)On the complexity of J. Comb. Theory Ser. B 48 92-110
[9]  
Krokhin A.(1983)-colouring Math. Oper. Res. 8 538-548
[10]  
Nordh G.(2002)Integer programming with a fixed number of variables SIAM J. Comput. 32 253-280