.. raw:: html
.. _independentSet_to_vertexCover:
.. raw:: html
.. |--| unicode:: U+2013 .. en dash
.. |---| unicode:: U+2014 .. em dash, trimming surrounding whitespace
:trim:
.. odsalink:: AV/NP/IStoVCCON.css
.. This file is part of the OpenDSA eTextbook project. See
.. http://opendsa.org for more details.
.. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.
.. avmetadata::
:author: Nabanita Maji
:topic: NP-completeness
Reduction of Independent Set to Vertex Cover
============================================
Independent Set to Vertex Cover
-------------------------------
The following slideshow shows that an instance of Independent Set
problem can be reduced to an instance of Vertex Cover problem
in polynomial time.
.. inlineav:: IStoVCCON ss
:points: 0.0
:required: False
:threshold: 1.0
:long_name: IS to VC Reduction
:output: show
This reduction can help in providing an NP Completeness proof for
the Vertex Cover problem.
.. odsascript:: AV/NP/IStoVCCON.js