List homomorphism to irreflexive oriented trees

Author: 
Date created: 
2017-10-17
Identifier: 
etd10418
Keywords: 
Min ordering
List homomorphism problem
Directed asteroid triple (DAT)
Smooth trees
Irreflexive oriented trees
Abstract: 

Min ordering of a digraph $H$ plays an important role in deciding the existence of a list homomorphism to $H$. For reflexive oriented trees $T$, there exists a concrete forbidden induced subgraph characterization to have a min ordering. For irreflexive oriented trees $T$, the existence of a min-ordering turned out to be somewhat harder, as there are many types of obstructions to its existence. In this thesis, we first review the existing results for list homomorphism problems $LHOM(H)$ for digraphs and graphs. Second, for a specific subclass of irreflexive oriented trees, we present a concrete forbidden induced subgraph characterization to have a min ordering and to have an obstruction called invertible pair ($I$-$pair$) and digraph asteroidal triple ($DAT$). Moreover, for this subclass of irreflexive oriented trees $T$, we show that if $T$ contains one of the forbidden obstructions, then the problem $LHOM(T)$ is $NP$-complete, and is polynomial otherwise. Third, we discuss general trees, and present some approaches to find the minimal forbidden obstructions in the general case.

Document type: 
Thesis
Rights: 
This thesis may be printed or downloaded for non-commercial research and scholarly purposes. Copyright remains with the author.
File(s): 
Senior supervisor: 
Pavol Hell
Department: 
Applied Sciences: School of Computing Science
Thesis type: 
(Thesis) M.Sc.
Statistics: