skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights
We consider the complexity of counting weighted graph homomorphisms defined by a symmetric matrix A. Each symmetric matrix A defines a graph homomorphism function Z A (·), also known as the partition function. Dyer and Greenhill [10] established a complexity dichotomy of Z A (·) for symmetric {0, 1}-matrices A, and they further proved that its #P-hardness part also holds for bounded degree graphs. Bulatov and Grohe [4] extended the Dyer-Greenhill dichotomy to nonnegative symmetric matrices A. However, their hardness proof requires graphs of arbitrarily large degree, and whether the bounded degree part of the Dyer-Greenhill dichotomy can be extended has been an open problem for 15 years. We resolve this open problem and prove that for nonnegative symmetric A, either Z A (G) is in polynomial time for all graphs G, or it is #P-hard for bounded degree (and simple) graphs G. We further extend the complexity dichotomy to include nonnegative vertex weights. Additionally, we prove that the #P-hardness part of the dichotomy by Goldberg et al. [12] for Z A (·) also holds for simple graphs, where A is any real symmetric matrix.  more » « less
Award ID(s):
1714275
PAR ID:
10294430
Author(s) / Creator(s):
Editor(s):
Czumaj, Artur Dawar
Date Published:
Journal Name:
47th International Colloquium on Automata, Languages, and Programming
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Iwata, Satoru; Kakimura, Naonori (Ed.)
    We give a new rapid mixing result for a natural random walk on the independent sets of a graph G. We show that when G has bounded treewidth, this random walk - known as the Glauber dynamics for the hardcore model - mixes rapidly for all fixed values of the standard parameter λ > 0, giving a simple alternative to existing sampling algorithms for these structures. We also show rapid mixing for analogous Markov chains on dominating sets, b-edge covers, b-matchings, maximal independent sets, and maximal b-matchings. (For b-matchings, maximal independent sets, and maximal b-matchings we also require bounded degree.) Our results imply simpler alternatives to known algorithms for the sampling and approximate counting problems in these graphs. We prove our results by applying a divide-and-conquer framework we developed in a previous paper, as an alternative to the projection-restriction technique introduced by Jerrum, Son, Tetali, and Vigoda. We extend this prior framework to handle chains for which the application of that framework is not straightforward, strengthening existing results by Dyer, Goldberg, and Jerrum and by Heinrich for the Glauber dynamics on q-colorings of graphs of bounded treewidth and bounded degree. 
    more » « less
  2. (, Symposium on Discrete Algorithms (SODA))
    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 near-linear 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, H-homomorphisms can be counted exactly in near-linear time in bounded degeneracy graphs. Can we precisely characterize the patterns H for which near-linear time algorithms are possible? We completely resolve this problem, discovering a clean dichotomy using fine-grained 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 H-homomorphisms in bounded degeneracy graphs. If the largest induced cycle in H has length at least 6, then (assuming standard fine-grained complexity conjectures) there is a constant γ>0, such that there is no o(m1+γ) time algorithm for counting H-homomorphisms. 
    more » « less
  3. ; ; (, Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms)
    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 near-linear 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, H-homomorphisms can be counted exactly in near-linear time in bounded degeneracy graphs. Can we precisely characterize the patterns H for which near-linear time algorithms are possible? We completely resolve this problem, discovering a clean dichotomy using fine-grained 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 H-homomorphisms in bounded degeneracy graphs. If the largest induced cycle in H has length at least 6, then (assuming standard fine-grained complexity conjectures) there is a constant γ > 0, such that there is no o(m1+γ) time algorithm for counting H-homomorphisms. 
    more » « less
  4. ; ; ; ; (, European Symposium on Algorithms)
    For a graph F, a graph G is F-free if it does not contain an induced subgraph isomorphic to F. For two graphs G and H, an H-coloring of G is a mapping f : V (G) → V (H) such that for every edge uv ∈ E(G) it holds that f(u)f(v) ∈ E(H). We are interested in the complexity of the problem H-Coloring, which asks for the existence of an H-coloring of an input graph G. In particular, we consider H-Coloring of F-free graphs, where F is a fixed graph and H is an odd cycle of length at least 5. This problem is closely related to the well known open problem of determining the complexity of 3-Coloring of Pt-free graphs. We show that for every odd k ≥ 5 the Ck-Coloring problem, even in the precoloring-extension variant, can be solved in polynomial time in P9-free graphs. On the other hand, we prove that the extension version of Ck-Coloring is NP-complete for F-free graphs whenever some component of F is not a subgraph of a subdivided claw. 
    more » « less
  5. ; (, Computational complexity)
    The complexity of graph homomorphism problems has been the subject of intense study for some years. In this paper, we prove a decidable complexity dichotomy theorem for the partition function of directed graph homomorphisms. Our theorem applies to all non-negative weighted forms of the problem: given any fixed matrix A with non-negative algebraic entries, the partition function ZA(G) of directed graph homomorphisms from any directed graph G is either tractable in polynomial time or #P-hard, depending on the matrix A. The proof of the dichotomy theorem is combinatorial, but involves the definition of an infinite family of graph homomorphism problems. The proof of its decidability on the other hand is algebraic and based on properties of polynomials. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email