Is it a NP-hard problem?
Difference between en1 and en2, changed 256 character(s)
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. ↵
![Statement](/predownloaded/43/4b/434ba12ef9bbb7dcbcf031d42dd852d68bee5e99.png)↵
![Explanation for samples](/predownloaded/59/1b/591b1423742b409c5c4c5e5d4746a6a7f717dc4d.png)↵
</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English ShapeBlaze 2023-11-30 19:29:46 256 Tiny change: 'orces.com/7e71e9/Screensho' -> 'orces.com/fa1471/Screensho'
en1 English ShapeBlaze 2023-11-30 19:02:20 842 Initial revision (published)