Counting and Detecting Small Subgraphs via Equations
Författare
Summary, in English
We present a general technique for detecting and counting small subgraphs. It consists of forming special linear combinations of the numbers of occurrences of different induced subgraphs of fixed size in a graph. These combinations can be efficiently computed by rectangular matrix multiplication. Our two main results utilizing the technique are as follows. Let H be a fixed graph with k vertices and an independent set of size s. 1. Detecting if an n-vertex graph contains a (not necessarily induced) subgraph isomorphic to H can be done in time O(n(omega(inverte right perpendicular(k-s)/2inverted letf perpendicular,1,1 right perpendicular(k- s)/2inverted letf perpendicular))), where omega(p, q, r) is the exponent of fast arithmetic matrix multiplication of an n(p) x n(q) matrix by an n(q) x n(r) matrix. 2. When s = 2, counting the number of (not necessarily induced) subgraphs isomorphic to H can be done in the same time, i.e., in time O(n(omega(inverted right perpendicular(k-2)/2inverted left perpendicular,1, inverted right perpendicular(k-2)/2inverted left perpendicular))). It follows in particular that we can count the number of subgraphs isomorphic to any H on four vertices that is not K-4 in time O(n(omega)), where omega = omega(1, 1, 1) is known to be smaller than 2.373. Similarly, we can count the number of subgraphs isomorphic to any H on five vertices that is not K-5 in time O(n(omega(2,1,1))), where omega(2, 1, 1) is known to be smaller than 3.257. Finally, we derive input-sensitive variants of our time upper bounds. They are partially expressed in terms of the number m of edges of the input graph and do not rely on fast matrix multiplication.
Avdelning/ar
- Computer Science
- Institutionen för datavetenskap
- Parallella System
Publiceringsår
2013
Språk
Engelska
Sidor
892-909
Publikation/Tidskrift/Serie
SIAM Journal on Discrete Mathematics
Volym
27
Issue
2
Dokumenttyp
Artikel i tidskrift
Förlag
Society for Industrial and Applied Mathematics
Ämne
- Computer Science
Nyckelord
- subgraph and induced subgraph isomorphism
- counting and detection of
- subgraphs
- linear equations
- exact algorithms
- rectangular matrix
- multiplication
Status
Published
ISBN/ISSN/Övrigt
- ISSN: 0895-4801