Linear Programming & Combinatorial Optimization (2022) Lecture-5

In today's lecture (24/01/2022):

We first discussed, at an intuitive level, why P is a subset of NP intersection co-NP (which is an important theorem in complexity theory). Since one of our main goals (in this course) is to study efficient algorithms for combinatorial optimization problems, we'll also be interested in NP and co-NP certificates for various decision problems.

Thereafter, we discussed the fundamental notion of an M-augmenting path (with respect to a fixed matching M in a graph G). If such a path P exists then the symmetric difference of M and P yields another matching (of cardinality |M| + 1).

In the next lecture (27/01/2022), we'll discuss Berge's Lemma which states that an M-augmenting path always exists (unless M is a maximum matching). All of the combinatorial algorithms to find a maximum matching rely on Berge's Lemma --- in particular, they find an M-augmenting path at each step until a maximum matching is found.

[newbie]

Never mind, I found the mistake. M can have sth that P doesn't have. An augmenting path P doesn't have to include all vertices in M.

[newbie]

Question: if maximum stable set is in Co-NP, shouldn't it be Co-NP-hard instead of NP-hard?