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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree

  • Christian Komusiewicz,
  • Diptapriyo Majumdar

摘要

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.