0
$\begingroup$

Is there any algorithm which can transform any graph to tree, with providing mapping from one to another? Suppose we have directed graph:

E->A
A->C
C->C
C->B
B->A
B->D

I want to convert it to tree in such way, that all biggest cycles is converted to node, and all dependencies out of this cycle is binded to this node. So, in other words, all cycles represented as nodes.

For example, the biggest cycle here:

A B C

Biggest cycle is a cycle which do not contained in other cycles. So, in example [C] is one-node-cycle but it contained in bigger cycle [A,B,C], so it is not biggest. On the other hand [A,B,C] is not contained in any other cycle, so it is biggest. Graph can contain multiple biggest cycles.

Output will be:

E->F
F->D

where F is alias for A,B,C

Is there some algorithm for this?

Other interesting example with 2 biggest cycles:

A->B
B->A

A->C

C->D
D->C

Will be converted to:

E->F
where E is alias for A,B
where F is alias for C,D
$\endgroup$
  • 1
    $\begingroup$ This is likely very difficult, since finding out whether there is a Hamiltonian cycle is NP-complete. $\endgroup$ – Yuval Filmus Jul 3 '17 at 12:37
  • 1
    $\begingroup$ You should formally define what you mean by "biggest cycles". $\endgroup$ – Yuval Filmus Jul 3 '17 at 12:44
  • 1
    $\begingroup$ Is a Hamiltonian cycle a "biggest cycle"? $\endgroup$ – Yuval Filmus Jul 3 '17 at 12:51
  • $\begingroup$ I may not understand the question, but is there a chance you are looking for the block-cut tree? That is the "biggest cycles" are the biconnected components. $\endgroup$ – marcv81 Jul 3 '17 at 12:54
  • $\begingroup$ Well, Im not sure it is Hamiltonian cycle, because sub-cycle can also be Hamiltonian. $\endgroup$ – eocron Jul 3 '17 at 12:54

Your Answer

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

Browse other questions tagged or ask your own question.