  We investigate the odd multiway node (edge) cut problem where the input is a
graph with a specified collection of terminal nodes and the goal is to find a
smallest subset of nonterminal nodes (edges) to delete so that the terminal
nodes do not have an odd length path between them. In an earlier work,
Lokshtanov and Ramanujan showed that both odd multiway node cut and odd
multiway edge cut are fixed-parameter tractable (FPT) when parameterized by the
size of the solution in undirected graphs. In this work, we focus on directed
acyclic graphs (DAGs) and design a fixed-parameter algorithm. Our main
contribution is a broadening of the shadow-removal framework to address parity
problems in DAGs. We complement our FPT results with tight approximability as
well as polyhedral results for 2 terminals in DAGs. Additionally, we show
inapproximability results for odd multiway edge cut in undirected graphs even
for 2 terminals.
