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:
 10114080
 Date Published:
 Journal Name:
 Leibniz international proceedings in informatics
 ISSN:
 18688969
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Megow, Nicole ; Smith, Adam (Ed.)Maximum weight independent set (MWIS) admits a 1/kapproximation in inductively kindependent graphs [Karhan Akcoglu et al., 2002; Ye and Borodin, 2012] and a 1/(2k)approximation in kperfectly orientable graphs [Kammer and Tholey, 2014]. These are a parameterized class of graphs that generalize kdegenerate graphs, chordal graphs, and intersection graphs of various geometric shapes such as intervals, pseudodisks, and several others [Ye and Borodin, 2012; Kammer and Tholey, 2014]. We consider a generalization of MWIS to a submodular objective. Given a graph G = (V,E) and a nonnegative submodular function f: 2^V → ℝ_+, the goal is to approximately solve max_{S ∈ ℐ_G} f(S) where ℐ_G is the set of independent sets of G. We obtain an Ω(1/k)approximation for this problem in the two mentioned graph classes. The first approach is via the multilinear relaxation framework and a simple contention resolution scheme, and this results in a randomized algorithm with approximation ratio at least 1/e(k+1). This approach also yields parallel (or lowadaptivity) approximations. Motivated by the goal of designing efficient and deterministic algorithms, we describe two other algorithms for inductively kindependent graphs that are inspired by work on streaming algorithms: a preemptive greedy algorithm and a primaldual algorithm. In addition to being simpler and faster, these algorithms, in the monotone submodular case, yield the first deterministic constant factor approximations for various special cases that have been previously considered such as intersection graphs of intervals, disks and pseudodisks.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(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

In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NPhard and hard to approximate within a factor of n1−ε for any ε > 0. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In Hfree graphs, that is, graphs not containing a fixed graph H as an induced subgraph, the problem is known to remain NPhard and APXhard whenever H contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of H is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomialtime solvability results for small graphs H such as P5, P6, the claw, or the fork. We prove that for every such “possibly tractable” graph H there exists an algorithm that, given an Hfree graph G and an accuracy parameter ε > 0, finds an independent set in G of cardinality within a factor of (1 – ε) of the optimum in time exponential in a polynomial of log  V(G)  and ε−1. That is, we show that for every graph H for which Maximum Independent Set is not known to be APXhard in Hfree graphs, the problem admits a quasipolynomial time approximation scheme in this graph class. Our algorithm works also in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set.more » « less