### ShapeBlaze's blog

By ShapeBlaze, history, 3 months ago,

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:)

Statement in Russian
• +11

 » 3 months ago, # |   +3 I think you should post the screenshot under spoiler
•  » » 3 months ago, # ^ |   0 Thanks, added
 » 3 months ago, # |   0 Auto comment: topic has been updated by ShapeBlaze (previous revision, new revision, compare).
 » 3 months ago, # |   0 Can the cycle visit the same node multiple times? If not, then like you said for K = 1 and if all the edges have safety 1, the existence of a Hamiltonian cycle can be reduced to checking if that longest valid cycle contains n nodes. And checking if a graph contains a Hamiltonian cycle is NP-Hard
•  » » 3 months ago, # ^ |   0 No, a node can not be visited more than once. Thanks for clarification:)
•  » » » 3 months ago, # ^ |   0 Then I am pretty sure it's NP-hard (at least the version you described in this blog, I can't read the statement you provided).