On the complexity of counting homomorphisms under surjectivity constraints
<p>Given two graphs G and H, a function h that maps the vertices of G to vertices of H is a (graph) homomorphism if h preserves the edges of G, i.e., whenever two vertices u, v of G share an edge then h(u) and h(v) must share an edge in H. For different H, such homomorphisms represent differen...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2020
|
| Subjects: |
| _version_ | 1817933125592809472 |
|---|---|
| author | Focke, J |
| author2 | Zivny, S |
| author_facet | Zivny, S Focke, J |
| author_sort | Focke, J |
| collection | OXFORD |
| description | <p>Given two graphs G and H, a function h that maps the vertices of G to vertices of H is a (graph) homomorphism if h preserves the edges of G, i.e., whenever two vertices u, v of G share an edge then h(u) and h(v) must share an edge in H. For different H, such homomorphisms represent different structures in G, thereby providing a framework that captures some of the most fundamental combinatorial problems studied in computer science and mathematics. One prominent example is the fact that homomorphisms from a graph G to a triangle (three vertices pairwise connected by edges) correspond to proper 3-colourings of G. </p>
<p>Furthermore, counting homomorphisms has close ties to statistical physics and the computation of partition functions. The complexity of computing and approximating homomorphism counts has therefore drawn a lot of attention over the last four decades. One of the most intriguing open problems in this line of research is determining, for every graph H, the complexity of approximately counting homomorphisms to H. In this thesis, we investigate the complexity of several closely related problems.</p>
<p>Our main objective is to establish complete complexity classifications for large classes of graph homomorphism counting problems. The focus is on counting homomorphisms that satisfy additional properties related to surjectivity. Apart from (unrestricted) homomorphisms, we mainly concentrate on:</p>
<p>- (vertex-)surjective homomorphisms,</p>
<p>- compactions (vertex- and non-loop-edge-surjective homomorphisms),</p>
<p>- retractions (also known as pre-colouring extensions or one-or-all list homomorphisms).</p>
<p>The main contributions of this thesis are as follows:</p>
<p><b>- We give a complete complexity dichotomy for exactly counting surjective homomorphisms.</b> This dichotomy is the same classification that also holds for exactly counting homomorphisms, list homomorphisms and retractions.</p>
<p><b>- We give a complete complexity dichotomy for exactly counting compactions.</b> Notably, this dichotomy is different from the dichotomy for surjective homomorphisms and shows that exactly counting compactions is actually the ``hardest'' of the aforementioned exact counting problems.</p>
<p><b>- We present a collection of approximation-preserving reductions between different homomorphism counting problems. </b>This includes reductions that establish that approximately counting retractions is at least as hard as approximately counting surjective homomorphisms and also at least as hard as approximately counting compactions. In these reductions we use a Monte Carlo sampling algorithm and this appears to be the first time such an approach has been used to obtain approximation-preserving reductions.</p>
<p><b>- We formalise a framework that can be used to generate #BIS-easiness results for approximately counting homomorphisms and retractions.</b> This framework is based on reduction techniques introduced by Dyer, Goldberg, Greenhill and Jerrum.</p>
<p><b>- We give a complete complexity trichotomy for approximately counting retractions to all square-free graphs.</b> As a consequence, we present separations between the problem of approximately counting homomorphisms and that of approximately counting retractions, as well as between the problem of approximately counting retractions and that of approximately counting list homomorphisms.</p>
<p><b>- We present new #BIS-easiness results for approximately counting homomorphisms</b> and thereby settle the complexity of this problem for a rich class of graphs for which it was previously unresolved.</p>
<p><b>- We give a complete complexity dichotomy for counting homomorphisms modulo 2 to all K<sub>4</sub>-minor-free graphs.</b> This confirms a conjecture by Faben and Jerrum for this class of graphs. We use novel global hardness gadgets, which can be used to subsume all previously known classifications. We strengthen the hardness results by ruling out subexponential-time algorithms, assuming rETH.</p> |
| first_indexed | 2024-03-06T22:05:42Z |
| format | Thesis |
| id | oxford-uuid:500fc9c0-00ee-4aa9-8019-c5e19c2759ba |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-12-09T03:48:50Z |
| publishDate | 2020 |
| record_format | dspace |
| spelling | oxford-uuid:500fc9c0-00ee-4aa9-8019-c5e19c2759ba2024-12-08T11:58:38ZOn the complexity of counting homomorphisms under surjectivity constraintsThesishttp://purl.org/coar/resource_type/c_db06uuid:500fc9c0-00ee-4aa9-8019-c5e19c2759baHomomorphisms (Mathematics)Computational complexityEnglishHyrax Deposit2020Focke, JZivny, SGoldberg, L<p>Given two graphs G and H, a function h that maps the vertices of G to vertices of H is a (graph) homomorphism if h preserves the edges of G, i.e., whenever two vertices u, v of G share an edge then h(u) and h(v) must share an edge in H. For different H, such homomorphisms represent different structures in G, thereby providing a framework that captures some of the most fundamental combinatorial problems studied in computer science and mathematics. One prominent example is the fact that homomorphisms from a graph G to a triangle (three vertices pairwise connected by edges) correspond to proper 3-colourings of G. </p> <p>Furthermore, counting homomorphisms has close ties to statistical physics and the computation of partition functions. The complexity of computing and approximating homomorphism counts has therefore drawn a lot of attention over the last four decades. One of the most intriguing open problems in this line of research is determining, for every graph H, the complexity of approximately counting homomorphisms to H. In this thesis, we investigate the complexity of several closely related problems.</p> <p>Our main objective is to establish complete complexity classifications for large classes of graph homomorphism counting problems. The focus is on counting homomorphisms that satisfy additional properties related to surjectivity. Apart from (unrestricted) homomorphisms, we mainly concentrate on:</p> <p>- (vertex-)surjective homomorphisms,</p> <p>- compactions (vertex- and non-loop-edge-surjective homomorphisms),</p> <p>- retractions (also known as pre-colouring extensions or one-or-all list homomorphisms).</p> <p>The main contributions of this thesis are as follows:</p> <p><b>- We give a complete complexity dichotomy for exactly counting surjective homomorphisms.</b> This dichotomy is the same classification that also holds for exactly counting homomorphisms, list homomorphisms and retractions.</p> <p><b>- We give a complete complexity dichotomy for exactly counting compactions.</b> Notably, this dichotomy is different from the dichotomy for surjective homomorphisms and shows that exactly counting compactions is actually the ``hardest'' of the aforementioned exact counting problems.</p> <p><b>- We present a collection of approximation-preserving reductions between different homomorphism counting problems. </b>This includes reductions that establish that approximately counting retractions is at least as hard as approximately counting surjective homomorphisms and also at least as hard as approximately counting compactions. In these reductions we use a Monte Carlo sampling algorithm and this appears to be the first time such an approach has been used to obtain approximation-preserving reductions.</p> <p><b>- We formalise a framework that can be used to generate #BIS-easiness results for approximately counting homomorphisms and retractions.</b> This framework is based on reduction techniques introduced by Dyer, Goldberg, Greenhill and Jerrum.</p> <p><b>- We give a complete complexity trichotomy for approximately counting retractions to all square-free graphs.</b> As a consequence, we present separations between the problem of approximately counting homomorphisms and that of approximately counting retractions, as well as between the problem of approximately counting retractions and that of approximately counting list homomorphisms.</p> <p><b>- We present new #BIS-easiness results for approximately counting homomorphisms</b> and thereby settle the complexity of this problem for a rich class of graphs for which it was previously unresolved.</p> <p><b>- We give a complete complexity dichotomy for counting homomorphisms modulo 2 to all K<sub>4</sub>-minor-free graphs.</b> This confirms a conjecture by Faben and Jerrum for this class of graphs. We use novel global hardness gadgets, which can be used to subsume all previously known classifications. We strengthen the hardness results by ruling out subexponential-time algorithms, assuming rETH.</p> |
| spellingShingle | Homomorphisms (Mathematics) Computational complexity Focke, J On the complexity of counting homomorphisms under surjectivity constraints |
| title | On the complexity of counting homomorphisms under surjectivity constraints |
| title_full | On the complexity of counting homomorphisms under surjectivity constraints |
| title_fullStr | On the complexity of counting homomorphisms under surjectivity constraints |
| title_full_unstemmed | On the complexity of counting homomorphisms under surjectivity constraints |
| title_short | On the complexity of counting homomorphisms under surjectivity constraints |
| title_sort | on the complexity of counting homomorphisms under surjectivity constraints |
| topic | Homomorphisms (Mathematics) Computational complexity |
| work_keys_str_mv | AT fockej onthecomplexityofcountinghomomorphismsundersurjectivityconstraints |