University of Illinois Urbana-Champaign

Odd multiway cut in directed acyclic graphs

Mozaffari, Sahand

Content Files
MOZAFFARI-THESIS-2021.pdf

Permalink

https://hdl.handle.net/2142/113081

Description

Title
Odd multiway cut in directed acyclic graphs
Author(s)
Mozaffari, Sahand
Issue Date
2021-07-20
Director of Research (if dissertation) or Advisor (if thesis)
Chandrasekaran, Karthekeyan
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Date of Ingest
2022-01-12T21:46:57Z
Keyword(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.
Graduation Semester
2021-08
Type of Resource
Thesis
Permalink
http://hdl.handle.net/2142/113081
Copyright and License Information
Copyright 2021 Sahand Mozaffari

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Computer Science
Dissertations and Theses from the Siebel School of Computer Science