Refined notions of parameterized enumeration kernels with applications to matching cut enumeration (Q2237892)

Intuitively, in the area of enumeration complexity, one aims for enumeration algorithms outputting all solutions of a given problem instance without printing duplicates. Here, one classifies algorithms by their overall runtime in the input and output length as well as by their delay. The delay is a runtime bound for consecutively printed solutions. In parameterized enumeration complexity, one studies delays from above of the form \(f(k)\cdot|x|^{O(1)}\), where \(f\) is a computable function, \(x\) the input and \(k\) the value of the parameter, e.g., one studies FPT(-delay) enumeration algorithms. A few years ago, \textit{N. Creignou} et al. [Theory Comput. Syst. 60, No. 4, 737--758 (2017; Zbl 1368.68221)] introduced the concept of an enum-kernel that lifts the idea from classical parameterized kernels to the parameterized enumeration setting. For the compressed instance (the kernel) it is required to generate the solution set of the original instance with FPT-delay (the so-called solution-lifting algorithm). This concept has been shown to work for a bunch of presented problems and is shown to characterize the class DelayFPT. This paper introduces two new versions of enumeration kernels, namely fully-polynomial enumeration as well as polynomial-delay enumeration kernels. These kernels are stricter than the enum-kernels of Creignou et al. on the level of the solution-lifting algorithm: the solution-lifting algorithm must run in polynomial time or with polynomial delay. At first sight, this might seem like a simple modification; however, the authors motivate these modifications well and justify them with a multitude of results. More specifically, they study the NP-hard problem MATCHING CUT (MC), and two variants of it (minimal and maximal) with respect to these new kernels and a long list of parameterizations (tree-/clique-/modular width, vertex cover/twin-cover/cyclomatic/clique partition number, neighborhood diversity). The authors give a brief introduction to the topic and immediately present their results. After mentioning related work, they start with introducing graph preliminaries. Then they introduce the new kernel versions. Theorem 2 justifies their approach by proving the equivalence of their kernels to FPT-enumeration/-delay algorithms. Section 3 studies upper and lower bounds for the number of (maximal/minimal) matching cuts in a graph and shows it to be tight for paths. Section 4 considers the parameter vertex-cover number and presents a fully-polynomial enumeration kernel for MINIMAL MC and P-delay (even linear delay!) kernels of quadratic size for the other two problems (ALL/MAXIMAL), and extend this result (the linear delay from before becomes P-delay though) to the vertex-cover number of the true-twin quotient graph (the twin-cover number has been introduced by \textit{R. Ganian} [Lect. Notes Comput. Sci. 7112, 259--271 (2012; Zbl 1352.68105)]). Section 5 is about the cyclomatic number as the parameter. Here, the authors show for MINIMAL and ALL a P-delay enum-kernel of linear size. In Section 6, they study the feedback edge number and show a P-delay enum-kernel with \(O(k)\) vertices for MINIMAL MC as well as for MC. Finally, they close this section with Corollary 3 (minimal matching cuts of an \(n\)-vertex graph can be enumerated with FPT-delay). Section 7 is about the clique partition number. In the appendix, many of the proofs are given (the only proofs in the main part are for Theorem 2.3 and the three-pages sketch in Section 5. Also, the results (and proof details) for the parameters neighborhood diversity, modular width, and clique partition number are contained only in the appendix. I enjoyed reading the paper. It is carefully written in a clear and comprehensible way. Furthermore, the authors do well in explaining their choices as well as in motivating their decisions. The presented context with other utilized results is of sufficient depth. The authors present also a good conclusion and outlook on further steps.