Files in this item

FilesDescriptionFormat

application/pdf

application/pdfMOZAFFARI-THESIS-2021.pdf (238kB)
(no description provided)PDF

Description

Title:Odd multiway cut in directed acyclic graphs
Author(s):Mozaffari, Sahand
Advisor(s):Chandrasekaran, Karthekeyan
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(s):Fixed-parameter Tractability
Graphs
Algorithm Design
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.
Issue Date:2021-07-20
Type:Thesis
URI:http://hdl.handle.net/2142/113081
Rights Information:Copyright 2021 Sahand Mozaffari
Date Available in IDEALS:2022-01-12
Date Deposited:2021-08


This item appears in the following Collection(s)

Item Statistics