Search

Correspondence homomorphisms generalize standard homomorphisms as well as correspondence colourings (also known as DP-colourings). For a fixed target graph H , we study the problem of deciding whether an input graph G , with each edge labelled by a pair of permutations of V (H) , admits a homomorphism to H 'corresponding' to the labels. Homomorphisms to H are called H -colourings, and we employ the similar term correspondence H -colourings for correspondence homomorphisms to H. We classify the complexity of this problem as a function of the fixed graph H. It turns out that there is dichotomy — each of the problems is polynomial-time solvable or NP-complete. While most graphs H yield NP-complete problems, there are interesting cases of graphs H for which the problem can be solved in polynomial time by Gaussian elimination. We also classify the complexity of the analogous correspondence list homomorphism problems, and also the complexity of a bipartite version of both problems. We give detailed proofs for the case when H is reflexive, and, for the record, sketch the remaining proofs. [ABSTRACT FROM AUTHOR]

Given a connected graph G and a terminal set R ⊆ V (G) , the Steiner tree problem (STREE) asks for a tree that includes all of R with at most r vertices from V (G) ∖ R , for some integer r ≥ 0. It is known from (Garey et al., 1977) that STREE is NP-complete in general graphs. A Split graph is a graph which can be partitioned into a clique and an independent set. White et al. (1985) have established that STREE in split graphs is NP-complete. In this paper, we present an interesting dichotomy: we show that STREE on K 1 , 4 -free split graphs is polynomial-time solvable, whereas STREE on K 1 , 5 -free split graphs is NP-complete. We investigate K 1 , 4 -free and K 1 , 3 -free (also known as claw-free) split graphs from a structural perspective. Further, using our structural study, we present polynomial-time algorithms for STREE in K 1 , 4 -free and K 1 , 3 -free split graphs. Although, polynomial-time solvability of K 1 , 3 -free split graphs is implied from K 1 , 4 -free split graphs, we wish to highlight our structural observations on K 1 , 3 -free split graphs which may be of use in solving other combinatorial problems. [ABSTRACT FROM AUTHOR]

A tropical graph ( H , c ) consists of a graph H and a (not necessarily proper) vertex-colouring c of H . Given two tropical graphs ( G , c 1 ) and ( H , c ) , a homomorphism of ( G , c 1 ) to ( H , c ) is a standard graph homomorphism of G to H that also preserves the vertex-colours. We initiate the study of the computational complexity of tropical graph homomorphism problems. We consider two settings. First, when the tropical graph ( H , c ) is fixed; this is a problem called ( H , c ) - Colouring . Second, when the colouring of H is part of the input; the associated decision problem is called H - Tropical-Colouring . Each ( H , c ) - Colouring problem is a constraint satisfaction problem (CSP), and we show that a complexity dichotomy for the class of ( H , c ) - Colouring problems holds if and only if the Feder–Vardi Dichotomy Conjecture for CSPs is true. This implies that ( H , c ) - Colouring problems form a rich class of decision problems. On the other hand, we were successful in classifying the complexity of at least certain classes of H - Tropical-Colouring problems. [ABSTRACT FROM AUTHOR]

Abstract: Interval graphs admit linear-time recognition algorithms and have several elegant forbidden structure characterizations. Interval digraphs can also be recognized in polynomial time, and they admit a characterization in terms of incidence matrices. Nevertheless, they do not have a known forbidden structure characterization or low-degree polynomial-time recognition algorithm. We introduce a new class of ‘adjusted interval digraphs’. By contrast, for these digraphs we exhibit a natural forbidden structure characterization, in terms of a novel structure which we call an ‘invertible pair’. Our characterization also yields a low-degree polynomial-time recognition algorithm of adjusted interval digraphs. It turns out that invertible pairs are also useful for undirected interval graphs, and our result yields a new forbidden structure characterization of interval graphs. In fact, it can be shown to be a natural link proving the equivalence of some known characterizations of interval graphs—the theorems of Lekkerkerker and Boland, and of Fulkerson and Gross. In addition, adjusted interval digraphs naturally arise in the context of list homomorphism problems. If is a reflexive undirected graph, the list homomorphism problem LHOM() is polynomial if is an interval graph, and NP-complete otherwise. If is a reflexive digraph, LHOM() is polynomial if is an adjusted interval graph, and we conjecture that it is also NP-complete otherwise. We show that our results imply the conjecture in two important cases. [Copyright &y& Elsevier]

Abstract: Trigraph list homomorphism problems, also known as list matrix partition problems, generalize graph list colouring and digraph list homomorphism problems. While digraph list homomorphism problems enjoy a dichotomy (each problem is -complete or polynomial time solvable), such dichotomy is not necessarily expected for trigraph list homomorphism problems, and in the few cases where dichotomy has been proved, for small trigraphs, the progress has been slow. In this paper, we prove dichotomy for trigraph list homomorphism problems where the underlying graph of the trigraph is a tree. In fact, we show that for these trigraphs the trigraph list homomorphism problem is polynomially equivalent to a related digraph list homomorphism problem. The result can be extended to a larger class of trigraphs, and we illustrate the extension on trigraph cycles. [Copyright &y& Elsevier]

Abstract: For digraphs and , a mapping is a homomorphism of to if implies . For a fixed digraph , the homomorphism problem is to decide whether an input digraph admits a homomorphism to or not, and is denoted as HOM(). An optimization version of the homomorphism problem was motivated by a real-world problem in defence logistics and was introduced in Gutin, Rafiey, Yeo and Tso (2006) . If each vertex is associated with costs , then the cost of the homomorphism is . For each fixed digraph , we have the minimum cost homomorphism problem for and denote it as MinHOM(). The problem is to decide, for an input graph with costs , whether there exists a homomorphism of to and, if one exists, to find one of minimum cost. Although a complete dichotomy classification of the complexity of MinHOM() for a digraph remains an unsolved problem, complete dichotomy classifications for MinHOM() were proved when is a semicomplete digraph Gutin, Rafiey and Yeo (2006) , and a semicomplete multipartite digraph Gutin, Rafiey and Yeo (2008) . In these studies, it is assumed that the digraph is loopless. In this paper, we present a full dichotomy classification for semicomplete digraphs with possible loops, which solves a problem in Gutin and Kim (2008) . [Copyright &y& Elsevier]

Abstract: We have proved in an earlier paper that the complexity of the list homomorphism problem, to a fixed graph , does not change when the input graphs are restricted to have bounded degrees (except in the trivial case when the bound is two). By way of contrast, we show in this paper that the extension problem, again to a fixed graph , can, in some cases, become easier for graphs with bounded degrees. [Copyright &y& Elsevier]

Abstract: Given a graph , let be the minimum integer , if it exists, for which -colouring is -complete when restricted to instances with degree bounded by . We show that exists for any non-bipartite graph. This verifies for graphs the conjecture of Feder, Hell, and Huang that any that is -complete, is -complete for instances of some maximum degree. Furthermore, we show the same for all projective s, and we get constant upper bounds on the parameter for various infinite classes of graph. For example, we show that for any graph with girth at least 7 in which every edge lies in a -cycle, where is the odd-girth of . [Copyright &y& Elsevier]