Finding minimal separators with small cardinality in graphs

Abstract: Finding minimal s-t vertex separators of an undirected graph appears as a sub-problem in several algorithms (e.g in finding tree decompositions) parametrized by Treewidth. Finding small minimal s-t separators is of particular interest, since they lead to a faster solution to the original problem. We present an algorithm for retrieving minimal s-t separators whose cardinality is at most K. The algorithm runs in FPT-delay parametrized by K, thus by controlling the value of K we can ensure that the returned separators are small, while controlling the algorithm’s delay complexity. We present experimental results, showing a comparison between our algorithm and the backtracking algorithm of Ken Takata. We have implemented the Takata algorithm, our new algorithm for enumerating minimal separators and another algorithm for ranked enumeration of s-t (not necessarily minimum), using the open-source Python library NetworkX, and demonstrated that the algorithm can achieve time delays several orders of magnitude smaller than the Takata algorithm, for small values of K. We have implemented a new python library for the algorithms. This implementation includes an extension code in C that uses the property of bounding the parameter K, to improve the performance of the Ford-Fulkerson algorithm implementation in NetworkX which was found to be the most critical process limiting retrieval speed. We conclude that our algorithm can perform well comparing to the Takata algorithm on random graphs with edge probabilities of up to 0.6, and on some of the graphs used in the PACE-2017 competition.