Visiting at least k good edges — Graph Problem

Revision en1, by alirezaopmc, 2021-05-14 10:06:46

There is a directed weighted graph with $$$m$$$ edges. There are $$$n$$$ edges marked as good one. Suppose that a vertex $$$h$$$ is called root and we want to find a minimum path starting from $$$h$$$ ending to itself that contains at least $$$k$$$ good edges. Path definition in this problem is as regular path that can not consists of same edges except good one. In fact on this path we can visit good edges as many times we want but not for other edges. (And also note that this path should end with $$$h$$$ itself.)

There is no constraints. I just wanna to know how to beat this problem theoretically.

Tags #graph

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English alirezaopmc 2021-05-14 10:06:46 630 Initial revision (published)