Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Counting and Detecting Small Subgraphs via Equations

In English

Författare

Summary, in English

We present a general technique for detecting and counting small subgraphs. It consists of forming special linear combinations of the numbers of occurrences of different induced subgraphs of fixed size in a graph. These combinations can be efficiently computed by rectangular matrix multiplication. Our two main results utilizing the technique are as follows. Let H be a fixed graph with k vertices and an independent set of size s. 1. Detecting if an n-vertex graph contains a (not necessarily induced) subgraph isomorphic to H can be done in time O(n(omega(inverte right perpendicular(k-s)/2inverted letf perpendicular,1,1 right perpendicular(k- s)/2inverted letf perpendicular))), where omega(p, q, r) is the exponent of fast arithmetic matrix multiplication of an n(p) x n(q) matrix by an n(q) x n(r) matrix. 2. When s = 2, counting the number of (not necessarily induced) subgraphs isomorphic to H can be done in the same time, i.e., in time O(n(omega(inverted right perpendicular(k-2)/2inverted left perpendicular,1, inverted right perpendicular(k-2)/2inverted left perpendicular))). It follows in particular that we can count the number of subgraphs isomorphic to any H on four vertices that is not K-4 in time O(n(omega)), where omega = omega(1, 1, 1) is known to be smaller than 2.373. Similarly, we can count the number of subgraphs isomorphic to any H on five vertices that is not K-5 in time O(n(omega(2,1,1))), where omega(2, 1, 1) is known to be smaller than 3.257. Finally, we derive input-sensitive variants of our time upper bounds. They are partially expressed in terms of the number m of edges of the input graph and do not rely on fast matrix multiplication.

Publiceringsår

2013

Språk

Engelska

Sidor

892-909

Publikation/Tidskrift/Serie

SIAM Journal on Discrete Mathematics

Volym

27

Issue

2

Dokumenttyp

Artikel i tidskrift

Förlag

Society for Industrial and Applied Mathematics

Ämne

  • Computer Science

Nyckelord

  • subgraph and induced subgraph isomorphism
  • counting and detection of
  • subgraphs
  • linear equations
  • exact algorithms
  • rectangular matrix
  • multiplication

Status

Published

ISBN/ISSN/Övrigt

  • ISSN: 0895-4801