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?

  • 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 '19 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$ – user17918 Aug 22 '19 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$ – user17918 Aug 22 '19 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 '19 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 '19 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy