<p>I'm looking for a subgraph isomorphism algorithm that takes advantage of properties of graph sequences.</p>

<p>Say <span class="math-container">$\{G_i\}_{i=1}^k$</span>  is a sequence of graphs on vertex set <span class="math-container">$\{1 ... n\}$</span>, and two consecutive elements <span class="math-container">$G_i$</span> and <span class="math-container">$G_{i+1}$</span> differ by an edge (i.e. either <span class="math-container">$G_{i+1}$</span> have one edge more than <span class="math-container">$G_i$</span>, or one edge less than <span class="math-container">$G_i$</span>).</p>

<p>Let <span class="math-container">$H$</span> be a graph not depending on <span class="math-container">$i$</span>.</p>

<p>The problem is:</p>

<blockquote>
  <p>Determine whether <span class="math-container">$H$</span> is a subgraph of some <span class="math-container">$G_i$</span>.</p>
</blockquote>

<p>The naive algorithm, running subgraph isomorphism from scratch on every <span class="math-container">$(G_i,H)$</span>, has time complexity <span class="math-container">$kM$</span>, where <span class="math-container">$M$</span> is the time complexity of one instance of <span class="math-container">$(G_i,H)$</span>.</p>

<p><strong>Question: Is it possible to design a deterministic algorithm faster in terms of worst-case running time? If <span class="math-container">$N(k)$</span> is the maximum time needed to check <span class="math-container">$k$</span> graphs, is it possible to achieve <span class="math-container">$\lim_{k\rightarrow\infty} \frac{N(k)}{k}&lt;M$</span>?</strong></p>

<p>Does it help if the graphs <span class="math-container">$G$</span> and <span class="math-container">$H$</span> are very sparse (say, maximum degree≤4)?</p>

CC BY-SA 4.0
2020-03-27T09:06:09.330Z
It seems $n$ denotes both the index of a graph in the sequence and the number of vertices. You may change the sequence index to $i$, thus $\{G_i\}_{i=1}^k$ and keep $n$ for the number of vertices. Unless you really want to restrict the problem to graph sequences with as many graphs as the number of vertices.
Arnaud Casteigts
CC BY-SA 4.0
2020-03-27T10:27:42.937Z
You are describing subgraph isomorphism in the turnstile graph streaming model. The *space* complexity for subgraphs $H$ of fixed size is discussed e.g. [here](http://cseweb.ucsd.edu/~dakane/CountingSubgraphs.pdf).
smapers
CC BY-SA 4.0
2020-03-28T01:39:07.443Z
@smapers: Seems very similar, but maybe not identical? Note that in the question here, although you are guaranteed that $G_i$ and $G_{i+1}$ only differ in one edge, there is no restriction that you only see them "in streaming order" - you get to see all the $G_i$ up front and can strategize based on that. Also, no need to approximate the *counts* in each $G_i$ (as in the paper you linked), the question is just about telling whether $H$ *exists* in *any one* of the $G_i$.
Joshua Grochow
CC BY-SA 4.0
2020-03-28T05:16:34.180Z
Sure, but at least it *reduces* to it.
smapers
CC BY-SA 4.0
2020-03-28T06:53:44.807Z
@smapers And the problem asks for the exact answer, not approximation.
LeechLattice
CC BY-SA 4.0
2020-03-28T06:56:37.433Z
They consider a multiplicative error, so they do decide whether there is a isomorphic subgraph.
smapers
CC BY-SA 4.0
2020-04-02T09:20:27.960Z
@smapers But there's a chance that the algorithm would give the wrong answer, since (1 ± ε)-approximation only guarantees a 2/3 chance of correctness.
LeechLattice
CC BY-SA 4.0
2020-04-02T13:31:17.410Z
True, but you can easily amplify the success probability close to 1
smapers
<ds.algorithms><reference-request><graph-algorithms><graph-isomorphism><parameterized-complexity>
Subgraph isomorphism on graph sequences
LeechLattice
# Subgraph isomorphism on graph sequences

(Asked by: username_0 on 2020-03-27)

I'm looking for a subgraph isomorphism algorithm that takes advantage of properties of graph sequences.

Say $\{G\_i\}\_{i=1}^k$ is a sequence of graphs on vertex set $\{1 ... n\}$, and two consecutive elements $G\_i$ and $G\_{i+1}$ differ by an edge (i.e. either $G\_{i+1}$ have one edge more than $G\_i$, or one edge less than $G\_i$).

Let $H$ be a graph not depending on $i$.

The problem is:

> Determine whether $H$ is a subgraph of some $G\_i$.

The naive algorithm, running subgraph isomorphism from scratch on every $(G\_i,H)$, has time complexity $kM$, where $M$ is the time complexity of one instance of $(G\_i,H)$.

**Question: Is it possible to design a deterministic algorithm faster in terms of worst-case running time? If $N(k)$ is the maximum time needed to check $k$ graphs, is it possible to achieve $\lim\_{k\rightarrow\infty} \frac{N(k)}{k}?**

Does it help if the graphs $G$ and $H$ are very sparse (say, maximum degree≤4)?

**Tags:** ds.algorithms, reference-request, graph-algorithms, graph-isomorphism, parameterized-complexity
> **Comments:**
> **username_1**: It seems $n$ denotes both the index of a graph in the sequence and the number of vertices. You may change the sequence index to $i$, thus $\{G_i\}_{i=1}^k$ and keep $n$ for the number of vertices. Unless you really want to restrict the problem to graph sequences with as many graphs as the number of vertices.  
> **username_2**: You are describing subgraph isomorphism in the turnstile graph streaming model. The *space* complexity for subgraphs $H$ of fixed size is discussed e.g. [here](http://cseweb.ucsd.edu/~dakane/CountingSubgraphs.pdf).  
> **username_3**: @smapers: Seems very similar, but maybe not identical? Note that in the question here, although you are guaranteed that $G_i$ and $G_{i+1}$ only differ in one edge, there is no restriction that you only see them "in streaming order" - you get to see all the $G_i$ up front and can strategize based on that. Also, no need to approximate the *counts* in each $G_i$ (as in the paper you linked), the question is just about telling whether $H$ *exists* in *any one* of the $G_i$.  
> **username_2**: Sure, but at least it *reduces* to it.  
> **username_0**: @smapers And the problem asks for the exact answer, not approximation.  
> **username_2**: They consider a multiplicative error, so they do decide whether there is a isomorphic subgraph.  
> **username_0**: @smapers But there's a chance that the algorithm would give the wrong answer, since (1 ± ε)-approximation only guarantees a 2/3 chance of correctness.  
> **username_2**: True, but you can easily amplify the success probability close to 1  

---

## 0 answers

