2023/07/02 by Batya Kenig, Kenig, Batya
Computer Science · #Advanced Database Systems and Queries #Complexity and Algorithms in Graphs #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2307.00604
openalex publication_date 2023/07/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be an undirected graph, and s,t distinguished vertices of G. A minimal s,t-separator is an inclusion-wise minimal vertex-set whose removal places s and t in distinct connected components. We present an algorithm for listing the minimal s,t-separators of a graph, whose cardinality is at most k, with FPT-delay, where the parameter depends only on k. This problem finds applications in various algorithms parameterized by treewidth, which include query evaluation in relational databases, probabilistic inference, and many more. We also present a simple algorithm that enumerates all of the (not necessarily minimal) s,t-separators of a graph in ranked order by size.