Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Counting Homomorphic Cycles in Degenerate Graphs

Counting Homomorphic Cycles in Degenerate Graphs Since counting subgraphs in general graphs is, by and large, a computationally demanding problem, it is natural to try and design fast algorithms for restricted families of graphs. One such family that has been extensively studied is that of graphs of bounded degeneracy (e.g., planar graphs). This line of work, which started in the early 80’s, culminated in a recent work of Gishboliner et al., which highlighted the importance of the task of counting homomorphic copies of cycles (i.e., cyclic walks) in graphs of bounded degeneracy.Our main result in this paper is a surprisingly tight relation between the above task and the well-studied problem of detecting (standard) copies of directed cycles in general directed graphs. More precisely, we prove the following:One can compute the number of homomorphic copies of C2k and C2k+1 in n-vertex graphs of bounded degeneracy in time Õ(ndk), where the fastest known algorithm for detecting directed copies of Ck in general m-edge digraphs runs in time Õ(mdk).Conversely, one can transform any O(nbk) algorithm for computing the number of homomorphic copies of C2k or of C2k+1 in n-vertex graphs of bounded degeneracy, into an Õ(mbk) time algorithm for detecting directed copies of Ck in general m-edge digraphs.We emphasize that our first result does not use a black-box reduction (as opposed to the second result which does). Instead, we design an algorithm for computing the number of Ck-homomorphisms in degenerate graphs and show that one part of its analysis can be reduced to the analysis of the fastest known algorithm for detecting directed cycles in general digraphs, which was carried out in a recent breakthrough of Dalirrooyfard, Vuong and Vassilevska Williams. As a by-product of our algorithm, we obtain a new algorithm for detecting k-cycles in directed and undirected graphs of bounded degeneracy that is faster than all previously known algorithms for 7 ≤ k ≤ 11, and faster for all k ≥ 7 if the matrix multiplication exponent is 2. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Counting Homomorphic Cycles in Degenerate Graphs

Download PDF
22 pages

Loading next page...
 
/lp/association-for-computing-machinery/counting-homomorphic-cycles-in-degenerate-graphs-PVjPZjN8iw
Publisher
Association for Computing Machinery
Copyright
Copyright © 2023 Association for Computing Machinery.
ISSN
1549-6325
eISSN
1549-6333
DOI
10.1145/3560820
Publisher site
See Article on Publisher Site

Abstract

Since counting subgraphs in general graphs is, by and large, a computationally demanding problem, it is natural to try and design fast algorithms for restricted families of graphs. One such family that has been extensively studied is that of graphs of bounded degeneracy (e.g., planar graphs). This line of work, which started in the early 80’s, culminated in a recent work of Gishboliner et al., which highlighted the importance of the task of counting homomorphic copies of cycles (i.e., cyclic walks) in graphs of bounded degeneracy.Our main result in this paper is a surprisingly tight relation between the above task and the well-studied problem of detecting (standard) copies of directed cycles in general directed graphs. More precisely, we prove the following:One can compute the number of homomorphic copies of C2k and C2k+1 in n-vertex graphs of bounded degeneracy in time Õ(ndk), where the fastest known algorithm for detecting directed copies of Ck in general m-edge digraphs runs in time Õ(mdk).Conversely, one can transform any O(nbk) algorithm for computing the number of homomorphic copies of C2k or of C2k+1 in n-vertex graphs of bounded degeneracy, into an Õ(mbk) time algorithm for detecting directed copies of Ck in general m-edge digraphs.We emphasize that our first result does not use a black-box reduction (as opposed to the second result which does). Instead, we design an algorithm for computing the number of Ck-homomorphisms in degenerate graphs and show that one part of its analysis can be reduced to the analysis of the fastest known algorithm for detecting directed cycles in general digraphs, which was carried out in a recent breakthrough of Dalirrooyfard, Vuong and Vassilevska Williams. As a by-product of our algorithm, we obtain a new algorithm for detecting k-cycles in directed and undirected graphs of bounded degeneracy that is faster than all previously known algorithms for 7 ≤ k ≤ 11, and faster for all k ≥ 7 if the matrix multiplication exponent is 2.

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Feb 20, 2023

Keywords: Subgraph counting

References

  • Popular conjectures imply strong lower bounds for dynamic problems
    [,
  • A refined laser method and faster matrix multiplication
    [,
  • Color-coding
    [,
  • Finding and counting given length cycles
    [,
  • Emergence of scaling in random networks
    [,
  • Counting subgraphs in degenerate graphs
    [,
  • Linear time subgraph counting, graph degeneracy, and the chasm at size six
    [,
  • Near-linear time homomorphism counting in bounded degeneracy graphs: the barrier of long induced cycles
    [,
  • On generalized graphs
    [,
  • Faster algorithms for counting subgraphs in sparse graphs
    [,
  • Arboricity and subgraph listing algorithms
    [,
  • Homomorphisms are a good basis for counting small subgraphs
    [,
  • Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts
    [,
  • Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles
    [,
  • The complexity of counting homomorphisms seen from the other side
    [,
  • Detecting directed 4-cycles still faster
    [,
  • Strong independence of graphcopy functions
    [,
  • The parameterized complexity of counting problems
    [,
  • The complexity of homomorphism and constraint satisfaction problems seen from the other side
    [,
  • Fast rectangular matrix multiplication and applications
    [,
  • Finding a minimum circuit in a graph
    [,
  • Tight hardness for shortest cycles and paths in sparse graphs
    [,
  • Powers of tensors and fast matrix multiplication
    [,
  • Large networks and graph limits
    [,
  • Can you beat treewidth?
    [,
  • Smallest-last ordering and clustering and graph coloring algorithms
    [,
  • The challenges of unbounded treewidth in parameterised subgraph counting problems
    [,
  • Network motifs: Simple building blocks of complex networks
    [,
  • How to find long paths efficiently
    [,
  • In Sparsity: Graphs, Structures, and Algorithms, Vol
    [,
  • On the complexity of the subgraph problem
    [,
  • Biological network comparison using graphlet degree distribution
    [,
  • Computational Complexity Theory, Vol
    [,
  • Efficient algorithms for clique problems
    [,
  • Multiplying matrices faster than Coppersmith-Winograd
    [,
  • Finding, minimizing, and counting weighted subgraphs
    [,
  • Finding heaviest \(H\) -subgraphs in real weighted graphs, with applications
    [,
  • Detecting short directed cycles using rectangular matrix multiplication and dynamic programming
    [,
  • Finding even cycles even faster
    [,