2026-09-19T20:23:48Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/113081 2023-07-11 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Chandrasekaran, Karthekeyan Mozaffari, Sahand 2022-01-12T21:46:57Z 2022-01-12T21:46:57Z 2021-07-20 2021-08 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 non-terminal 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. Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-01-12 without embargo terms The student, Sahand Mozaffari, accepted the attached license on 2021-07-20 at 15:01. The student, Sahand Mozaffari, submitted this Thesis for approval on 2021-07-20 at 15:06. This Thesis was approved for publication on 2021-07-20 at 15:38. DSpace SAF Submission Ingestion Package generated from Vireo submission #17031 on 2022-01-12 at 12:46:27 Made available in DSpace on 2022-01-12T21:46:57Z (GMT). No. of bitstreams: 2 MOZAFFARI-THESIS-2021.pdf: 238109 bytes, checksum: 09e27375db3a7047f261b1c393f42468 (MD5) LICENSE.txt: 4213 bytes, checksum: 182b08340af945720e392828b9f11804 (MD5) Previous issue date: 2021-07-20 application/pdf http://hdl.handle.net/2142/113081 en Copyright 2021 Sahand Mozaffari Fixed-parameter Tractability Graphs Algorithm Design Odd multiway cut in directed acyclic graphs text Thesis Computer Science Computer Science University of Illinois at Urbana-Champaign Thesis M.S.