论文标题
查找最大最小分离器：图形类和固定参数障碍性
Finding a Maximum Minimal Separator: Graph Classes and Fixed-Parameter Tractability
论文作者
论文摘要
我们研究了发现图的最大基数最小分离器的问题。即使对于两分图，也已知该问题是NP-HARD。在本文中，我们通过证明对于平面两分的图来增强这种硬度，问题仍然是NP-HARD。此外，对于共同图形和线路图，问题也仍然是NP-HARD。从积极的一面来看，我们给出了一种算法，以确定输入图是否具有最小的大小的分离器至少$ k $，该分离器在时间上运行$ 2^{o（k）} n^{o（1）} $。我们进一步表明，除非指数时间假设（ETH）失败，否则不存在亚指数参数化算法。最后，我们讨论了该问题多项式核的下限。
We study the problem of finding a maximum cardinality minimal separator of a graph. This problem is known to be NP-hard even for bipartite graphs. In this paper, we strengthen this hardness by showing that for planar bipartite graphs, the problem remains NP-hard. Moreover, for co-bipartite graphs and for line graphs, the problem also remains NP-hard. On the positive side, we give an algorithm deciding whether an input graph has a minimal separator of size at least $k$ that runs in time $2^{O(k)}n^{O(1)}$. We further show that a subexponential parameterized algorithm does not exist unless the Exponential Time Hypothesis (ETH) fails. Finally, we discuss a lower bound for polynomial kernelizations of this problem.
