Refined Notions of Parameterized Enumeration Kernels with Applications\n to Matching Cut Enumeration

An enumeration kernel as defined by Creignou et al. [Theory Comput. Syst.\n2017] for a parameterized enumeration problem consists of an algorithm that\ntransforms each instance into one whose size is bounded by the parameter plus a\nsolution-lifting algorithm that efficiently enumerates all solutions from the\nset of the solutions of the kernel. We propose to consider two new versions of\nenumeration kernels by asking that the solutions of the original instance can\nbe enumerated in polynomial time or with polynomial delay from the kernel\nsolutions. Using the NP-hard Matching Cut problem parameterized by structural\nparameters such as the vertex cover number or the cyclomatic number of the\ninput graph, we show that the new enumeration kernels present a useful notion\nof data reduction for enumeration problems which allows to compactly represent\nthe set of feasible solutions.\n