0
$\begingroup$

I developed an algorithm that transforms any simple connected graph, cyclic or not, into a tree. The resulting tree is syntax-preserving, in a sense that it allows to reconstruct the original input graph and only the original input graph. In other words, the constructed tree preserves adjacency information, while resolving cycles. Moreover, I assume that with the constructed tree allowing to reconstruct only the original input graph, no other graph that is structurally different can exist that would result in an identical tree form.

I did some research on algorithms that transform graphs into tree form, but I was unable to find another algorithm that would work for any simple connected graph like described above. However, I am pretty such there must exist something.

So maybe one more experienced in graph theory can help me out. It would be highly appreciated.

Alex

Improve this question
$\endgroup$
  • $\begingroup$ Here is another algorithm. Choose your favorite binary encoding, and encode the graph as a binary string. Now encode the binary string as a tree, for example by taking a path, hanging from every vertex an optional edge (to signify 1 rather than 0), and adding some gadget to mark the root (say 10 paths of length 2). With a little bit of work, this encoding would be reversible. $\endgroup$ – Yuval Filmus May 30 '20 at 12:49
  • $\begingroup$ Thanks for the answer, although I do not fully understand your approach? How would you encode a cyclic graph in binary form? Could you also elaborate more on how that path construction would work? $\endgroup$ – Alexander May 30 '20 at 13:39
  • $\begingroup$ @user121863, In any way you want, really. If you have a graph then you must represent it somehow in your memory. That is, you are already encoding it with some binary string. $\endgroup$ – Steven May 30 '20 at 14:41
0
$\begingroup$

In a general graph, the number of edges can go up to $\mathcal{O}(n^2)$ (where n is the number of verticies). But in a tree, that number is always $n-1$.

Then, we understand that its impossible to convert a graph to a tree preserving syntax without increasing the memory for each node by a linear factor, or increasing the number of nodes significantly.

Let us define a unique number for every node (in any way you like).

The algorithm now will be:

  1. Let $\mathcal{T}$ be the tree from the BFS algorithm on the graph (starting from node 1, for uniqueness)
  2. For every edge $e=(i,j)$ in the graph, that is not in $\mathcal{T}$ already, w.l.o.g assume $i\le j$, and add a new node with value $j$ to $\mathcal{T}$, and a connection between it and the (original) node $i$ in the tree.

Note that in the new tree, there will be a lot of nodes that have the same number.

To reconstruct the original graph, we will do the following:

  1. Create a node for every unique number in $\mathcal{T}$.
  2. Add an edge $(i,j)$ if there is a node with number $i$ that has an edge to some node with value $j$
Improve this answer
$\endgroup$
  • $\begingroup$ I believe this is exactly what I am doing, except that I add a global sink to the graph, if and only if it does not already exhibit. Hence, I circument choosing a node of the graph to be the root, but instead use the added global sink. Therefore, regardless of labeling the graph ( e.g., assigning numbers to vertices ) the resulting tree will be identical in construction. I further observed, as you mentioned, an explosion in vertices. Where I really want to get to is that for two constructed trees, their isomorphism would mean that the corresponding input graphs would also have to be isomorphic $\endgroup$ – Alexander May 30 '20 at 18:32
  • $\begingroup$ Then great! this should work for any undirected graph (including non-simple ones) $\endgroup$ – nir shahar May 30 '20 at 18:33
  • $\begingroup$ Im pretty sure this preserves isomorphism (of node numbers ), but dont take my word for that $\endgroup$ – nir shahar May 30 '20 at 18:42
  • $\begingroup$ Yes, it would work for any graph. Thanks for your clarification. What interests me is the property of graph isomorphism for the two graphs, which can then be shown efficiently. I must miss something in my thought process. If T_G is an unambiguous tree representation of G, then showing that T_G isomorph T_H would also show G isomorph H. I recond that either the algorithm to construct T_G is then in exp. time or the T_G is enlarged in size exp., meaning that showing isomorphism for the two graphs would be exp. overall. $\endgroup$ – Alexander May 30 '20 at 18:43
  • $\begingroup$ the graph isomorphism problem (GISO for short) is not known to be solvable in polynomial time (but also is not known to be NP-Complete) if thats what you are trying to solve, then it makes sense this would take exp time overall... $\endgroup$ – nir shahar May 30 '20 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.