Odd multiway cut in directed acyclic graphs

Publikationstyp
Journal Article
Publikationsdatum
2020
Sprache
English
Author
Chandrasekaran, Karthekeyan 
Mnich, Matthias orcid-logo
Mozaffari, Sahand 
Institut
Algorithmen und Komplexität E-11 
TORE-URI
http://hdl.handle.net/11420/5836
Enthalten in
SIAM journal on discrete mathematics 
Citation
SIAM Journal on Discrete Mathematics (2020)
Publisher DOI
10.1137/18M1176087
Scopus ID
2-s2.0-85092422410
ArXiv ID
1708.02323v2
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.
Schlagworte
Computer Science - Data Structures and Algorithms
G.2.2
I.1.2