Struktura a složitost homomorfismů

Bok, Jan

This thesis is concerned with computational complexity aspects of graph homomorph- isms and related concepts. We are mainly interested in various polynomial time versus NP-complete dichotomies. These results are especially popular thanks to the seminal result of Hell and Nešetřil providing the complexity dichotomy for graph homomorph- ism problems and the recent breakthrough result proving the complexity dichotomy for constraint satisfaction problems. The thesis is divided into three parts, all unified by the common goal to provide complexity classifications of various graph homomorphism problems. The first part is about list homomorphism problems for signed graphs. We study the complexity of such problems and obtain a structural description and dichotomy first for the case of targets being signed trees and then for the so-called separable graphs. The second part focuses on graph covering projections, also known as locally bijective homomorphisms. To the best of our knowledge, we are the first to initiate cataloguing the complexity of the corresponding problems for (mutli)graphs with semi-edges. We have three larger goals here. (1) Providing the complete dichotomy for one- and two- vertex target graphs. (2) Discuss and propose the right definition of graph cover in the case of disconnected targets. (3)...

guest :: login Digital Repository
		Search		Submit		Help		About