Summary: In this paper, we study a parity based generalization of the classical multiway cut problem. Formally, we study the parity multiway cut problem, where the input is a graph \(G\), vertex subsets \(T _{e }\) and \(T _{o }\) \((T = T _{e } \cup T _{o })\) called terminals, a positive integer \(k\) and the objective is to test whether there exists a \(k\)-sized vertex subset \(S\) such that \(S\) intersects all odd paths from \(v \in T _{o }\) to \(T \setminus \{v\}\) and all even paths from \(v \in T _{e }\) to \(T \setminus \{v\}\). When \(T _{e } = T _{o }\), this is precisely the classical multiway cut problem. If \(T _{o } = \emptyset \) then this is the even multiway cut problem and if \(T _{e } = \emptyset \) then this is the odd multiway cut problem. We remark that even the problem of deciding whether there is a set of at most \(k\) vertices that intersects all odd paths between a pair of vertices \(s\) and \(t\) is NP-complete. Our primary motivation for studying this problem is the recently initiated parameterized study of parity versions of graphs minors and separation problems similar to multiway cut. The area of design of parameterized algorithms for graph separation problems has seen a lot of recent activity, which includes algorithms for multi-cut on undirected graphs, \(k\)-way cut, and multiway cut on directed graphs. A second motivation is that this problem serves as a good example to illustrate the application of a generalization of important separators which we introduce, and can be applied even when most of the recently develped tools fail to apply. We believe that this could be a useful tool for several other separation problems as well. We obtain this generalization by dividing the graph into slices with small boundaries and applying a divide and conquer paradigm over these slices. We show that parity multiway cut is fixed parameter tractable (FPT) by giving an algorithm that runs in time \(f(k)n^{O(1)}\). More precisely, we show that instances of this problem with solutions of size \(O(\log \log n)\) can be solved in polynomial time. Along with this new notion of generalized important separators, our algorithm also combines several ideas used in previous parameterized algorithms for graph separation problems including the notion of important separators and randomized selection of important sets to simplify the input instance.
For the entire collection see [Zbl 1268.68011].