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

DOI10.1016/J.TCS.2021.03.006MaRDI QIDQ2661784zbMATH OpenOpenAlexFDO

Authors Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Tsuyoshi Yagita

Publication date 8 April 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.12184

zbMATH Keywords

fixed-parameter tractabilityminimal separatorNP-hardnesstreewidth

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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.

Recommendations

• On the maximum weight minimal separator
• On the maximum weight minimal separator
• On the parameterized complexity of finding separators with non-hereditary properties
• On the parameterized complexity of finding separators with non-hereditary properties
• Finding small separators in linear time via treewidth reduction

Cites work

• An introduction to clique minimal separator decomposition
• Approximation and intractability results for the maximum cut problem and its variants
• Clustering and domination in perfect graphs
• Computing the largest bond of a graph
• Exact Algorithms for Treewidth and Minimum Fill-In
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• scientific article; zbMATH DE number 1420906 (Why is no real title available?)
• scientific article; zbMATH DE number 7650221 (Why is no real title available?)
• Independent dominating set problem revisited
• Kernelization. Theory of parameterized preprocessing
• Large Induced Subgraphs via Triangulations and CMSO
• Linear time solvable optimization problems on graphs of bounded clique-width
• Lower bounds based on the exponential time hypothesis
• Minimal separators in graph classes defined by small forbidden induced subgraphs
• Minimum Fill-in on Circle and Circular-Arc Graphs
• On interval routing schemes and treewidth
• On problems without polynomial kernels
• On rigid circuit graphs
• On the complexity of k-SAT
• On the maximum weight minimal separator
• On the number of minimal separators in graphs
• Parameterized algorithms
• The Pathwidth and Treewidth of Cographs
• Towards tight(er) bounds for the excluded grid theorem
• Treewidth and minimum fill-in: Grouping the minimal separators
• Treewidth and Pathwidth of Permutation Graphs

Cited in

(6)

• On the maximum weight minimal separator
• Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques
• On the maximum weight minimal separator
• Treewidth reduction for constrained separation and bipartization problems
• Bisimplicial separators
• Parameterized max min feedback vertex set

This page was built for publication: Finding a maximum minimal separator: graph classes and fixed-parameter tractability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2661784)