Search

We confirm a conjecture of Gartland and Lokshtanov [SODA 2023]: if for a hereditary graph class G there exists a constant k such that no member of G contains a k-creature as an induced subgraph or a k-skinny-ladder as an induced minor, then there exists a polynomial p such that every G ∈ G contains at most p(|V(G)|) minimal separators. By a result of Fomin, Todinca, and Villanger [SIAM J. Comput., 44 (2015), pp. 54-87] the latter entails the existence of polynomial-time algorithms for MAXIMUM WEIGHT INDEPENDENT SET, FEEDBACK VERTEX SET and many other problems, when restricted to an input graph from G. Furthermore, as shown by Gartland and Lokshtanov, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators). [ABSTRACT FROM AUTHOR]

One of the first applications of the recently introduced technique of flow augmentation [Kim et al., STOC 2022] is a fixed-parameter algorithm for the weighted version of Directed Feedback Vertex Set, a landmark problem in parameterized complexity. In this article, we explore the applicability of flow augmentation to other weighted graph separation problems parameterized by the size of the cutset. We show the following: \bullet In weighted undirected graphs, Multicut is fixed-parameter tractable (FPT) in both the edge- and the vertex-deletion version. \bullet The weighted version of Group Feedback Vertex Set is FPT, even with oracle access to group operations. \bullet The weighted version of Directed Subset Feedback Vertex Set is FPT. Our study reveals Directed Symmetric Multicut as the next important graph separation problem whose parameterized complexity remains unknown, even in the unweighted setting. [ABSTRACT FROM AUTHOR]