Algorithms Index

Algorithms Index

This page provides an organized index of all algorithm posts, grouped by topic and relationships.

NP-Completeness and Complexity Theory

Introduction to NP-Complete Problems

Core Problems:

• SAT (Boolean Satisfiability)
• 3-SAT - Special case of SAT with 3 literals per clause
• Clique
• Independent Set
• Vertex Cover
• Subset Sum
• Rudrata Path
• Rudrata Cycle
• Traveling Salesman Problem (TSP)
• Zero-One Equations (ZOE)
• 3D Matching
• Integer Linear Programming (ILP)

Reduction Reference Guides

• NP-Complete Reduction Examples - How to prove NP-completeness using reductions
• NP-Complete Reduction Reference - Common NP-complete problems for reductions

Reductions from SAT/3-SAT

• Reductions from SAT
• Reductions from 3-SAT
• 3-SAT to Partition
• 3-SAT to Exact 4-SAT
• SAT to Stingy SAT
• SAT to Max SAT
• SAT to Circuit Design

Reductions from Clique

• Reductions from Clique
• Clique to Subgraph Isomorphism
• Clique to Clique-3
• Clique to Dense Subgraph
• Clique to Kite
• Clique to Maximum Common Subgraph

Reductions from Independent Set

• Reductions from Independent Set
• Independent Set to Clique + Independent Set
• Independent Set to Sparse Subgraph

Reductions from Vertex Cover

• Reductions from Vertex Cover
• Vertex Cover to Hitting Set
• Vertex Cover to Set Cover
• Vertex Cover to Dominating Set
• Vertex Cover to Flower Search

Reductions from Rudrata Path/Cycle

• Reductions from Rudrata Path
• Reductions from Rudrata (s,t)-Path
• Reductions from Rudrata Cycle
• Rudrata Path to Longest Path
• Rudrata Path to Spanning Tree with k or Fewer Leaves
• Rudrata Path to Spanning Tree with Exact Leaves
• Rudrata (s,t)-Path to White and Gold Path
• Rudrata Cycle to TSP
• Rudrata Cycle to Reliable Network

Reductions from Subset Sum

• Reductions from Subset Sum
• Subset Sum to Knapsack

Reductions from Other Problems

• Reductions from Zero-One Equations (ZOE)
• Reductions from 3D Matching
• Reductions from ILP
• Reductions from TSP

Linear Programming (LP)

LP Fundamentals

• Linear Programming Fundamentals - LP basics, algorithms, duality, and applications
• Integer Linear Programming (ILP) Introduction - ILP as an NP-complete problem

LP Reductions

• Linear Programming Reductions - Reductions involving LP and ILP

Greedy Algorithms

• Greedy Algorithms Examples - Examples and applications of greedy algorithms

Problem Relationships

Graph Problems

• Clique ↔ Independent Set (complement graphs)
• Vertex Cover ↔ Independent Set (complement relationship)
• Clique → Subgraph Isomorphism → Maximum Common Subgraph
• Vertex Cover → Hitting Set → Set Cover
• Rudrata Path → Longest Path, Spanning Tree variants

SAT Variants

• SAT → 3-SAT → Exact 4-SAT
• SAT → Stingy SAT, Max SAT, Circuit Design

Number Problems

• Subset Sum → Partition → Knapsack

Network Problems

• Rudrata Cycle → TSP → Reliable Network

Study Paths

Starting with SAT

1. SAT Introduction
2. 3-SAT
3. Reductions from SAT
4. Reductions from 3-SAT

Starting with Graph Problems

1. Clique
2. Independent Set
3. Vertex Cover
4. Reductions from Clique
5. Reductions from Vertex Cover

Starting with Linear Programming

1. Linear Programming Fundamentals
2. Integer Linear Programming
3. Linear Programming Reductions

Learning Reduction Techniques

1. NP-Complete Reduction Examples
2. NP-Complete Reduction Reference
3. Individual reduction posts for specific techniques

---

Last updated: November 2025