Advanced

Detecting and Counting Small Pattern Graphs

Floderus, Peter LU ; Kowaluk, Miroslaw; Lingas, Andrzej LU and Lundell, Eva-Marta LU (2015) In SIAM Journal on Discrete Mathematics 29(3). p.1322-1339
Abstract
We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs. We present a new general method for detecting induced subgraphs of a host graph isomorphic to a fixed pattern graph by reduction to polynomial testing for nonidentity with zero over a field of finite characteristic. It yields new upper time bounds for several pattern graphs on five vertices and provides an alternative combinatorial method for the majority of pattern graphs on four and three vertices. Since our method avoids the large overhead of fast matrix multiplication, it can be of practical interest even for larger pattern graphs. Next, we derive new upper time bounds on counting the number of isomorphisms between a... (More)
We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs. We present a new general method for detecting induced subgraphs of a host graph isomorphic to a fixed pattern graph by reduction to polynomial testing for nonidentity with zero over a field of finite characteristic. It yields new upper time bounds for several pattern graphs on five vertices and provides an alternative combinatorial method for the majority of pattern graphs on four and three vertices. Since our method avoids the large overhead of fast matrix multiplication, it can be of practical interest even for larger pattern graphs. Next, we derive new upper time bounds on counting the number of isomorphisms between a fixed pattern graph with an independent set of size s and a subgraph of the host graph. We also consider a weighted version of the counting problem, when one counts the number of isomorphisms between the pattern graph and lightest subgraphs, providing a slightly slower combinatorial algorithm. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
subgraph and induced subgraph isomorphism, counting and detection of, subgraphs, polynomial testing, exact algorithms, randomized algorithms, rectangular matrix multiplication
in
SIAM Journal on Discrete Mathematics
volume
29
issue
3
pages
1322 - 1339
publisher
SIAM Publications
external identifiers
  • wos:000362419600011
  • scopus:84943147680
ISSN
0895-4801
DOI
10.1137/140978211
language
English
LU publication?
yes
id
ca3427b4-1f67-49e4-bc35-0635d2dd426f (old id 8227247)
date added to LUP
2015-12-01 11:03:57
date last changed
2017-09-17 06:04:21
@article{ca3427b4-1f67-49e4-bc35-0635d2dd426f,
  abstract     = {We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs. We present a new general method for detecting induced subgraphs of a host graph isomorphic to a fixed pattern graph by reduction to polynomial testing for nonidentity with zero over a field of finite characteristic. It yields new upper time bounds for several pattern graphs on five vertices and provides an alternative combinatorial method for the majority of pattern graphs on four and three vertices. Since our method avoids the large overhead of fast matrix multiplication, it can be of practical interest even for larger pattern graphs. Next, we derive new upper time bounds on counting the number of isomorphisms between a fixed pattern graph with an independent set of size s and a subgraph of the host graph. We also consider a weighted version of the counting problem, when one counts the number of isomorphisms between the pattern graph and lightest subgraphs, providing a slightly slower combinatorial algorithm.},
  author       = {Floderus, Peter and Kowaluk, Miroslaw and Lingas, Andrzej and Lundell, Eva-Marta},
  issn         = {0895-4801},
  keyword      = {subgraph and induced subgraph isomorphism,counting and detection of,subgraphs,polynomial testing,exact algorithms,randomized algorithms,rectangular matrix multiplication},
  language     = {eng},
  number       = {3},
  pages        = {1322--1339},
  publisher    = {SIAM Publications},
  series       = {SIAM Journal on Discrete Mathematics},
  title        = {Detecting and Counting Small Pattern Graphs},
  url          = {http://dx.doi.org/10.1137/140978211},
  volume       = {29},
  year         = {2015},
}