Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts

Abstract

A skew-symmetric graph (D=(V,A),σ) is a directed graph D with an involution σ on the set of vertices and arcs. Flows on skew-symmetric graphs have been used to generalize maximum flow and maximum matching problems on graphs, initially by Tutte and later by Goldberg and Karzanov. In this article, we introduce a separation problem, d-Skew-Symmetric Multicut, where we are given a skew-symmetric graph D, a family τ of d-size subsets of vertices, and an integer k. The objective is to decide whether there is a set X ⊑ A of k arcs such that every set J in the family has a vertex υ such that υ and σ(υ) are in different strongly connected components of D′=(V,A \ (X ∪ σ(X)). In this work, we give an algorithm for d-Skew-Symmetric Multicut that runs in time O((4d)k(m+n+ℓ)), where m is the number of arcs in the graph, n is the number of vertices, and ℓ is the length of the family given in the input.