0
$\begingroup$

I am studying for my final exams in complexity theory and I came across a graph problem which I cannot fully prove that it is NP-complete. Its gist is the following:

Assume that you have a weighted directed graph, where the weight of each edge is the travel time between the two corresponding nodes. There are goods on each location of value $v_i$ that you can acquire once. Each good has a time deadline $d_i$ after which it expires.

You want to answer whether you can accumulate a total value $V$.

I have to show that the problem above is NP-complete. Skipping the proof that it is in NP, what's left is to show that we can reduce a known NP-hard problem to it. I believe the Knapsack problem is a good candidate if one uses the following reduction:

Each item in the Knapsack problem becomes a node in our graph. The weight of the item is the time to travel to this node from all other nodes, and the value of the item is the value of the good at this node. We are asked if we can reach a total value of V, the same as in the Knapsack problem.

This construction can be done in polynomial time. Therefore, our problem is NP-hard.

My questions:

  1. Is there any better way to map the different expiration deadlines to the Knapsack problem?

  2. Do you see another known NP-hard problem that is a better fit than the Knapsack problem?

$\endgroup$

1 Answer 1

0
$\begingroup$

Let $G = (V, E)$ be an undirected graph. Assume the value is $v_i = 1$ for each vertex and the weight is $w_e = 1$ for each edge. Also assume the deadline is $d_i = |V| - 1$ for each vertex.

Then you can accumulate a total value $|V|$ if and only if there is an hamiltonian path in $G$.

$\endgroup$
2
  • $\begingroup$ Thanks a lot for your succinct and prompt answer @Nathaniel. I am wondering if assuming $\{v_i=1, w_e=1, d_i=|V|-1\}$ poses a loss of generality and only deals with a special case of the problem, meaning that one cannot say that the original one is actually NP-complete; only its special case is. Or am I missing something? $\endgroup$
    – pcko1
    May 29, 2023 at 22:32
  • 1
    $\begingroup$ When doing a reduction from problem $A$ (here the hamiltonian path problem) to problem $B$ (here your problem), you need to find a construction $f$ that, from any instance $x$ of $A$, constructs a particular instance $f(x)$ of $B$ such that $x\in A$ if and only if $f(x) \in B$. This is the basis of reductions. $\endgroup$
    – Nathaniel
    May 29, 2023 at 23:20

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.