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$
  • $\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$ – Apass.Jack May 20 at 4:20
  • $\begingroup$ Correct, I have added that to make it clearer $\endgroup$ – Mantas Kandratavicius May 20 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$ – Apass.Jack May 20 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$ – Apass.Jack May 20 at 13:03
  • $\begingroup$ There is no "original" problem. This problem was made by me for a game that is yet to be made. That's what makes it so hard for me to find related materials on my own. $\endgroup$ – Mantas Kandratavicius May 20 at 19:08

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.