Theory of Algorithms

Chapter 9 Limits to Computing

| About   中文版   «  9.15. Reduction of 3-SAT to Clique   ::   Contents   ::   9.17. Reduction of 3-SAT to Hamiltonian Cycle  »

9.16. Reduction of Independent Set to Vertex Cover

9.16.1. Independent Set to Vertex Cover

The following slideshow shows that an input instance to INDEPENDENT SET can be reduced to an equivalent input instance to VERTEX COVER in polynomial time.

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

This reduction can help in providing an NP Completeness proof for the Vertex Cover problem.

   «  9.15. Reduction of 3-SAT to Clique   ::   Contents   ::   9.17. Reduction of 3-SAT to Hamiltonian Cycle  »

© Copyright 2011-2025 by OpenDSA Project Contributors and distributed under an MIT license. Last updated on Oct 25, 2026. Created using Sphinx 8.2.0.
Close Window