Reviews: The Cluster Description Problem - Complexity Results, Formulations and Approximations

The main contributions of the paper are: - Formulating a cluster description problem as a combinatorial optimisation problem to find descriptions for clusters that are descriptive and non-overlapping - Showing NP-completeness of the problem, even if there are only two clusters - Providing ILP encodings modelling (also extended) variants of the problem - Providing a tractable subclass of the problem, and together with a polynomial time algorithm for this subclass Pros: - A novel problem that is relevant by providing explanations for previously computed clusterings - Well-written paper with a clear focus and clear contributions Cons: - In lines 102–103, it is stated that some version of DTDF can be reduced to SAT. Should not this be 2-SAT? Since DTDF is shown to be NP-complete, all versions of DTDF can be reduced to SAT, right? The NP-completeness should hold in general (if not, it should not be possible to devise and ILP encoding for the problem). While I did not check all the details in the supplementary, the constructions for reductions seem sound.