.. This file is part of the OpenDSA eTextbook project. See
   .. http://opendsa.org for more details.
   .. Copyright (c) 2012-2025 by the OpenDSA Project Contributors, and
   .. distributed under an MIT open source license.

.. avmetadata::
      :author: Cliff Shaffer
      :requires: 
      :satisfies: 
      :topic: Data Structures

NP Completeness Proof
==========================================

Reduction
----------


.. splicetoolembed:: https://acos.cs.vt.edu/parsons/pif/pb-reduction.peml
   :height: 600
   :width: 1050
   :name: pb-reduction

.. splicetoolembed:: https://acos.cs.vt.edu/parsons/pif/pb-sort2pair.peml
   :height: 800
   :width: 1050
   :name: pb-sort2pair


General NP Completeness Proof Process
----------------------------------------

.. splicetoolembed:: https://acos.cs.vt.edu/parsons/pif/pb-nptemplate-DAG.peml
   :height: 700
   :width: 1050
   :name: pb-nptemplate-DAG

 Independent Set
 -------------------------------

.. splicetoolembed:: https://acos.cs.vt.edu/parsons/pif/pb-Clique2IS-DAG.peml
   :height: 1150
   :width: 1050
   :name: pb-Clique2IS-DAG