Finding a maximum minimal separator: Graph classes and fixed-parameter tractability

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 there is no 2 o ( n ) n O ( 1 ) -time algorithm unless the Exponential Time Hypothesis (ETH) fails. Finally, we discuss a lower bound for polynomial kernelizations of this problem.

Authors

• Tesshu Hanaka Kyushu University
• Yasuaki Kobayashi Hokkaido University
• Yusuke Kobayashi Kyoto University
• Tsuyoshi Yagita

Keywords

• Minimal separator
• Fixed-parameter tractability
• Treewidth
• NP-hardness