Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree
摘要
We consider the NP-complete \(d\) -Cut problem in the context of enumeration kernelization. The decision version of \(d\) -Cut asks if a given undirected graph G has a cut (A, B) such that every \(u \in A\) has at most d neighbors in B and every \(v \in B\) has at most d neighbors in A. We study various structural parameterizations of three different enumeration variants of the problem–Enum \(d\) -Cut, Enum Min- \(d\) -Cut and Enum Max- \(d\) -Cut in which one aims to enumerate all d-cuts, all inclusion-wise minimal d-cuts, and all inclusion-wise maximal d-cuts, respectively. For parameterization by vertex cover number ( \({\textsf {vc}}\) ) and neighborhood diversity ( \({\textsf {nd}}\) ) we provide polynomial-delay enumeration kernels of polynomial size for Enum \(d\) -Cut and Enum Max- \(d\) -Cut and fully-polynomial enumeration kernels of polynomial size for Enum Min- \(d\) -Cut. For parameterization by the clique partition number ( \({\textsf {pc}}\) ), we provide bijective enumeration kernels for all three problems.