Complexity of homomorphisms to direct products of graphs |
| |
| Authors: | Judit Bü ki,Csaba Szabó |
| |
| Affiliation: | a Carmelite Convent, Tettye u. 14, H-7625 Pécs, Hungary
b Eötvös Loránd University, Department of Algebra and Number Theory, Kecskeméti u. 10-12, H-1051 Budapest, Hungary |
| |
| Abstract: | For a graph G, OALG asks whether or not an input graph H together with a partial map g:S→G, S⊆V(H), admits a homomorphism f:H→G such that f|S=g. We show that for connected graphs G1, G2, OAL G1×G2 is in P if G1 and G2 are trees and NP-complete otherwise. |
| |
| Keywords: | Computational complexity Graph homomorphism |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
