Page 1 of 1
Consider the following problem: Long Enough Cycle Input: undirected simple graph G=(V,E) with |V = n, positive integer k
Posted: Wed Mar 30, 2022 9:28 am
by 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 62 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.