An algorithm to find every induced subgraph that is a tree

Question

I've been taking discrete math classes for a few months now and I was recently tasked to with a challenging exercise. I have to write a program that finds every induced subgraph that is a tree. The induced graph must have $m$ number of vertices ($m < n$, where $n$ is the number of vertices in the given graph).

So I've been digging around the internet for the last two days and the best things that I've found are an algorithm to check whether the graph is a tree: https://www.geeksforgeeks.org/check-given-graph-tree/ and these mathematical proofs: https://reader.elsevier.com/reader/sd/pii/S0166218X09000663?token=63213A4B2D548D315FF37E74896FD371A61C08FBDEC7C79C89D1C3E919C631ABBF6C048E5DB1600A3622E12758D51E49. It's quite frustrating as we were only given basic theory about trees and no programming knowledge at all so any help would really be appreciated!

Answer 1

I am assuming the graph is the data structure consisting of two "lists," a vertex list $V$ and an edge list $E$. Furthermore, I am assuming you know what while-loops and for-loops are. Good luck with your class!

First, you must know the following algorithm that checks for a cycle in a connected graph:

check_cycle(vertex_list $V$, edge_list $E$)
$\ \ \ $ 1. if $E= \emptyset$
$\ \ \ $ 2. $\ \ \ $ then return False
$\ \ \ $ 3. else pick some $v \in V$
$\ \ \ $ 4. let explored $= \{v\}$, unexplored $= E$
$\ \ \ $ 5. while unexplored $\neq \emptyset$
$\ \ \ $ 6.$\ \ \ $ pick some $e\in$ unexplored such that $e\cap$explored$\neq \emptyset$
$\ \ \ $ 7.$\ \ \ $ if $|e \cap $explored$|=2$
$\ \ \ $ 8.$\ \ \ $ $\ \ \ $ then return True
$\ \ \ $ 9.$\ \ \ $ else
$\ \ \ $ 10.$\ \ \ $ $\ \ \ $set explored $=$ explored$ \cup e$
$\ \ \ $ 11.$\ \ \ $ $\ \ \ $ set unexplored $=$ unexplored$ \setminus e$
$\ \ \ $ 12. return False

second I assume that you are familiar with Kruskal's algorithm which finds a spanning forest

find_forrest(vertex_list $V$, edge_list $E$)
$\ \ \ $ 1. if $E= \emptyset$
$\ \ \ $ 2. $\ \ \ $ then return $(V,E)$
$\ \ \ $ 3. let forest $= \emptyset$, unexplored $= E$
$\ \ \ $ 4. while unexplored $\neq \emptyset$
$\ \ \ $ 5.$\ \ \ $ pick some $e\in$ unexplored
$\ \ \ $ 6.$\ \ \ $ set unexplored $=$ unexplored$ \setminus e$
$\ \ \ $ 7.$\ \ \ $ if check_cycle($V$, forest$\cup \{e\})==$ False
$\ \ \ $ 8.$\ \ \ $ $\ \ \ $ then set forest $=$ forest$ \cup e$
$\ \ \ $ 9. return $(V,$ forest$)$

and third I also assume that you know how to perform the following

connected_components(vertex_list $V$, edge_list $E$)
$\ \ \ $1. start with the obvious explored/unexplored sets of vertices
$\ \ \ $2. for each $v \in V$ that is unexplored perform depthfirst search for the vertices connected to it
$\ \ \ \ \ \ $ each time you start on a new vertex create a new component $C_i$ (i.e. for each loop iteration)
$\ \ \ \ \ \ $ each time you find a new vertex add it to the current $C_i$ (i.e. within each loop iteration)
$\ \ \ $3. return a list $(C_1,...,C_n)$ of the connected components of $(V,E)$

here I am assuming familiarity with depthfirst search.

We are finally ready to write the final algorithm

find_subtrees_of_size(int m, vertex_list $V$, edge_list $E$)
$\ \ \ $ 1. set components = connected_components($V$, $E$)
$\ \ \ $ 2. set trees = $\emptyset$
$\ \ \ $ 3. delete all of $C_i \in$ components that have less than $m$ vertices
$\ \ \ $ 4. let $(V_i,E_i)$ be the subgraphs induced by the $C_i$
$\ \ \ $ 5. for each $(V,E)$ in components
$\ \ \ $ 7. $\ \ \ $ for each $V'\subset V$ such that $|V'|=m$
$\ \ \ $ 9. $\ \ \ $$\ \ \ $ if $|$connected_components(find_forrest($V'$, $E'$))$|==1$
$\ \ \ $ 10. $\ \ \ $$\ \ \ $$\ \ \ $then for each $E''\subset E'$ such that $|E''|=m-1$
$\ \ \ $ 9. $\ \ \ $ $\ \ \ $ $\ \ \ $if $|$connected_components($V'$, $E''$)$|==1$
$\ \ \ $ 10. $\ \ \ $$\ \ \ $$\ \ \ $ $\ \ \ $then set trees = trees$\cup \{(V'', E'')\}$
$\ \ \ $ 5. return trees

here I am assuming you know how to produce all of the $\binom{V}{m}$, the simplest problem in algorithmic combinatorics/discrete math.

Answer 2

What do you know about a tree? It is a connected graph with no cycles!

You mentioned you don't have a programming background, and no algorithms were taught, so the answer has to be somewhat simple!

First, you can construct a function that check for cycles. It doesn't have to be complicated or terribly efficient! Just get a function that works. A depth first search would be something to look up if you have no idea how to start. Or if you really want to try exotic methods, try looking at this question.

Now, you cannot have any cycles in your induced subgraph. What can you do next? Remove vertices! How do you check which vertices to remove? You can always do something clever like over in this paper, but what you want now is something that works! You could just remove vertices one by one and check. Or you could see that you need to disconnect every cycle to get trees. Just choose how you want to remove vertices! Remember you have to check all possible removal of vertices, not just one branch! You can look up breadth-first search if you are stuck!

Now to check if the induced subgraph is a tree or a forest. You just have to check connectedness. If it is connected, it is a tree! If not, the connected components are individually trees! Moreover, if you have done a breadth-first search for induced subgraphs with no cycles, you also can confirm that your tree is of maximum size.

At this point, you should have all possible induced subgraphs of maximum size. You also know that induced subgraphs of trees are trees too! So any subset of vertices of your current trees are also induced subgraphs that are trees!

Et Voila! You are done!