On finite reflexive homomorphism-homogeneous binary relational systems

A structure is called homogeneous if every isomorphism between finitely induced substructures of the structure extends to an automorphism of the structure. Recently, P. J. Cameron and J. Nešetřil introduced a relaxed version of homogeneity: we say that a structure is homomorphism-homogeneous if every homomorphism between finitely induced substructures of the structure extends to an endomorphism of the structure.In this paper, we consider finite homomorphism-homogeneous relational systems with one reflexive binary relation. We show that for a large part of such relational systems (bidirectionally connected digraphs; a digraph is bidirectionally connected if each of its connected components can be traversed by ⇄-paths) the problem of deciding whether the system is homomorphism-homogeneous is coNP-complete. Consequently, for this class of relational systems there is no polynomially computable characterization (unless P=NP). On the other hand, in case of bidirectionally disconnected digraphs we present the full characterization. Our main result states that if a digraph is bidirectionally disconnected, then it is homomorphism-homogeneous if and only if it is either a finite homomorphism-homogeneous quasiorder, or an inflation of a homomorphism-homogeneous digraph with involution (a specific class of digraphs introduced later in the paper), or an inflation of a digraph whose only connected components are C3∘ and 1∘.