Minimum Hitting Sets and Beyond
Grant Data
Project Title
Minimum Hitting Sets and Beyond
Principal Investigator
Professor Zang, Wenan
(Principal Investigator (PI))
Duration
36
Start Date
2016-01-01
Amount
449964
Conference Title
Minimum Hitting Sets and Beyond
Presentation Title
Keywords
algorithm, hitting set, integral polyhedron, min-max relation
Discipline
Applied Mathematics
Panel
Physical Sciences (P)
HKU Project Code
17301215
Grant Type
General Research Fund (GRF)
Funding Year
2015
Status
Completed
Objectives
1 To characterize all tournaments T=(V, A) such that the maximum size of a cycle packing is equal to the minimum total weight of a feedback arc set in T for any nonnegative integral weight function defined on A; 2 To characterize all tournaments T=(V, A) such that the maximum size of a feedback arc set packing is equal to the minimum total weight of a cycle in T for any nonnegative integral weight function defined on A; 3 To show that the minimum total weight of a feedback vertex set of a planar digraph G=(V, A) is at most five times the maximum size of a cycle packing for any nonnegative integral weight function defined on V; and 4 To characterize all graphs G=(V, E) such that the maximum size of an odd cycle packing is equal to the minimum total weight of an odd cycle cover in G for any nonnegative integral weight function defined on V.