1
$\begingroup$

Instance: an undirected graph $G=(V,E)$ with edge-weights $w:E\to{\mathbb{R}}$;
a source $s\in V$ and a sink $t\in V$;
a ground set $X=\{x_1, ..., x_k\}$, and for every $v\in V$ a corresponding subset $X(v)\subseteq X$.

Objective: Find a minimum weight $s$-$t$-path for which the subsets on its path verties cover $X$.

Has this problem been studied before in combinatorial optimization?

$\endgroup$
  • 1
    $\begingroup$ Your problem contains the TSP-path problem as a special case, as the subsets can be used to enforce that the path visits every vertex in the graph. $\endgroup$ – Gamow Aug 22 at 7:18
  • $\begingroup$ @Gamow Thank you for your comments. Maybe Hamiltonian Path with s and t as end vertices is more precise? In general, each feasible path is a subset Hamiltonian Path with s and t as ends. But it looks like enumerating all such subsets is expensive. $\endgroup$ – Rupei Xu Aug 22 at 7:37
  • $\begingroup$ Let's assume the graph is complete and unweighted, thus the shortest distance between any two vertices is 1. Then, this problem can be seen as the Minimum Set Cover Problem, it is already very difficult as by Dinur & Steurer's result, it cannot be approximated to (1-o(1) )ln n, unless P =NP. $\endgroup$ – Rupei Xu Aug 22 at 8:11
  • $\begingroup$ Since edge weights can be negative in the above formulation, you can use the same reduction to show that it's NP hard to distinguish between the case where OPT=0 and when OPT>0, so there's no hope for a multiplicative factor approximation algorithm. Assuming you're more interested in the positive weight case, do you have an idea of what kinds of paths you're most interested in (simple paths, edge non-repeating paths / trails, walks, etc.)? $\endgroup$ – Yonatan N Aug 22 at 16:46
  • 1
    $\begingroup$ In the case of simple paths, doesn't @Gamow's response rule out any hope of an approximation algorithm? If one can't solve the feasibility problem in the first place, one can't expect to find a feasible solution with good approximation guarantees. $\endgroup$ – Yonatan N Aug 23 at 15:51

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.