Authors Top

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.


1. Introduction

In this tutorial, we’ll explain what an induced subgraph is. We’ll also show how to construct it, how to check if a (sub)graph is induced, and how to find the induced graph isomorphism.

2. Subgraphs

Let’s say we have a graph G=(V, E), where V is the set of nodes, and E denotes the edges between them. A subgraph of G is any graph G'=(V', E') such that V' \subseteq V and E' \subseteq E. In other words, each node in a subgraph is also a node in the supergraph. Further, every edge in the subgraph is an edge in the supergraph.

For example, all these graphs:

Examples of subgraphs

Can be listed as subgraphs of:

graph

3. Induced Subgraphs

An induced subgraph is a special case of a subgraph. If S is a subset of G‘s nodes, then the subgraph of G induced by S is the graph that has S as its set of vertices and contains all the edges of \boldsymbol{G} that have both endpoints in \boldsymbol{S}. This definition covers both directed and undirected graphs. Also, it covers the weighted just as the unweighted ones.

Given G and S, the induced subgraph is unique. There’s only one subgraph induced by \{D, E, G, J, K\} in the above graph:

Example of an induced subgraph

3.1. What’s the Difference?

The concepts of an induced subgraph and an ordinary subgraph are very similar. The difference is that an induced subgraph includes all the edges that have both endpoints in the inducing set \boldsymbol{S}, whereas an ordinary subgraph may miss some.

So, an induced subgraph keeps both adjacency and non-adjacency of the inducing vertices, in contrast to an ordinary subgraph that preserves only non-adjacency.

4. Induced Subgraph Problems and Algorithms

Let’s introduce a few problems related to induced subgraphs.

4.1. Induced Subgraph Construction

Here, the input consists of the graph \boldsymbol{G=(V, E)} and the inducing set \boldsymbol{S \subseteq V}. Our goal is to construct the induced subgraph \boldsymbol{G_S = (S, E_S)}. We’ll do so by iterating over the edges in E and keeping only those whose both endpoints are in S:

Rendered by QuickLaTeX.com

The time complexity depends on how we represent the graphs. Using linked lists, we traverse each edge incident to a node in S twice, so the time complexity is \Theta(|E_S|). On the other hand, if we use matrices, we traverse the whole row of |V| entries for each of the |S| inducing nodes. Therefore, the complexity will be \Theta(|S|\cdot |V|).

4.2. How to Check if a Subgraph Is Induced

In this problem, we have a graph \boldsymbol{G_1=(V_1, E_1)} and its subgraph \boldsymbol{G_2=(V_2, E_2)} (so V_2 \subseteq V_1 and E_2 \subseteq E_1). Our goal is to check if \boldsymbol{G_2} is an induced subgraph of \boldsymbol{G_1}. To do so, we iterate over the edges incident to V_2 in G_1. If we find an edge that isn’t in E_2, we can conclude that G_2 isn’t an induced subgraph because it doesn’t preserve adjacency. Otherwise, we conclude that G_2 is induced:

Rendered by QuickLaTeX.com

As before, the complexity depends on the way we represent the graphs.

We don’t need to check if G_2 contains an edge not in G_1. That’s because of the way we defined the input. Since we know that G_2 is a subgraph of G_1, E_2 can’t contain an edge that’s not in E_1.

4.3. How to Check if a Graph Is an Induced Subgraph

However, if we get G_2 as a graph of some nodes in V_1, we’ll have to check both that G_2 is a subgraph and that it is induced.

Rendered by QuickLaTeX.com

4.4. Induced Subgraph Isomorphism

The Induced Subgraph Isomorphism (ISI) is an injective mapping from one graph \boldsymbol{G_2 = (V_2, E_2)} to an induced subgraph of another, \boldsymbol{G_1=(V_1, E_1)}. So, we get G_1 and G_2 at the input and find an ISI mapping from the former to the latter.

Unlike in the previous two problems, G_2 and G_1 don’t use the same labels for their nodes. So, we have to find a mapping that translates \boldsymbol{G_2} to an induced subgraph of \boldsymbol{G_1}:

isi

Formally, we say that f: V_2 \mapsto V_1 is an ISI if and only if it satisfies:

(1)   \begin{equation*}  \begin{aligned} (\forall v',v'' \in V_2) \begin{cases}   v' \neq v'' \implies f(v') \neq f(v'') \\   (v', v'') \in E_2 \implies (f(v'), f(v'')) \in E_1 \\   (v', v'') \not \in E_2 \implies (f(v'), f(v'')) \not \in E_1 \end{cases} \end{aligned} \end{equation*}

The first condition states that f is an injective function. The second is that an ISI preserves adjacency, and the third is that it also keeps non-adjacency.

This problem is NP-hard, which means that no polynomial-time algorithm for solving it is known to date. We can treat it as a constraint-satisfaction problem (CSP) and solve it like we solve other CSPs. The Equation (1) lists all the constraints we need to define the CSP and feed it to the universal solver. Each f(v) for v \in V_2 will correspond to a CSP variable, and each variable will have the whole set V_1 as its domain.

5. Conclusion

In this article, we talked about induced and ordinary subgraphs. We also presented a few common problems related to the former subgraphs. Those are the induced subgraph construction, verification, and isomorphism.

Authors Bottom

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

Comments are closed on this article!