Homomorphisms to oriented paths
A homomorphism of a digraph \(G= (V, A)\) to a digraph \(H= (V', A')\) is a mapping \(f: V\to V'\) of the vertices of \(G\) to the vertices of \(H\) (not necessarily onto) which preserves arcs, i.e., such that \(xy\in A\) implies \(f(x) f(y)\in A'\). If such a homomorphism exists, \(G\) is said to be homomorphic to \(H\) and the notation \(G\to H\) is used. Otherwise the notation \(G\nrightarrow H\) is used. Given an oriented path \(P\), the authors characterize those digraphs \(G\) which are homomorphic to \(P\). The characterization equates the nonexistence of a homomorphism \(G\to P\) with the existence of a homomorphism \(W\to G\), for some oriented path \(W\) which is not homomorphic to \(P\). This result complements the recent polynomial time algorithm of \textit{W. Gutjahr}, \textit{E. Welzl} and \textit{G. Woeginger} to find such a homomorphism (if one exists) [Polynomial graph-colorings, Discrete Appl. Math. 35, No. 1, 29-45 (1992; Zbl 0761.05040)]. Say that \(H\) has tree-duality if \(G\nrightarrow H\) if and only if there is an oriented tree \(T\) such that \(T\to G\) and \(T\nrightarrow H\). The main result in this paper is that oriented paths have tree-duality. In another recent paper with J. Nešetřil, the authors have proved that whenever \(H\) has tree-duality then there is a polynomial algorithm to test for the existence of homomorphisms to \(H\).
- A Polynomial Algorithm for Homomorphisms to Oriented Cycles
- scientific article; zbMATH DE number 878894
- Complexity of tree homomorphisms
- The Existence of Homomorphisms to Oriented Cycles
- Duality pairs and homomorphisms to oriented and unoriented cycles
- A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
- Publication:4863467
- An algorithm for the number of path homomorphisms
- The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
- Directed path graph isomorphism
- Hereditarily hard \(H\)-colouring problems
- Homomorphisms to oriented cycles
- scientific article; zbMATH DE number 3520447 (Why is no real title available?)
- On classes of relations and graphs determined by subobjects and factorobjects
- On multiplicative graphs and the product conjecture
- On the complexity of colouring by superdigraphs of bipartite graphs
- On the Complexity of Colouring by Vertex-Transitive and Arc-Transitive Digraphs
- On the complexity of H-coloring
- On the complexity of the general coloring problem
- Polynomial graph-colorings
- Some new good characterizations for directed graphs
- Symmetric graphs and interpretations
- The Complexity of Colouring by Semicomplete Digraphs
- The effect of two cycles on the complexity of colourings by directed graphs
- The Existence of Homomorphisms to Oriented Cycles
- A surprising permanence of old motivations (a not-so-rigid story)
- Homomorphisms to oriented cycles
- Homomorphisms to powers of digraphs
- ILP formulation of the degree-constrained minimum spanning hierarchy problem
- Homomorphic preimages of geometric paths
- Hereditarily hard \(H\)-colouring problems
- Complexity of tree homomorphisms
- Duality pairs and homomorphisms to oriented and unoriented cycles
- Graph partitions with prescribed patterns
- Adjoint functors and tree duality
- scientific article; zbMATH DE number 2061631 (Why is no real title available?)
- Homology of Spaces of Directed Paths in Euclidean Pattern Spaces
- The Existence of Homomorphisms to Oriented Cycles
- On homomorphisms to acyclic local tournaments
- A Polynomial Algorithm for Homomorphisms to Oriented Cycles
- scientific article; zbMATH DE number 841621 (Why is no real title available?)
- Path homomorphisms
- Dualities for Constraint Satisfaction Problems
- Learning logic programs with structured background knowledge
- Semidefinite programming and its applications to NP problems
- Orienteering with one endomorphism
- Interleaved adjoints of directed graphs
- Homomorphically full oriented graphs
- Homomorphisms of random paths
This page was built for publication: Homomorphisms to oriented paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1336655)
