## Full WriteUp

Full Writeup on our website: [https://www.aperikube.fr/docs/inshack_2019/proggenius/](https://www.aperikube.fr/docs/inshack_2019/proggenius/)

## TL;DR

This was a minimal dominating set problem which is a NP-Hard problem. This problem can be solved by computing the node with the most occurrences, remove the lines in which the node is, then compute the new node with the most occurrences… until there is no line left. This gave us a “127” solution.
The solution expected for the latest challenge was “126” so I decided to keep every 127 solutions, keep their first starting nodes and bruteforce the 2nd node, then compute the end using the same algorithm and here it is, we got a “126” solution.