A min-max theorem on feedback vertex sets

Mao-Cheng Cai; Xiaotie Deng; Wenan Zang

doi:10.1287/moor.27.2.361.328

A min-max theorem on feedback vertex sets

Mao-Cheng Cai
, Xiaotie Deng
, Wenan Zang

Department of Computer Science

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

35 Citations (Scopus)

Abstract

We establish a necessary and sufficient condition for the linear system {x : Hx ≥ e, x ≥ 0} associated with a bipartite tournament to be totally dual integral, where H is the cycle-vertex incidence matrix and e is the all-one vector. The consequence is a min-max relation on packing and covering cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem on the corresponding bipartite tournaments. In addition, we show that the feedbank vertex set problem on general bipartite tournaments is NP-complete and approximable within 3.5 based on the min-max theorem.

Original language	English
Pages (from-to)	361-371
Journal	Mathematics of Operations Research
Volume	27
Issue number	2
DOIs	https://doi.org/10.1287/moor.27.2.361.328
Publication status	Published - May 2002

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Research Keywords

Approximation algorithm
Bipartite tournament
Feedback vertex set
Min-max relation
Totally dual integrality

Access Output

10.1287/moor.27.2.361.328

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{b0fbb0ad50054777ab2ce29c55844f8e,

title = "A min-max theorem on feedback vertex sets",

abstract = "We establish a necessary and sufficient condition for the linear system \{x : Hx ≥ e, x ≥ 0\} associated with a bipartite tournament to be totally dual integral, where H is the cycle-vertex incidence matrix and e is the all-one vector. The consequence is a min-max relation on packing and covering cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem on the corresponding bipartite tournaments. In addition, we show that the feedbank vertex set problem on general bipartite tournaments is NP-complete and approximable within 3.5 based on the min-max theorem.",

keywords = "Approximation algorithm, Bipartite tournament, Feedback vertex set, Min-max relation, Totally dual integrality",

author = "Mao-Cheng Cai and Xiaotie Deng and Wenan Zang",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "2002",

month = may,

doi = "10.1287/moor.27.2.361.328",

language = "English",

volume = "27",

pages = "361--371",

journal = "Mathematics of Operations Research",

issn = "0364-765X",

publisher = "Institute for Operations Research and the Management Sciences (INFORMS)",

number = "2",

}

TY - JOUR

T1 - A min-max theorem on feedback vertex sets

AU - Cai, Mao-Cheng

AU - Deng, Xiaotie

AU - Zang, Wenan

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 2002/5

Y1 - 2002/5

N2 - We establish a necessary and sufficient condition for the linear system {x : Hx ≥ e, x ≥ 0} associated with a bipartite tournament to be totally dual integral, where H is the cycle-vertex incidence matrix and e is the all-one vector. The consequence is a min-max relation on packing and covering cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem on the corresponding bipartite tournaments. In addition, we show that the feedbank vertex set problem on general bipartite tournaments is NP-complete and approximable within 3.5 based on the min-max theorem.

AB - We establish a necessary and sufficient condition for the linear system {x : Hx ≥ e, x ≥ 0} associated with a bipartite tournament to be totally dual integral, where H is the cycle-vertex incidence matrix and e is the all-one vector. The consequence is a min-max relation on packing and covering cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem on the corresponding bipartite tournaments. In addition, we show that the feedbank vertex set problem on general bipartite tournaments is NP-complete and approximable within 3.5 based on the min-max theorem.

KW - Approximation algorithm

KW - Bipartite tournament

KW - Feedback vertex set

KW - Min-max relation

KW - Totally dual integrality

UR - https://www.scopus.com/pages/publications/0036577366

UR - https://www.scopus.com/pages/publications/0036577366#tab=impact

U2 - 10.1287/moor.27.2.361.328

DO - 10.1287/moor.27.2.361.328

M3 - RGC 21 - Publication in refereed journal

SN - 0364-765X

VL - 27

SP - 361

EP - 371

JO - Mathematics of Operations Research

JF - Mathematics of Operations Research

IS - 2

ER -

A min-max theorem on feedback vertex sets

Abstract

Bibliographical note

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this