On finite reflexive homomorphism-homogeneous binary relational systems

DOI10.1016/J.DISC.2011.07.032MaRDI QIDQ409366zbMATH OpenOpenAlexFDO

Authors Dragan Mašulović, Rajko Nenadov, Nemanja Škorić

Publication date 13 April 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0912.4978

zbMATH Keywords

coNP-completenessfinite digraphshomomorphism-homogeneous relational structures

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Relational systems, laws of composition (08A02) Automorphisms and endomorphisms of algebraic structures (08A35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: 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. Nev{s}etv{r}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 $ightleftarrows$-paths) the problem of deciding whether the system is homomorphism-homogeneous is coNP-complete. Consequently, for this class of relational systems we cannot hope for a description involving a catalogue, where by a catalogue we understand a finite list of polynomially decidable classes of structures. 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 peculiar class of digraphs introduced later in the paper), or an inflation of a digraph whose only connected components are $C_3^{c}irc$ and $1^{c}irc$.

Review text

The notion of homomorphism-homogeneity was introduced in [\textit{P. J. Cameron} and \textit{J. Nešetřil}, Comb. Probab. Comput. 15, No. 1--2, 91--103 (2006; Zbl 1091.08001)] as a relaxed version of homogeneity. The aim of this paper is to contribute to the work on the classification of homomorphism-homogeneous relational structures. In particular, the authors consider finite homomorphism-homogeneous relational systems with one reflexive binary relation. Among them are so-called bidirectionally connected digraphs of special interest. It turns out that the problem of deciding their homomorphism-homogeneity is coNP-complete. On the other hand, it is possible to characterize homomorphism-homogenous bidirectionally disconnected digraphs. This characterization is also the main result of this paper.

Recommendations

• Towards finite homomorphism-homogeneous relational structures
• Finite irreflexive homomorphism-homogeneous binary relational systems
• On the complexity of deciding homomorphism-homogeneity for finite algebras
• Connected-homomorphism-homogeneous graphs
• Homomorphism-Homogeneous Relational Structures

Cites work

• Finite homomorphism-homogeneous tournaments with loops
• Finite irreflexive homomorphism-homogeneous binary relational systems
• Homomorphism-homogeneous graphs
• Homomorphism-homogeneous partially ordered sets
• Homomorphism-Homogeneous Relational Structures
• On Subtournaments of a Tournament
• Posets, homomorphisms and homogeneity
• The classification of countable homogeneous directed graphs and countable homogeneous 𝑛-tournaments

Cited in

(12)

• On countable stable structures which are homogeneous for a finite relational language
• On polymorphism-homogeneous relational structures and their clones.
• Towards finite homomorphism-homogeneous relational structures
• Connected-homomorphism-homogeneous graphs
• scientific article; zbMATH DE number 5978026 (Why is no real title available?)
• Finite irreflexive homomorphism-homogeneous binary relational systems
• On the complexity of deciding homomorphism-homogeneity for finite algebras
• Towards the characterization of finite homomorphism-homogeneous oriented graphs with loops
• On a power of $n$-ary relational systems carried by strong homomorphisms
• Homomorphically full reflexive graphs and digraphs
• Towards the classification of polymorphism-homogeneous metric spaces
• Relational systems with trivial endomorphisms and polymorphisms

This page was built for publication: On finite reflexive homomorphism-homogeneous binary relational systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q409366)