{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/113081"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/113081","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Odd multiway cut in directed acyclic graphs","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Mozaffari, Sahand"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Chandrasekaran, Karthekeyan"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-01-12T21:46:57Z","date_published":"2022-01-12T21:46:57Z","updated_at":"2026-07-22T22:24:53Z","subjects":["Fixed-parameter Tractability","Graphs","Algorithm Design"],"languages":["en"],"rights":["Copyright 2021 Sahand Mozaffari"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/113081","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Chandrasekaran, Karthekeyan"]},{"key":"dc:creator","label":"Author","values":["Mozaffari, Sahand"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-01-12T21:46:57Z","2021-07-20","2021-08"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Fixed-parameter Tractability","Graphs","Algorithm Design"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2021 Sahand Mozaffari"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/113081"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Odd multiway cut in directed acyclic graphs"]}]}],"canonical_facts":{"dc:contributor":["Chandrasekaran, Karthekeyan"],"dc:creator":["Mozaffari, Sahand"],"dc:date":["2022-01-12T21:46:57Z","2021-07-20","2021-08"],"dc:description":["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"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/113081"],"dc:language":["en"],"dc:rights":["Copyright 2021 Sahand Mozaffari"],"dc:subject":["Fixed-parameter Tractability","Graphs","Algorithm Design"],"dc:title":["Odd multiway cut in directed acyclic graphs"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:53Z"}