Counting and Detecting Small Subgraphs via Equations
(2013) In SIAM Journal on Discrete Mathematics 27(2). p.892-909- Abstract
- 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... (More)
- 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/3979396
- author
- Kowaluk, Miroslaw ; Lingas, Andrzej LU and Lundell, Eva-Marta LU
- organization
- publishing date
- 2013
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- subgraph and induced subgraph isomorphism, counting and detection of, subgraphs, linear equations, exact algorithms, rectangular matrix, multiplication
- in
- SIAM Journal on Discrete Mathematics
- volume
- 27
- issue
- 2
- pages
- 892 - 909
- publisher
- Society for Industrial and Applied Mathematics
- external identifiers
-
- wos:000321042800018
- scopus:84880414451
- ISSN
- 0895-4801
- DOI
- 10.1137/110859798
- language
- English
- LU publication?
- yes
- id
- 77224fca-27ac-4e31-82b7-d43f262cd7ca (old id 3979396)
- date added to LUP
- 2016-04-01 14:09:25
- date last changed
- 2022-03-14 03:56:09
@article{77224fca-27ac-4e31-82b7-d43f262cd7ca,
abstract = {{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.}},
author = {{Kowaluk, Miroslaw and Lingas, Andrzej and Lundell, Eva-Marta}},
issn = {{0895-4801}},
keywords = {{subgraph and induced subgraph isomorphism; counting and detection of; subgraphs; linear equations; exact algorithms; rectangular matrix; multiplication}},
language = {{eng}},
number = {{2}},
pages = {{892--909}},
publisher = {{Society for Industrial and Applied Mathematics}},
series = {{SIAM Journal on Discrete Mathematics}},
title = {{Counting and Detecting Small Subgraphs via Equations}},
url = {{http://dx.doi.org/10.1137/110859798}},
doi = {{10.1137/110859798}},
volume = {{27}},
year = {{2013}},
}