More Web Proxy on the site http://driver.im/

research-article

A fast deterministic detection of small pattern graphs in graphs without large cliques

Authors:

Mirosław Kowaluk,

Andrzej LingasAuthors Info & Claims

Volume 770, Issue C

Pages 79 - 87

https://doi.org/10.1016/j.tcs.2018.10.028

Published: 24 May 2019 Publication History

Abstract

We show that for several pattern graphs on four vertices (e.g., C 4), their induced copies in host graphs with n vertices and no clique on k + 1 vertices can be deterministically detected in O ( n 2.5719 k 0.3176 + n 2 k 2 ) time for k < n 0.394 and O ( n 2.5 k 0.5 + n 2 k 2 ) time for k ≥ n 0.394. The aforementioned pattern graphs have a pair of non-adjacent vertices whose neighborhoods are equal. By considering dual graphs, in the same asymptotic time, we can also detect four vertex pattern graphs, that have an adjacent pair of vertices with the same neighbors among the remaining vertices (e.g., K 4), in host graphs with n vertices and no independent set on k + 1 vertices.

By using the concept of Ramsey numbers, we can extend our method for induced subgraph isomorphism to include larger pattern graphs having a set of independent vertices with the same neighborhood and n-vertex host graphs without cliques on k + 1 vertices (as well as the pattern graphs and host graphs dual to the aforementioned ones, respectively).

References

[1]

N. Alon, P. Dao, I. Hajirasouliha, F. Hormozdiari, S.C. Sahinalp, Biomolecular network motif counting and discovery by color coding, 2008, ISMB, Bioinformatics 24 (13) (2008) 241–249.

[2]

D.G. Corneil, Y. Perl, L.K. Stewart, A linear recognition algorithm for cographs, SIAM J. Comput. 14 (4) (1985) 926–934.

Digital Library

[3]

F.R.K. Chung, C.M. Grinstead, A survey of bounds for classical Ramsey numbers, J. Graph Theory 7 (1983) 25–37.

[4]

F. Eisenbrand, F. Grandoni, On the complexity of fixed parameter clique and dominating set, Theoret. Comput. Sci. 326 (2004) 57–67.

Digital Library

[5]

E.M. Eschen, C.T. Hoàng, J. Spinrad, R. Sritharan, On graphs without a C4 or a diamond, Discrete Appl. Math. 159 (7) (2011) 581–587.

[6]

P. Floderus, M. Kowaluk, A. Lingas, E.-M. Lundell, Detecting and counting small pattern graphs, SIAM J. Discrete Math. 29 (3) (2015) 1322–1339.

[7]

P. Floderus, M. Kowaluk, A. Lingas, E.-M. Lundell, Induced subgraph isomorphism: are some patterns substantially easier than others?, Theoret. Comput. Sci. 605 (2015) 119–128.

[8]

L. Gąsieniec, M. Kowaluk, A. Lingas, Faster multi-witnesses for Boolean matrix product, Inform. Process. Lett. 109 (2009) 242–247.

[9]

C.T. Hoàng, M. Kaminski, J. Sawada, R. Sritharan, Finding and listing induced paths and cycles, Discrete Appl. Math. 161 (4–5) (2013) 633–641.

Digital Library

[10]

A. Itai, M. Rodeh, Finding a minimum circuit in a graph, SIAM J. Comput. 7 (1978) 413–423.

Digital Library

[11]

T. Kloks, D. Kratsch, H. Müller, Finding and counting small induced subgraphs efficiently, Inform. Process. Lett. 74 (3–4) (2000) 115–121.

Digital Library

[12]

M. Kowaluk, A. Lingas, E.-M. Lundell, Counting and detecting small subgraphs via equations and matrix multiplication, SIAM J. Discrete Math. 27 (2) (2013) 892–909.

[13]

F. Le Gall, Faster algorithms for rectangular matrix multiplication, in: Proc. 53rd Symposium on Foundations of Computer Science, FOCS, 2012, pp. 514–523.

[14]

F. Le Gall, Powers of tensors and fast matrix multiplication, in: Proc. 39th International Symposium on Symbolic and Algebraic Computation, 2014, pp. 296–303.

[15]

J. Nešetr̆il, S. Poljak, On the complexity of the subgraph problem, Comment. Math. Univ. Carolin. 26 (2) (1985) 415–419.

[16]

S. Olariu, Paw-free graphs, Inform. Process. Lett. 28 (1988) 53–54.

[17]

T. Schank, D. Wagner, Finding, counting and listing all triangles in large graphs, an experimental study, in: Proc. WEA, 2005, pp. 606–609.

[18]

C.P. Schnorr, C.R. Subramanian, Almost optimal (on the average) combinatorial algorithms for Boolean matrix product witnesses, computing the diameter, in: Proc. Randomization and Approximation Techniques in Computer Science. Second International Workshop, in: Lecture Notes in Computer Science, vol. 1518, RANDOM'98, 1998, pp. 218–231.

[19]

C. Wolinski, K. Kuchcinski, E. Raffin, Automatic design of application-specific reconfigurable processor extensions with UPaK synthesis kernel, ACM Trans. Des. Autom. Electron. Syst. 15 (1) (2009) 1–36.

[20]

V. Vassilevska, Efficient Algorithms for Path Problems in Weighted Graphs, PhD thesis, CMU, CMU-CS-08-147 2008.

[21]

V. Vassilevska Williams, J.R. Wang, R. Williams, H. Yu, Finding four-node subgraphs in triangle time, in: Proc. of SODA, 2015, pp. 1671–1680.

[22]

V. Vassilevska Williams, Multiplying matrices faster than Coppersmith–Winograd, in: Proc. 44th Annual ACM Symposium on Theory of Computing, STOC, 2012, pp. 887–898.

[23]

H. Yu, An improved combinatorial algorithm for Boolean matrix multiplication, in: Proc. 42nd International Colloquium on Automata, Languages and Programming, in: LNCS, vol. 9134, ICALP, 2015, pp. 1094–1105.

Cited By

Koana TNichterlein A(2022)Detecting and enumerating small induced subgraphs in c-closed graphsDiscrete Applied Mathematics10.1016/j.dam.2021.06.019302:C(198-207)Online publication date: 9-Apr-2022
https://dl.acm.org/doi/10.1016/j.dam.2021.06.019

Index Terms

A fast deterministic detection of small pattern graphs in graphs without large cliques
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Graph enumeration
2. Theory of computation
  1. Design and analysis of algorithms
  2. Randomness, geometry and discrete structures

Index terms have been assigned to the content through auto-classification.

Recommendations

Rare Siblings Speed-Up Deterministic Detection and Counting of Small Pattern Graphs
Abstract
We consider a class of pattern graphs on $q \geq 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 ... $_{}$ $_{}$ $_{}$ $^{}_{}$ $_{}$ $_{}$ $^{}$
Cliques in the union of graphs

Let B and R be two simple graphs with vertex set V, and let G ( B , R ) be the simple graph with vertex set V, in which two vertices are adjacent if they are adjacent in at least one of B and R. For X V , we denote by B | X the subgraph of B induced by ...
Induced subgraph isomorphism

The complexity of the subgraph isomorphism problem where the pattern graph is of fixed size is well known to depend on the topology of the pattern graph. Here, we present two results which, in contrast, provide evidence that no topology of an induced ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 770, Issue C

May 2019

102 pages

ISSN:0304-3975

Issue’s Table of Contents

Elsevier B.V.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 24 May 2019

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Koana TNichterlein A(2022)Detecting and enumerating small induced subgraphs in c-closed graphsDiscrete Applied Mathematics10.1016/j.dam.2021.06.019302:C(198-207)Online publication date: 9-Apr-2022
https://dl.acm.org/doi/10.1016/j.dam.2021.06.019

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents