Advanced

Rare Siblings Speed-Up Deterministic Detection and Counting of Small Pattern Graphs

Kowaluk, Mirosław and Lingas, Andrzej LU (2019) In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 11651 LNCS. p.322-334
Abstract

We consider a class of pattern graphs on (formula presented) vertices that have q-2 distinguished vertices with equal neighborhood in the remaining two vertices. Two pattern graphs in this class are siblings if they differ by some edges connecting the distinguished vertices. In particular, we show that if induced copies of siblings to a pattern graph in such a class are rare in the host graph then one can detect the pattern graph relatively efficiently. For example, we infer that if there are (formula presented) induced copies of a diamond (i.e., a graph on four vertices missing a single edge to be complete) in the host graph, then an induced copy of the complete graph on four vertices, K:4 as well as an induced copy of the cycle on... (More)

We consider a class of pattern graphs on (formula presented) vertices that have q-2 distinguished vertices with equal neighborhood in the remaining two vertices. Two pattern graphs in this class are siblings if they differ by some edges connecting the distinguished vertices. In particular, we show that if induced copies of siblings to a pattern graph in such a class are rare in the host graph then one can detect the pattern graph relatively efficiently. For example, we infer that if there are (formula presented) induced copies of a diamond (i.e., a graph on four vertices missing a single edge to be complete) in the host graph, then an induced copy of the complete graph on four vertices, K:4 as well as an induced copy of the cycle on four vertices, C:4 can be deterministically detected in (formula presented) time. Note that the fastest known algorithm for K:4 and the fastest known deterministic algorithm for C:4 run in (formula presented) time. We also show that if there is a family of siblings whose induced copies in the host graph are rare then there are good chances to determine the numbers of occurrences of induced copies for all pattern graphs on q vertices relatively efficiently.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Fundamentals of Computation Theory : 22nd International Symposium, FCT 2019, Proceedings - 22nd International Symposium, FCT 2019, Proceedings
series title
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
editor
Gąsieniec, Leszek Antoni ; Jansson, Jesper ; Levcopoulos, Christos ; ; and
volume
11651 LNCS
pages
13 pages
publisher
Springer
external identifiers
  • scopus:85070616029
ISSN
1611-3349
0302-9743
ISBN
9783030250270
9783030250263
DOI
10.1007/978-3-030-25027-0_22
language
English
LU publication?
yes
id
867da6fb-eaf7-424f-8165-5731405be5cf
date added to LUP
2019-08-26 09:58:59
date last changed
2019-11-25 09:33:42
@inproceedings{867da6fb-eaf7-424f-8165-5731405be5cf,
  abstract     = {<p>We consider a class of pattern graphs on (formula presented) vertices that have q-2 distinguished vertices with equal neighborhood in the remaining two vertices. Two pattern graphs in this class are siblings if they differ by some edges connecting the distinguished vertices. In particular, we show that if induced copies of siblings to a pattern graph in such a class are rare in the host graph then one can detect the pattern graph relatively efficiently. For example, we infer that if there are (formula presented) induced copies of a diamond (i.e., a graph on four vertices missing a single edge to be complete) in the host graph, then an induced copy of the complete graph on four vertices, K:4 as well as an induced copy of the cycle on four vertices, C:4 can be deterministically detected in (formula presented) time. Note that the fastest known algorithm for K:4 and the fastest known deterministic algorithm for C:4 run in (formula presented) time. We also show that if there is a family of siblings whose induced copies in the host graph are rare then there are good chances to determine the numbers of occurrences of induced copies for all pattern graphs on q vertices relatively efficiently.</p>},
  author       = {Kowaluk, Mirosław and Lingas, Andrzej},
  booktitle    = {Fundamentals of Computation Theory : 22nd International Symposium, FCT 2019, Proceedings},
  editor       = {Gąsieniec, Leszek Antoni and Jansson, Jesper and Levcopoulos, Christos},
  isbn         = {9783030250270},
  issn         = {1611-3349},
  language     = {eng},
  month        = {01},
  pages        = {322--334},
  publisher    = {Springer},
  series       = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
  title        = {Rare Siblings Speed-Up Deterministic Detection and Counting of Small Pattern Graphs},
  url          = {http://dx.doi.org/10.1007/978-3-030-25027-0_22},
  doi          = {10.1007/978-3-030-25027-0_22},
  volume       = {11651 LNCS},
  year         = {2019},
}