1
$\begingroup$

I have a directed graph (DAG) containing many nodes, all with various attributes (node attributes not edge attributes). I have a single target (finish) node and a set of source (start) nodes. I want to find a path through this graph that minimizes the sum of all the attributes on said path, and return the top N minimized paths .

Example: the nodes are tasks in a to-do list. Some items on the list need to be completed before others can be started. In this example, an attribute could be the 'spare time' or 'wiggle room' an item has before its delay would have a knock-on effect and delay the next item. So I want to find the path that minimizes the total 'spare time'. i.e. the most optimal way of working through the task from A to B.

I considered using Dijkstra's algorithm where I replace the distance parameter with the node attribute I wish to minimize. However, I am not sure how this would work as I only have node attributes, not edge attributes. I could set the edge attribute to be that of the source, or target nodes for that edge, but I don't think this is valid. E.g. if using the source node attribute for the edge attribute, then the final node in the chain's attribute would never be used and vice versa. Additionally, the actual path length doesn't matter, just the sum of the attributes along the path.

Finally, another issue is that the attributes along the path that I am trying to minimize can be negative, so the minimized path sum can be negative or positive. This seems to rule out a BFS or DFS method with early stopping (threshold) as it could stop before a future negative attribute has been reached, which would decrease the total sum along the path.

Any help or suggestions would be great, thanks.

$\endgroup$
5
  • $\begingroup$ What is meant by "the sum of all the attributes"? What type does each attribute have? Is it a number? Is there any relevant difference between a node with attributes 2,17 vs a node with attribute 19? What is meant by "the node attribute I am wishing to minimize"? I thought you want to minimize a sum; I don't know what that phrase means. What are the input to the algorithm? What is the desired output? $\endgroup$
    – D.W.
    Commented Mar 20 at 4:26
  • $\begingroup$ Sorry let me be more specific. The attributes can be a variety of things but let's take an example where the nodes are tasks in a to-do list. Some items on the list need to be completed before others can be started. In this example, an attribute could be the 'spare time' or 'wiggle room' an item has before its delay would have a knock-on effect and delay the next item. So I want to find the path that minimizes the total 'spare time'. i.e. the most optimal way of working through the task from A to B. $\endgroup$
    – laurence
    Commented Mar 20 at 20:11
  • $\begingroup$ Please don't put clarifications in the comments. Instead, edit the question so it is clear to someone who encounters it for the first time, and so people don't need to read the comments to understand what is being asked. Those seem like critical constraints that aren't mentioned anywhere in the question. We need a more careful statement of the problem, and a precise definition of which paths are valid and the score of each path, as a function of the attributes. $\endgroup$
    – D.W.
    Commented Mar 20 at 20:32
  • $\begingroup$ Thanks, I have reflected on this in the post. I am trying to be general as the specifics of the problem do not matter. The goal is to just minimize the sum of attributes (weights) along a path. $\endgroup$
    – laurence
    Commented Mar 20 at 20:51
  • $\begingroup$ If your goal is to minimize the sum of weights, and the weights are numbers, then this seems like a classic shortest-path problem, hence solvable by standard algorithms, like Dijkstra's or Bellman-Ford. If that is not accurate, then then please clarify the problem statement and explain the differences. If the only issue is weights on nodes rather than edges, I think it would help to state your problem using the standard terminology from shortest-paths problems (e.g., weights, instead of attributes). $\endgroup$
    – D.W.
    Commented Mar 21 at 1:22

1 Answer 1

0
$\begingroup$

It's NP-hard with a single source and a single target, and looking for a single path.

Reduction from SAT. Let $\phi = C_1 \land C_2$ where $C_1 = x \lor y$ and $C_2 = \neg x \lor y$.

See attached picture. There is a path collecting exactly #variables many attributes if and only if $\phi$ is satisfiable.

In the example, you can find an $s$-$t$-path collecting exactly two attributes, the ones corresponding to your chosen truth assignment. Notice that if you in the start choose to visit $\neg y$, you need to visit three attributes.

Reduction from SAT

$\endgroup$
5
  • $\begingroup$ I don't understand, what is the mechanic that prevents you from taking any path you please through the "clauses"-part of the graph? $\endgroup$
    – Highheath
    Commented Mar 19 at 19:38
  • $\begingroup$ @Highheath feel free, but picking a literal that hasn't been chosen in the "variable" part of the path will cost you 1 extra. $\endgroup$
    – Pål GD
    Commented Mar 20 at 9:00
  • $\begingroup$ If your path contains both a literal and its negation, the cost must be more than the number of variables $\endgroup$
    – Pål GD
    Commented Mar 20 at 9:01
  • $\begingroup$ Ah, I see. But then I would double check whether your definition of "attribute" is the same as OP's - from the sound of it, it sounds like he/she is referring simply to a vertex-weighted graph (or multiple weights per vertex, perhaps). $\endgroup$
    – Highheath
    Commented Mar 20 at 18:39
  • $\begingroup$ Yes it is multiple weights per vertex but I am only interested in minimizng the path between vertices for a single weight at a time. E.g. the path from A to B with the smallest some of weights x, contains these vertices... Then similarly for another weight y, etc. $\endgroup$
    – laurence
    Commented Mar 20 at 20:17

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.