Room 327

Important Separators: Old and New

Rian Neogi [Credit Seminar]

IMSc

We will look at the notion of important separators. We will see how they help in providing us FPT algorithms for the problem of Directed Feedback Arc Set. Next we will look at the problem of finding a Multi-budgeted cut, where we are given a p-coloring on the edges and integers k_1,...,k_p and we need to find an s-t cut that picks atmost k_i edges of color i. We will extend the notion of important separators to the multi-budgeted variant give an algorithm for the Multi-budgeted Directed Feedback Arc Set problem.