Directional graph with maximum vertex accuracy

Question

I tried to look at several network stream applications when I ran into this problem:

We start with the directed graph G = (V,E) . We need to add more faces to the graph so that we have \forall u,v \in V, e = (u -> v) or e = (v -> u) but not both . that is, we want to add additional edges to the graph so that each pair of vertices in the graph is connected to each other (either an outgoing front or an incoming front, but not both). So, in the general case, we will have edges |V||V-1|/2 . While we are building this graph, we need to make sure that the degree of a given vertex, say w , is the maximum among all vertices of the graph (if possible, given the original graph). Note that we cannot change the orientation of the edges in the original graph.

I am trying to solve it using a network stream by building a network without a vertex w (and using 2 new vertices for the source, s and sink, t). But I’m not sure how to represent the power and direction of the flow in the new graph, in order to simplify the network flow problem, in order to find the orientation of the edges in the graph. It’s possible that I’m doing it wrong, but I just wrote if someone could get a hint from him.

Answer 1

When attacking this kind of problem, I usually record a mathematical program, and then massage it. It is clear that we must orient all the missing edges from w to w. Let d be a finite power of w. For all different i, j, let x_{ij} = 1 if the arc i-> j appears in the solution, and let x_{ij} = 0 if arc j-> i appears.

 forall j. sum_i x_{ij} <= k forall i <> j. x_{ij} = 1 - x_{ji} forall i <> j. x_{ij} in {0, 1} 

Rewrite to use x_{ij} only if I <k.

 (*) forall j. sum_{i<j} x_{ij} + sum_{i>j} (1-x_{ji}) <= k forall i < j. x_{ij} in {0, 1} 

Now (*) begins to resemble storage constraints, since each variable appears once negatively and once positively. Let the change in inequality be equal to equality.

 (*) forall j. x_{si} + sum_{i<j} x_{ij} + sum_{i>j} (1-x_{ji}) = k ^^^^^^ ^ forall i < j. x_{ij} in {0, 1} forall i. x_{si} >= 0 ^^^^^^^^^^^^^^^^^^^^^ 

We almost completely approached the LP stream - we just need to clear the constants 1 and k . I will let you handle the rest (this is related to the introduction of t).