On the hardness of computing maximum self-reduction sequences (Q1841907)

Various combinatorial problems on graphs can be approached by reducing the size of the graph according to certain rules (i.e., reducing complete subgraphs to one vertex). Here the authors show that computing maximum reduction sequences for the operation ``two-pair reduction'' [see, i.e., \textit{J. Fonlupt} and \textit{J. P. Uhry}, Ann. Discrete Math. 16, 83-95 (1982; Zbl 0502.05023)] is NP-hard. Thus there is no benefit for the solution of combinatorial graph problems using this reduction type. They also extend this result to other types and larger sets of self-reduction.