I have an undirected unweighted graph that is defined by an adjacency matrix $D$.
I need an easy to compute measure for how tree-like the structure of the graph is. I have no specific requirements, other than that it should be 1 if the graph consists of trees (i.e. is a forest) and less otherwise.
My initial hunch would be to go for something like
share of edges that would need to be removed to obtain a forest or
number of nodes that would need to be duplicated in order to obtain a forest
But those seem to be hard to compute (maybe something could be done with igraphs unfold_tree().
I could not find any theory or literature that I could dive deeper into. Any pointers to existing concepts/theories/algorithms would be appreciated.
You may be interested in the treewidth of a graph. Computing the treewidth is NP-hard in general, however there may be a polynomial time or fixed-parameter tractable algorithm depending on the specific case.
A tree decomposition of a graph $G$ is a tree whose vertices are subsets of $V(G)$ called bags such that the following hold:
1) Every vertex in $G$ is contained in some bag.
2) For every edge $e=(u, v)$ there is some bag $B$ with $u, v \in B$.
3) The subgraph induced by all bags containing a vertex $v \in V(G)$ is a tree.
The treewidth of $G$ is defined to be the cardinality of the largest bag minus one. A graph has treewidth 1 if and only if it is a forest. The treewidth of $G$ tells us how "treelike" $G$ because it tells us the size of $G$'s recursive balanced separators.
A separator of $G$ is a set of vertices $S$ such that the graph induced by $V(G) \setminus S$ is disconnected and the vertices in $V(G) \setminus S$ can be partitioned into two sets $S_1$ and $S_2$ with no edges between them. We call a separator balanced if both $|S_1| = O(n)$ and $|S_2| = O(n)$ where $n = |V(G)|$. We call a balanced separator $S$ recursive if recursive balanced separators can also be found for the subgraphs induced by $S_1$ and $S_2$. If a class of graphs has recursive balanced separators, they can be used to design efficient divide and conquer algorithms on them.
Trees have recursive balanced separators consisting of single vertices. A consequence of the definition of the tree decomposition is that every bag is a separator for $G$. It can be shown that there always exists a bag $B$ that acts as a balanced separator for $G$. Moreover, $B$ separates $G$'s tree decomposition, hence the process of finding a balanced separator can be applied recursively.