A Min-Max Theorem on Feedback Vertex Sets

DOI10.1287/moor.27.2.361.328zbMath1082.90583OpenAlexW2047739168MaRDI QIDQ5704082

Wenan Zang, Xiaotie Deng, Mao-cheng Cai

Publication date: 11 November 2005

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.27.2.361.328

zbMATH Keywords

feedback vertex set, bipartite tournament, totally dual integrality, min-max relation, approximation algorithm

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)

Related Items (17)

Feedback arc set in bipartite tournaments is NP-complete ⋮ Improved FPT algorithm for feedback vertex set problem in bipartite tournament ⋮ A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments ⋮ Feedback vertex sets on restricted bipartite graphs ⋮ Packing cycles in graphs. II ⋮ Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem ⋮ Packing directed circuits exactly ⋮ Two Hardness Results on Feedback Vertex Sets ⋮ Analysis, calculation and utilization of the \(k\)-balance attribute in interdependent networks ⋮ Improved approximation algorithm for the feedback set problem in a bipartite tournament ⋮ On the minimum feedback vertex set problem: Exact and enumeration algorithms ⋮ Linear programming based approximation algorithms for feedback set problems in bipartite tournaments ⋮ A quadratic vertex kernel for feedback arc set in bipartite tournaments ⋮ Fixed-parameter tractability results for feedback set problems in tournaments ⋮ Triangle packing in (sparse) tournaments: approximation and kernelization ⋮ Unnamed Item ⋮ Fixed-parameter tractability for subset feedback set problems with parity constraints

This page was built for publication: A Min-Max Theorem on Feedback Vertex Sets