Given two (di)graphs G, H and a cost function c:V(G) x V(H) > Q_{>= 0} cup {+infty}, in the minimum cost homomorphism problem, MinHOM(H), we are interested in finding a homomorphism f:V(G)> V(H) (a.k.a Hcoloring) that minimizes sum limits_{v in V(G)}c(v,f(v)). The complexity of exact minimization of this problem is well understood [Pavol Hell and Arash Rafiey, 2012], and the class of digraphs H, for which the MinHOM(H) is polynomial time solvable is a small subset of all digraphs. In this paper, we consider the approximation of MinHOM within a constant factor. In terms of digraphs, MinHOM(H) is not approximable if H contains a digraph asteroidal triple (DAT). We take a major step toward a dichotomy classification of approximable cases. We give a dichotomy classification for approximating the MinHOM(H) when H is a graph (i.e. symmetric digraph). For digraphs, we provide constant factor approximation algorithms for two important classes of digraphs, namely biarc digraphs (digraphs with a conservative semilattice polymorphism or minordering), and karc digraphs (digraphs with an extended minordering). Specifically, we show that:  Dichotomy for Graphs: MinHOM(H) has a 2V(H)approximation algorithm if graph H admits a conservative majority polymorphims (i.e. H is a biarc graph), otherwise, it is inapproximable;  MinHOM(H) has a V(H)^2approximation algorithm if H is a biarc digraph;  MinHOM(H) has a V(H)^2approximation algorithm if H is a karc digraph. In conclusion, we show the importance of these results and provide insights for achieving a dichotomy classification of approximable cases. Our constant factors depend on the size of H. However, the implementation of our algorithms provides a much better approximation ratio. It leaves open to investigate a classification of digraphs H, where MinHOM(H) admits a constant factor approximation algorithm that is independent of V(H).
more »
« less
Toward a Dichotomy for Approximation of HColoring
Given two (di)graphs G, H and a cost function c:V(G) x V(H) > Q_{>= 0} cup {+infty}, in the minimum cost homomorphism problem, MinHOM(H), we are interested in finding a homomorphism f:V(G)> V(H) (a.k.a Hcoloring) that minimizes sum limits_{v in V(G)}c(v,f(v)). The complexity of exact minimization of this problem is well understood [Pavol Hell and Arash Rafiey, 2012], and the class of digraphs H, for which the MinHOM(H) is polynomial time solvable is a small subset of all digraphs. In this paper, we consider the approximation of MinHOM within a constant factor. In terms of digraphs, MinHOM(H) is not approximable if H contains a digraph asteroidal triple (DAT). We take a major step toward a dichotomy classification of approximable cases. We give a dichotomy classification for approximating the MinHOM(H) when H is a graph (i.e. symmetric digraph). For digraphs, we provide constant factor approximation algorithms for two important classes of digraphs, namely biarc digraphs (digraphs with a conservative semilattice polymorphism or minordering), and karc digraphs (digraphs with an extended minordering). Specifically, we show that:  Dichotomy for Graphs: MinHOM(H) has a 2V(H)approximation algorithm if graph H admits a conservative majority polymorphims (i.e. H is a biarc graph), otherwise, it is inapproximable;  MinHOM(H) has a V(H)^2approximation algorithm if H is a biarc digraph;  MinHOM(H) has a V(H)^2approximation algorithm if H is a karc digraph. In conclusion, we show the importance of these results and provide insights for achieving a dichotomy classification of approximable cases. Our constant factors depend on the size of H. However, the implementation of our algorithms provides a much better approximation ratio. It leaves open to investigate a classification of digraphs H, where MinHOM(H) admits a constant factor approximation algorithm that is independent of V(H).
more »
« less
 Award ID(s):
 1751765
 NSFPAR ID:
 10114532
 Date Published:
 Journal Name:
 Leibniz international proceedings in informatics
 ISSN:
 18688969
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


null (Ed.)Counting homomorphisms of a constant sized pattern graph H in an input graph G is a fundamental computational problem. There is a rich history of studying the complexity of this problem, under various constraints on the input G and the pattern H. Given the significance of this problem and the large sizes of modern inputs, we investigate when nearlinear time algorithms are possible. We focus on the case when the input graph has bounded degeneracy, a commonly studied and practically relevant class for homomorphism counting. It is known from previous work that for certain classes of H, Hhomomorphisms can be counted exactly in nearlinear time in bounded degeneracy graphs. Can we precisely characterize the patterns H for which nearlinear time algorithms are possible? We completely resolve this problem, discovering a clean dichotomy using finegrained complexity. Let m denote the number of edges in G. We prove the following: if the largest induced cycle in H has length at most 5, then there is an O(mlogm) algorithm for counting Hhomomorphisms in bounded degeneracy graphs. If the largest induced cycle in H has length at least 6, then (assuming standard finegrained complexity conjectures) there is a constant γ>0, such that there is no o(m1+γ) time algorithm for counting Hhomomorphisms.more » « less

null (Ed.)Counting homomorphisms of a constant sized pattern graph H in an input graph G is a fundamental computational problem. There is a rich history of studying the complexity of this problem, under various constraints on the input G and the pattern H. Given the significance of this problem and the large sizes of modern inputs, we investigate when nearlinear time algorithms are possible. We focus on the case when the input graph has bounded degeneracy, a commonly studied and practically relevant class for homomorphism counting. It is known from previous work that for certain classes of H, Hhomomorphisms can be counted exactly in nearlinear time in bounded degeneracy graphs. Can we precisely characterize the patterns H for which nearlinear time algorithms are possible? We completely resolve this problem, discovering a clean dichotomy using finegrained complexity. Let m denote the number of edges in G. We prove the following: if the largest induced cycle in H has length at most 5, then there is an O(m log m) algorithm for counting Hhomomorphisms in bounded degeneracy graphs. If the largest induced cycle in H has length at least 6, then (assuming standard finegrained complexity conjectures) there is a constant γ > 0, such that there is no o(m1+γ) time algorithm for counting Hhomomorphisms.more » « less

Let $D$ be a simple digraph (directed graph) with vertex set $V(D)$ and arc set $A(D)$ where $n=V(D)$, and each arc is an ordered pair of distinct vertices. If $(v,u) \in A(D)$, then $u$ is considered an \emph{outneighbor} of $v$ in $D$. Initially, we designate each vertex to be either filled or empty. Then, the following color change rule (CCR) is applied: if a filled vertex $v$ has exactly one empty outneighbor $u$, then $u$ will be filled. If all vertices in $V(D)$ are eventually filled under repeated applications of the CCR, then the initial set is called a \emph{zero forcing set} (ZFS); if not, it is a \emph{failed zero forcing set} (FZFS). We introduce the \emph{failed zero forcing number} $\F(D)$ on a digraph, which is the maximum cardinality of any FZFS. The \emph{zero forcing number}, $\Z(D)$, is the minimum cardinality of any ZFS. We characterize digraphs that have $\F(D)<\Z(D)$ and determine $\F(D)$ for several classes of digraphs including de Bruijn and Kautz digraphs. We also characterize digraphs with $\F(D)=n1$, $\F(D)=n2$, and $\F(D)=0$, which leads to a characterization of digraphs in which any vertex is a ZFS. Finally, we show that for any integer $n \geq 3$ and any nonnegative integer $k$ with $k
more » « less 
Let $D=(V,A)$ be a digraph. A vertex set $K\subseteq V$ is a quasikernel of $D$ if $K$ is an independent set in $D$ and for every vertex $v\in V\setminus K$, $v$ is at most distance 2 from $K$. In 1974, Chvátal and Lovász proved that every digraph has a quasikernel. P. L. Erdős and L. A. Székely in 1976 conjectured that if every vertex of $D$ has a positive indegree, then $D$ has a quasikernel of size at most $V/2$. This conjecture is only confirmed for narrow classes of digraphs, such as semicomplete multipartite, quasitransitive, or locally semicomplete digraphs. In this note, we state a similar conjecture for all digraphs, show that the two conjectures are equivalent, and prove that both conjectures hold for a class of digraphs containing all orientations of 4colorable graphs (in particular, of all planar graphs).more » « less