Consider the following problem: Long Enough Cycle Input: undirected simple graph G=(V,E) with |V = n, positive integer k

[answerhappygod]

Consider The Following Problem Long Enough Cycle Input Undirected Simple Graph G V E With V N Positive Integer K 1 (23.13 KiB) Viewed 60 times

Consider the following problem: Long Enough Cycle Input: undirected simple graph G=(V,E) with |V = n, positive integer k Question: Does G contain a simple cycle containing at least k vertices? a) Describe the language Llong for Long Enough Cycle. b) Show that Long Enough Cycle is in NP. Hint for b): Give a polynomial verifier Vlong for Llong. Explain why Vlong satisfies the definition of verifier and why it is is indeed a polynomial time verifier. Don't forget to describe what a certificate looks like.