Directed graph with max indegree of a vertex

Question

I was trying to look at few applications of network flow when I came across this problem:

We begin with a directed graph, G = (V,E). We need to add more edges to the graph such that we have \forall u,v \in V, e = (u -> v) or e = (v -> u) but not both. i.e. we want to add more edges to the graph so that every pair of vertices in the graph are connected to each other (either with an outgoing edge or incoming edge but not both). So, in total we will have |V||V-1|/2 edges. While we build this graph, we need to ensure that the indegree of a given vertex, say w is the maximum among all the vertices of the graph (if it is 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 network flow by building a network without vertex w (and with 2 new vertices for source, s and sink, t). But I'm not sure how to represent the capacities and flow direction in the new graph so as to simplify the problem to network flow in order to find the edge orientations in the graph. Maybe what I'm doing is wrong, but I just wrote if someone might get a hint from it.

Per Per · Accepted Answer · 2011-11-17T22:48:57

When attacking this kind of problem, I tend to write down a mathematical program and then massage it. Clearly, we should orient all missing edges involving w toward w. Let d be the resulting in-degree of w. For all distinct i, j, let x_{ij} = 1 if 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 < j.

(*) 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 conservation constraints, as each variable appears once negatively and once positively. Let's change the inequality to an 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're almost all the way to a flow LP -- we just need to clean out the constants 1 and k. I'll let you handle the rest (it involves introducing t).

Directed graph with max indegree of a vertex

1 Answers