Homomorphism Problem and its Approximation Version

Several combinatorial optimization problems can be formulated as a homomorphism problem. The homomorphism problem seeks for a structure-preserving mapping from an input relational structure to a fixed target relational structure. If the target structure is a digraph H with a special combinatorial structure (special ordering) or H has a certain type of polymorphism then the homomorphism problem is polynomial time solvable.

We talk about a forbidden structural characterization of digraphs for which the homomorphism problem is polynomial. In particular digraphs that admit a Min-Max ordering and the digraphs without "digraph asteroidal triple (DAT)" play important rules in the homomorphism problem. The digraphs with Min-Max ordering can be equivalently described by a geometric representation with two inclusion-free families of intervals. The digraphs without DAT admit majority and semilattice polymorphisms.

We talk about an approximation version of the homomorphism problem and we mention some results and open problems.

Event Topic

Networks and Optimization