## 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.