Header menu link for other important links
X
Odd Cycle Transversal in Mixed Graphs
A. Das, , J. Madathil, S. Saurabh
Published in Springer Science and Business Media Deutschland GmbH
2021
Volume: 12911 LNCS
   
Pages: 130 - 142
Abstract
An odd cycle transversal (oct, for short) in a graph is a set of vertices whose deletion will leave a graph without any odd cycles. The Odd Cycle Transversal (OCT) problem takes an undirected graph G and a non-negative integer k as input, and the objective is to test if G has an oct of size at most k. The directed counterpart of the problem, Directed Odd Cycle Transversal (DOCT), where the input is a digraph and k, is defined analogously. When parameterized by k, OCT is known to be FPT [Reed et al., Oper. Res. Lett., 2004] whereas DOCT was recently shown to be W[1]-hard [Lokshtanov et al., SODA, 2020]. A mixed graph is a graph that contains both directed and undirected edges. In this paper, we study the Mixed Odd Cycle Transversal (MOCT) problem, i.e., OCT on mixed graphs. And we show that MOCT admits a fixed-parameter tractable algorithm when parameterized by k+ ℓ, where ℓ is the number of directed edges in the input mixed graph. In the course of designing our algorithm for MOCT, we also design a fixed-parameter tractable algorithm for a variant of the well-known Multiway Cut problem, which might be of independent interest. © 2021, Springer Nature Switzerland AG.
About the journal
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Science and Business Media Deutschland GmbH
ISSN03029743