Hi! ↵
↵
One of my students got the following problem on a competition.↵
↵
Given a undirected graph with $N\leq 100$ vertices and $M\leq 1000$ edges. $1\leq K\leq N$ vertices are considered special and you are given their numbers. Each edge has a "safety" characteristic — a real number between $0$ and $1$. ↵
↵
The task is to find the longest cycle, which has at least half of special vertices and the product of safety on the edges is at least $0.5$.↵
↵
It seems to me that this problem with $K=1$ is the same as finding the longest cycle in a graph, but as far as I know this is NP-hard. ↵
↵
Is it unsolvable in polynomial time or did I miss something?↵
↵
P.S. I have a screenshot of the statement but it is in Russian. If you want — I can post it in the comments, but I warn you — it is very bad:)↵
↵
<spoiler summary="Statement in Russian">↵
It is very unclear. ↵
↵
↵
</spoiler>↵
↵
↵
One of my students got the following problem on a competition.↵
↵
Given a undirected graph with $N\leq 100$ vertices and $M\leq 1000$ edges. $1\leq K\leq N$ vertices are considered special and you are given their numbers. Each edge has a "safety" characteristic — a real number between $0$ and $1$. ↵
↵
The task is to find the longest cycle, which has at least half of special vertices and the product of safety on the edges is at least $0.5$.↵
↵
It seems to me that this problem with $K=1$ is the same as finding the longest cycle in a graph, but as far as I know this is NP-hard. ↵
↵
Is it unsolvable in polynomial time or did I miss something?↵
↵
P.S. I have a screenshot of the statement but it is in Russian. If you want — I can post it in the comments, but I warn you — it is very bad:)↵
↵
<spoiler summary="Statement in Russian">↵
It is very unclear. ↵
↵
↵
</spoiler>↵
↵
