I have an ordered bipartite graph such that every node of the first node set is connected to every node in the second node set by an edge of a given direction (i.e., a so-called bipartite tournament graph). The direction of a given subset of the edges may be reversed, the direction of the others not.

I want to determine a minimal set of edges which are reversible and which need to be reversed such that the graph becomes acyclic.

Does anyone know an integer programming formulation for this?

  • $\begingroup$ What do you mean by "are reversible"? How do you tell whether an edge is reversible? Or do you mean just that you want to determine a minimal set of edges that, if reversed, cause the graph to become acyclic? Anyway, as far as ILP formulation, what have you tried? Why did you get stuck? It seems straightforward: you assign an integer label to each node (this is an integer variable); you require that (after reversal) edges always go from a lower-numbered to a higher-numbered edge; and you use 0/1-valued integer variables to encode which edges will be reversed. Does that not work? $\endgroup$ – D.W. Jul 3 '14 at 22:41
  • $\begingroup$ I think the idea is that there is a subset of edges which are eligible for reversing and that the minimal set of edges to be reversed must come from that subset. For example, I think that if there is a cycle containing only edges not from that subset, you're hosed. $\endgroup$ – mhum Jul 4 '14 at 0:23

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.