Counting Homomorphic Cycles in Degenerate Graphs

DOI10.1145/3560820MaRDI QIDQ6051927zbMATH OpenOpenAlexWikidataFDO

Authors Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira, Raphael Yuster

Publication date 23 October 2023

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.05957

zbMATH Keywords

cycle detectioncycle homomorphismsdegeneracysubgraph counting

Mathematics Subject Classification ID

Computer science (68-XX)

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: 1. One can compute the number of homomorphic copies of $C_{2k}$ and $C_{2k+1}$ in $n$-vertex graphs of bounded degeneracy in time $ildeO(n^{d_k})$, where the fastest known algorithm for detecting directed copies of $C_k$ in general $m$-edge digraphs runs in time $ildeO(m^{d_k})$. 2. Conversely, one can transform any $O(n^{b_k})$ algorithm for computing the number of homomorphic copies of $C_{2k}$ or of $C_{2k+1}$ in $n$-vertex graphs of bounded degeneracy, into an $ildeO(m^{b_k})$ time algorithm for detecting directed copies of $C_k$ 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 $C_k$-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.

Cites work

• Arboricity and Subgraph Listing Algorithms
• Can you beat treewidth?
• Color-coding
• Counting Subgraphs in Degenerate Graphs
• Detecting directed 4-cycles still faster
• Detecting short directed cycles using rectangular matrix multiplication and dynamic programming
• Efficient algorithms for clique problems
• Emergence of Scaling in Random Networks
• Fast rectangular matrix multiplication and applications
• Faster algorithms for counting subgraphs in sparse graphs
• Finding a Minimum Circuit in a Graph
• Finding and counting given length cycles
• Finding Even Cycles Even Faster
• Finding heaviest H-subgraphs in real weighted graphs, with applications
• Finding, minimizing, and counting weighted subgraphs
• Graph pattern detection: hardness for all induced patterns and faster non-induced cycles
• Homomorphisms are a good basis for counting small subgraphs
• scientific article; zbMATH DE number 3910446 (Why is no real title available?)
• scientific article; zbMATH DE number 3974318 (Why is no real title available?)
• scientific article; zbMATH DE number 3722700 (Why is no real title available?)
• scientific article; zbMATH DE number 2110413 (Why is no real title available?)
• scientific article; zbMATH DE number 7650386 (Why is no real title available?)
• Large networks and graph limits
• Multiplying matrices faster than coppersmith-winograd
• On generalized graphs
• Powers of tensors and fast matrix multiplication
• Smallest-last ordering and clustering and graph coloring algorithms
• Sparsity. Graphs, structures, and algorithms
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• The complexity of counting homomorphisms seen from the other side
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The Parameterized Complexity of Counting Problems
• Tight hardness for shortest cycles and paths in sparse graphs

Cited in

(4)

• Counting pure \(k\)-cycles in sequences of Cayley graphs
• The complexity of pattern counting in directed graphs, parameterised by the outdegree
• Partition constraints for conjunctive queries: bounds and worst-case optimal joins
• Parameterised holant problems

This page was built for publication: Counting Homomorphic Cycles in Degenerate Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6051927)