Minimum Hitting Sets and Beyond


Grant Data
Project Title
Minimum Hitting Sets and Beyond
Principal Investigator
Professor Zang, Wenan   (Principal investigator)
Duration
36
Start Date
2016-01-01
Completion Date
2018-12-31
Amount
449964
Conference Title
Presentation Title
Keywords
hitting set, integral polyhedron, min-max relation, algorithm
Discipline
Applied Mathematics
Panel
Physical Sciences (P)
Sponsor
RGC General Research Fund (GRF)
HKU Project Code
17301215
Grant Type
General Research Fund (GRF)
Funding Year
2015/2016
Status
On-going
Objectives
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.