Good evening, I am following a combinatorial optimization lecture and we are now working on complexity and reduction through the appreciation/recognition associated problem of the maximal stable set problem(translated from the French problme de reconnaissance associ, for which I provide a definition in the end). We used an example to show how to proceed which I didn't understood :I didn't understood the proof why if we had an algorithm for the solving the appreciation/recognition associated problem of the maximal stable set problem we would have an algorithm for the maximal stable set problem.Especially the related algorithm that would substitute and solve the first maximal stable problem.a maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is maximal with respect to the independent set property.Proof:We are going to show that if we knew a polynomial algorithm to to solve the appreciation/recognition associated problem of the maximal stable set problem(translated from the French problme de reconnaissance associ) we would have an algorithm for the maximal stable set problem.appreciation/recognition associated problem of the maximal stable set problemGiven  $k\in \mathbb{N}$, does it exists a stable of cardinality greater or equal to $k$?Look for a maximal stable set.FOR (k=i from 1 to n) \\\n =|V| the vertices number    We solve 1. for k=i    IF(k0) is the first integer such that 1. is FALSE        THEN RETURN k0-1 reduction of the maximal stable set problem to appreciation/recognition associated problemIf we can solve the maximal stable set with weights $\ge 0$ on the vertices. can we solve the actual problem if we can solve if it exists a stable with weights greater or equals to $k$?Yes, using the same procedure than preceding but the algorithm would have been proportional to the data size.I don't understood how the algorithm in the second part of the appreciation/recognition associated problem solve the maximal stable problem.Appendix : the general appreciation/recognition associated problem definitionGiven a combinatorial optimization problemFind  - an $\hat p$ problem such that $f(p)=\max_{p\in s}f(s)$ (respectivley   $\min_{p\in s}f(0)$ - a number a, we define the appreciation/recognition associated problem as $$\exists s^*\in s, f(s^*)\ge a$$respectively $f(s^*)\le a$
Reduction of the maximal stable set problem
algorithms;complexity theory;graph theory;reductions