7
$\begingroup$

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}<M$?

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

Improve this question
$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – Arnaud Casteigts
    Commented Mar 27, 2020 at 9:06
  • 1
    $\begingroup$ 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. $\endgroup$
    – smapers
    Commented Mar 27, 2020 at 10:27
  • $\begingroup$ @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$. $\endgroup$
    – Joshua Grochow
    Commented Mar 28, 2020 at 1:39
  • $\begingroup$ Sure, but at least it reduces to it. $\endgroup$
    – smapers
    Commented Mar 28, 2020 at 5:16
  • $\begingroup$ @smapers And the problem asks for the exact answer, not approximation. $\endgroup$
    – LeechLattice
    Commented Mar 28, 2020 at 6:53

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.