Rare Siblings Speed-Up Deterministic Detection and Counting of Small Pattern Graphs
(2023) In Algorithmica 85(4). p.976-991- Abstract
We consider a class of pattern graphs on q≥ 4 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 an example, we infer that if there are Nd 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, K4, as well as an induced copy of the cycle on four... (More)
We consider a class of pattern graphs on q≥ 4 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 an example, we infer that if there are Nd 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, K4, as well as an induced copy of the cycle on four vertices, C4, can be deterministically detected in O(n2.75+ Nd) time. Note that the fastest known algorithm for K4 and the fastest known deterministic algorithm for C4 run in O(n3.257) time. By using random bits, we can speed up our method such that the number of induced copies of the siblings is replaced by the ratio of this number to the number of induced copies of the pattern graph plus 1 in the upper time bound. 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)
- author
- Kowaluk, Mirosław and Lingas, Andrzej LU
- organization
- publishing date
- 2023
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Induced subgraph isomorphism, Matrix multiplication, Time complexity, Witnesses for Boolean matrix product
- in
- Algorithmica
- volume
- 85
- issue
- 4
- pages
- 976 - 991
- publisher
- Springer
- external identifiers
-
- scopus:85142286734
- ISSN
- 0178-4617
- DOI
- 10.1007/s00453-022-01063-2
- language
- English
- LU publication?
- yes
- id
- ca040150-06f4-4c23-bc85-9c07a235dd6d
- date added to LUP
- 2023-01-20 12:15:20
- date last changed
- 2023-10-26 14:53:56
@article{ca040150-06f4-4c23-bc85-9c07a235dd6d,
abstract = {{<p>We consider a class of pattern graphs on q≥ 4 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 an example, we infer that if there are N<sub>d</sub> 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<sub>4</sub>, as well as an induced copy of the cycle on four vertices, C<sub>4</sub>, can be deterministically detected in O(n<sup>2.75</sup>+ N<sub>d</sub>) time. Note that the fastest known algorithm for K<sub>4</sub> and the fastest known deterministic algorithm for C<sub>4</sub> run in O(n<sup>3.257</sup>) time. By using random bits, we can speed up our method such that the number of induced copies of the siblings is replaced by the ratio of this number to the number of induced copies of the pattern graph plus 1 in the upper time bound. 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}},
issn = {{0178-4617}},
keywords = {{Induced subgraph isomorphism; Matrix multiplication; Time complexity; Witnesses for Boolean matrix product}},
language = {{eng}},
number = {{4}},
pages = {{976--991}},
publisher = {{Springer}},
series = {{Algorithmica}},
title = {{Rare Siblings Speed-Up Deterministic Detection and Counting of Small Pattern Graphs}},
url = {{http://dx.doi.org/10.1007/s00453-022-01063-2}},
doi = {{10.1007/s00453-022-01063-2}},
volume = {{85}},
year = {{2023}},
}