Rare Siblings SpeedUp Deterministic Detection and Counting of Small Pattern Graphs
(2019) In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 11651 LNCS. p.322334 Abstract
We consider a class of pattern graphs on (formula presented) vertices that have q2 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 q2 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)
 author
 Kowaluk, Mirosław and Lingas, Andrzej ^{LU}
 organization
 publishing date
 20190101
 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
 16113349
 03029743
 ISBN
 9783030250270
 9783030250263
 DOI
 10.1007/9783030250270_22
 language
 English
 LU publication?
 yes
 id
 867da6fbeaf7424f81655731405be5cf
 date added to LUP
 20190826 09:58:59
 date last changed
 20191125 09:33:42
@inproceedings{867da6fbeaf7424f81655731405be5cf, abstract = {<p>We consider a class of pattern graphs on (formula presented) vertices that have q2 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 = {16113349}, language = {eng}, month = {01}, pages = {322334}, publisher = {Springer}, series = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}, title = {Rare Siblings SpeedUp Deterministic Detection and Counting of Small Pattern Graphs}, url = {http://dx.doi.org/10.1007/9783030250270_22}, doi = {10.1007/9783030250270_22}, volume = {11651 LNCS}, year = {2019}, }