Graph theory: best algorithm to find combination of edges “directions”, where each node has at most one edge directed to it

Question

I’m dealing with a graph where there are a certain number of nodes, and there are predefined connections between them which don’t have “directions” yet.

Problem is to give all the edges a direction (ex. If there’s a connection between A And B, give this edge the A->B direction, or B->A), in a way that no node is at the receiving end of more than one edge.

Examples: For this model (A-B-C), A->B->C works, but A->B<-C does not work, as B is at the receiving end of more than one connection. Although A<-B->C works, as B is on the giving end of both of its connections.

I’ve tried loop detection, but the fact that these nodes can be arbitrarily connected to one another, there can be numerous loops which may or may not be directly attached to each other, I could not find a solution to make use of the information.

Number of nodes can be north of thousands, and connections can be many hundreds in my case. This also rules out brute force.

It is not guaranteed that there will be a definite solution, the aim of the algorithm is to find a combination where there’s the least number of connections causing nodes to have more than one edge pointing to them.

Answer 1

Not a complete algorithm, but given your description of the problem in the comments, I feel like these steps will probably bring the problem back into the brute-forcible range.

First, you should "trim" your graph. Any nodes of degree one should be pruned, with their connected edge being directed at the pruned node. Since no other edge can point to that node, we know that this choice is optimal. Rinse and repeat until all nodes remaining have two or more edges.

Next, as you mentioned, you should exclude any isolated nodes. You can actually extend this up to connected components of size <= 3. This is because for up to three nodes, your number of edges cannot exceed the number of nodes, so you can randomly assign one edge, and the rest will fall into place.

Now, what will remain are a bunch of large, highly-connected, connected components. You could actually do one more check and see if any of these form a single cycle (all nodes degree two) and then assign one edge randomly, but this is probably a fairly rare case. You'll probably just want to start brute forcing each of these independently. It'd probably be best to start from the nodes with the smallest number of edges first, updating the degree of nodes as you assign edges (and also pruning any degree one edges as before), backtracking as necessary.

Answer 2

This is a continuation of the answer by Dillon Davis.

After tree-like branches are removed, and simple cycles are resolved, the remaining graph has nodes of degree 2 or more. I propose that (for the purposes of analyzing the graph) all of the nodes of degree 2 can be removed.

Allow me to explain by example. In this example, when a node is represented by a number, that number is the degree of the node. When a node is represented by a letter, that node has degree 2. So the graph

3 - A - B - C - 4

represents a node of degree 3, connected to a chain of nodes of degree 2, connected to a node of degree 4.

The two ideal choices for this section of the graph are

3 -> A -> B -> C -> 4
3 <- A <- B <- C <- 4

These are ideal in the sense that each lettered node has exactly one incoming edge. I propose that these aren't just ideal choices, they are the only choices. Consider the first ideal solution

3 -> A -> B -> C -> 4

If node 4 has too many incoming edges, we can reduce its count by reversing the edge to C, giving

3 -> A -> B -> C <- 4

But that hasn't improved the situation, it trades "too many edges into 4" with "too many edges into C". Subsequently reversing the edge between C and B resolves C, but breaks B. Keep reversing along the chain and eventually the connection between A and 3 is reversed, and we've arrived at the second ideal solution.

Which leads me to conclude that (for the purposes of analysis)

3 - A - B - C - 4

is equivalent to

3 - 4

So how is this useful in simplifying the problem. Consider the following graph:

When nodes A and B are removed, the remaining edge connects the top node 3 to itself, so that edge can be removed. Likewise for C and D. Which leaves a graph with a single edge. Choose either direction for that edge. Then complete the solution by choosing a direction for the simple cycle A-B-3, and independently choose a direction for the simple cycle C-D-3.

Here's another example:

In this case, removing A and B creates redundant edges between the remaining nodes. After removing the redundant edges, choose either direction for the edge. The direction of that edge determines the direction of the cycle 3-A-3, and cycle 3-B-3.