Reductions from Sigma2 SAT to m-ω-vertex-cost-of-stability and ω-vertex-cost-of-stability

Introduction:

This repository contains implementations of polynomial-time many-one reductions ($\leq^P_m$) from Sigma_2-SAT to m-ω-vertex-cost-of-stability and ω-vertex-cost-of-stability. Both reductions were implemented in python using jupyter notebooks. Since both m-ω-vertex-cost-of-stability and ω-vertex-cost-of-stability are graph problems based on the CLIQUE-problem, the graph library networkx was used to construct, analyze and draw graphs.

Usage:

1️⃣ Clone this repository using git clone.

2️⃣ Navigate into the cloned repository and run pip install -r requirements.txt to install all dependencies

3️⃣ Start jupyter or any code editor/IDE which is capable of rendering .ipynb files.

4️⃣ Always run ALL code blocks inside of the jupyter notebook after startup, since later code blocks override previous ones for educational purposes.

Mentions:

This work is based on publications in the area of Complexity Theory, especially Stability of Graphs, studied and published by Fabian Frei, Edith Hemaspaandra, Jörg Rothe and Robin Weishaupt.

Sources:

• [1] Fabian Frei, Edith Hemaspaandra, and Jörg Rothe. Complexity of stability. CoRR, abs/1910.00305, 2019.

• [2] Richard M. Karp. Reducibility among Combinatorial Problems, pages 85–103. Springer US, Boston, MA, 1972.

• [3] J. Rothe and R. Weishaupt, F. Frei, E. Hemaspaandra. Cost of stability. Manuscript, 2022.

• [4] R. Weishaupt. Stability of graphs and its costs. Master’s thesis, Heinrich-Heine- Universit#t Düsseldorf, July 2021.

License:

This repository is MIT licensed. More information can be found here LICENSE.