Faster ways to find small patterns in big sparse networks
Faster Algorithms for Finding Small Induced Patterns in Sparse Host Graphs
Data Structures and Algorithms
Summary
Finding small connected patterns inside large complex networks is a common problem in computer science. The authors show new algorithms that find certain small patterns much faster when the larger network is not densely connected. They introduce a new general measure called (p, q)-width to guide these faster searches and improve on existing methods. These algorithms work well especially for patterns like cycles and paths of specific sizes and are sometimes provably optimal. They also extend their approach to handle special networks called bipartite graphs, speeding up detection of even longer paths and cycles.
What this means in practice
- •For network analysis engineers: Detects small structural patterns faster in large, sparse network data improving analysis speed for social or communication networks.
- •For graph database developers: Enables more efficient query operations involving small induced patterns in sparse graph databases, reducing computational overhead.
Authors
Priyanshi Agrawal, Balagopal Komarath
Abstract
We study algorithms for detecting induced subgraphs corresponding to fixed pattern graphs in host graphs. We show that at least five of the 21 connected graphs on five vertices can be detected in time roughly the product of the number of vertices and the number of edges, and that at least 65 of the 112 connected graphs on six vertices can be detected in time nearly quadratic in the number of edges. We also give algorithms for detecting induced paths and cycles on seven vertices, running in time roughly the number of vertices times the square of the number of edges. Our main technical tool is a generalized notion of tree decomposition width, called (p, q)-width. It yields algorithms whose running times depend on both the number of vertices and the number of edges, and are never worse than existing bounds. Whenever the host graph has fewer than roughly quadratically many edges in its number of vertices, our bounds are strictly faster. For some patterns, including the seven-vertex cycle, our algorithms are optimal under standard complexity-theoretic assumptions. We further develop this approach using pattern-based polynomials that exploit the structure of tree decompositions, not just their width. This gives algorithms for detecting induced paths and cycles on an even number of vertices in bipartite graphs, running in time roughly the (k-1)-th power of the number of edges for paths on 2k vertices, and that same bound times the number of vertices for cycles on 2k vertices. These are faster than the best known algorithms for general graphs.