(Not an assignment)
Motivation: You can imagine a street of houses, and we consider two houses to be neighbors if the distance between them is no more than 10 houses. We want a minimal set of representatives so that at least each house is represented by itself or one of its neighbors. I have therefore represented each house by a vertex and all sets of neighbors are represented by cliques (a house or a vertex can belong to several cliques).
Problem formulation:
There is given undirected graph $G$ of $n$ vertices.
I'm looking for $A=\{v_0,...,v_k\}$ which represents the minimal set of vertices where : each clique $c$ in $G$ with size $k$ have at least one vertex $v_i$ in commun with $A$.
Or :
find the minimal set $A$ of vertices, if we remove these vertices there will be no clique of size $k$ in
Thank you in advance for help.
This problem is equivalent to finding a minimum dominating set, if we represent the street of houses as a graph where each house is a vertex and each two neighbouring houses are represented as an edge between the two corresponding vertices.
This problem in general is NP-complete, but the specific problem above is easily solvable; simply choose the $11$th house, $32$rd house, $53$th house, $74$th house, etc. to ensure that every house is within a $10$-house distance from the selected houses.