Algorithms : problems cheatsheet

TODO : update this page, add complexity th

Vertex cover

Data : an undirected graph $G$
Problem : find a minimum cardinality set of vertices that covers all edges

Hamiltonian path

Data : an undirected graph $G$
Problem : is there a path going once and only once through each vertex ?

SAT

Data : a boolean formula
Problem : is there an assignment of variables that make this formula true

Independant set (stable)

Data : an undirected graph $G$ and an integer $k$
Problem : does there exist a set with at least k vertices that do not contain any pair of neighboring vertices ?

Hitting set

Data : a collection $C$ of $m$ subsets of $\{1,...,n\}$
Problem : find a minimum cardinality subset of $\{1,...,n\}$ that contains at least one element of each subset of $C$

References

• Polytechnique course - INF550 - Advanced Algorithms by G. Schaeffer