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

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

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 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.

Details

Authors
Organisations
External organisations
  • University of Warsaw
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computer Science
Original languageEnglish
Title of host publicationFundamentals of Computation Theory
Subtitle of host publication22nd International Symposium, FCT 2019, Proceedings
EditorsLeszek Antoni Gąsieniec, Jesper Jansson, Christos Levcopoulos
PublisherSpringer
Pages322-334
Number of pages13
Volume11651
ISBN (Electronic)9783030250270
ISBN (Print)9783030250263
Publication statusPublished - 2019 Jan 1
Publication categoryResearch
Peer-reviewedYes
Event22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14 - Copenhagen Biocenter, Ole Maaloes Vej 5, DK-2200 Copenhagen N, Copenhagen, Denmark
Duration: 2019 Aug 222019 Aug 24
https://di.ku.dk/fct2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11651 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14
Abbreviated titleFCT 2019
CountryDenmark
CityCopenhagen
Period2019/08/222019/08/24
Internet address