1
$\begingroup$

So I have recently ran into a graph theory problem and was unable to find a matching algorithm for the problem or reword the problem to match some existing algorithm.

The problem is pretty straightforward - given a weighted directed graph, pick edges to maximize the sum of all weights of the chosen edges. Max one edge can point to another vertex and no vertex can be the head for more than one edge.

So far this would seem like a problem solvable with a matching algorithm, but there's an extra catch - a vertex can be the head for an edge only if the vertex is not a tail of any edges in the initially given graph, or if it's a tail for one of the chosen edges. On top of that, the graph from the chosen edges has to be acyclic.

A good analogy would be to imagine each vertex as a cell. I can mark all vertices that are initially tails of some edges as cells with some object in them. Picking an edge would mean moving the object from one cell to another. This analogy seems perfect, because:

  • A vertex can be the tail of max one chosen edge (aka the object can be moved to only one other cell)
  • A vertex can be the head of max one chosen edge (aka only one object can be moved into a cell)
  • A vertex can be the head for a selected edge only if the vertex was not a tail of any edges in the initially provided graph, or if it's a tail for one of the chosen edges (aka the cell was either initially empty or the object can be carried into another cell thus emptying the cell)

As good as it is, I was unable to find any algorithms that would be of any help. Is pure bruteforcing for edge combinations as good as it gets? Or can I get the edges in a more optimized way?

$\endgroup$
10
  • $\begingroup$ "Max one edge can point to another vertex". Do you mean "Max one chosen edge can point to another vertex"? "A vertex can be the head for an edge only ..." Do you mean "a vertex can be the head for a chosen edge only ..."? Please make sure to change "edge" to "chosen edge" at all appropriate places so as to be clear. $\endgroup$
    – John L.
    May 20, 2019 at 4:20
  • $\begingroup$ Correct, I have added that to make it clearer $\endgroup$ May 20, 2019 at 4:31
  • $\begingroup$ "A vertex can be the head for an edge only if the vertex is not a tail of any edges in the given graph". So, in the given graph, it cannot happen that there are two edges $\vec{AB}$ and $\vec{BC}$. Correct? $\endgroup$
    – John L.
    May 20, 2019 at 13:01
  • $\begingroup$ Could you please add a reference to the original problem? 1) Credit should be attributed. 2) The original problem is probably stated clearer. 3) A reference is apt to motivate people. 4) A reference may save readers who look for related materials lots of time. $\endgroup$
    – John L.
    May 20, 2019 at 13:03
  • 1
    $\begingroup$ Here is my understanding of the problem. Given a weighted directed graph, we want to select a set of vertex-disjoint paths that start from vertices whose in-degree is 0 such that the sum of weights of all edges in those paths reaches the maximum. Is that correct? $\endgroup$
    – John L.
    May 21, 2019 at 4:14

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.