main page — CS 627 Advanced Algorithms

NP-Completeness Mini-Seminar

The mini-seminar on NP-completeness is a small seminar component as part of Advanced Algorithms.

It serves both as a refresher of classic complexity theory techniques (as a preparation for remainder of the module) and to practice working with primary research literature.

Content

Via this seminar, we will relive the birth of the theory of NP-completeness, which led to two Turing Awards (Stephen Cook and Richard Karp).

After the observation that the Boolean satisfiability problem is NP-complete (Cook-Levin theorem), Richard Karp kickstarted the field of NP-completeness with a single paper, Reducibility Among Combinatorial Problems (1972), in which he discussed 21 algorithmic problems and proved their NP-completeness by reductions from the satisfiability problem.

The specific topics for the group work will be the following reductions. Note that these use the names from the paper, but you should (where applicable) also state the more modern names from the literature, such as vertex cover and 3SAT.

Satisfiability $\le_p$ 0-1-IntegerProgramming
Satisfiability $\le_p$ Clique
Clique $\le_p$ SetPacking
Clique $\le_p$ NodeCover
NodeCover $\le_p$ SetCovering
NodeCover $\le_p$ FeedbackNodeSet
NodeCover $\le_p$ FeedbackArcSet
* NodeCover $\le_p$ DirectedHamiltonianCircuit
DirectedHamiltonianCircuit $\le_p$ UndirectedHamiltonianCircuit
Satisfiability $\le_p$ SatisfiabilityWithAtMost3LiteralsPerClause
SatisfiabilityWithAtMost3LiteralsPerClause $\le_p$ ChromaticNumber
ChromaticNumber $\le_p$ CliqueCover
ChromaticNumber $\le_p$ ExactCover
ExactCover $\le_p$ HittingSet
ExactCover $\le_p$ SteinerTree
ExactCover $\le_p$ 3DimensionalMatching
ExactCover $\le_p$ Knapsack
(Knapsack $\le_p$ JobSequencing)
Knapsack $\le_p$ Partition
Knapsack $\le_p$ MaxCut

Reduction 18 (Knapsack $\le_p$ JobSequencing) is too easy to make for a group work, so it is not eligible. It is included above for completeness.
Reduction 8 (NodeCover $\le_p$ DirectedHamiltonianCircuit) is a bit more involved than most of the others, but you are welcome to select it if you enjoy a (slight) challenge.

Further reductions from other sources can be added if needed.

Organization & Deliverables

Each group of 3–4 students will work out the details of one of the reductions above. Reductions are assigned on a first-come-first-serve basis here. You have to book your topic as a group, so please coordinate with your group members before booking.

There will be no synchronous presentations, but each group will prepare

a short report (2–4 pages) with the formal proof with full detail,
the report must include two examples illustrating the reduction, one Yes- and one No-instance, and
a video presentation (5–10 minutes) explaining your problem and the reduction.

These have to be submitted on ILIAS until 9 May 2025, 5pm.

Peer-Review Phase

After the submission deadline, each group will be assigned to review works of other groups using a structured questionnaire. The peer-review phase will be open from 10 May 2025, 9am until 17 May 2025, 5pm. More details will be provided in due course.

Resouces

Collaboration & GenAI Policy

This programming puzzle is an individual project, and you have to submit you own solution. As for all assessments, the University of Liverpool Policy on Academic Integrity applies; please refer to the Canvas page for details.

The use of generative AI for producing solutions to this assessment is not encouraged since it is intended to be worked on to build intuitions on the algorithmic problems. Using tools to generate code (such as GitHub Copilot) is allowed for routine code, but strongly discouraged for generating algorithmic solutions. If you are using generative AI in any form, it has to be documented as precisely as possible. For example, for ChatGPT, you are required to include your chat as an appendix.