Listing Small Minimal Separators of a Graph

2020/12/16 by Tuukka Korhonen, Korhonen, Tuukka
Computer Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #cs.DS

paper · pdf · doi:10.48550/arxiv.2012.09153

9 pages

arxiv created 2020/12/16 · arxiv updated 2020/12/17

Abstract

Let G be a graph and a,b vertices of G. A minimal a,b-separator of G is an inclusion-wise minimal vertex set of G that separates a and b. We consider the problem of enumerating the minimal a,b-separators of G that contain at most k vertices, given some integer k. We give an algorithm which enumerates such minimal separators, outputting the first R minimal separators in at most poly(n) R ⋅ min(4^k, R) time for all R. Therefore, our algorithm can be classified as fixed-parameter-delay and incremental-polynomial time. To the best of our knowledge, no algorithms with non-trivial time complexity have been published for this problem before. We also discuss barriers for obtaining a polynomial-delay algorithm.

Related

• Listing Small Minimal s,t-separators in FPT-Delay
• Enumerating Minimal Separators in Ranked Order
• Finding a Maximum Minimal Separator: Graph Classes and Fixed-Parameter Tractability
• A linear-time algorithm to find a separator in a graph excluding a minor
• On the hardness of inclusion-wise minimal separators enumeration