Min-max theorems on feedback vertex sets
MIN-MAX THEOREMS ON FEEDBACK VERTEX SETS
submitted by LI, Yin Chiu
for the degree of Master of Philosophy at The University of Hong Kong
in October 2002
Given a directed (resp. undirected) graph G = (V, E) with weight w(u) on each u E 1", a vertex-subset of G is called a feedback ver-tex set (FVS) if it intersects every directed (resp. undirected) cycle in G. The problem of finding a feedback vertex set with the minimum total weight is called the feedback vcr-te:r: set pTObleTn. which has a rich variety of applications and has been studied extensively Since this problem is N P-hard, there is no efficient algorithm for optimally solving it in general unless N P = P. The present thesis is devoted to the feedback vertex set problem on some special classes of graphs, and is motiv~lted by the duality theory of mathematical programmmg.
To be specific, a collection C of cycles (repetition is allowed) of G is called a cycle packiTLg if each vertex u of G is used at most w (v) times by members of C. The cycle pack'lng pr-oblem aims to find a cvcle packing with the maximum size. Clearlv. this problem and the above feedback vertex set problem form a prirnal-dual pair. Let Tw(G) denote the minimum total weight of a feedback set in G, and let l/",(G) denote the maximum size of a cycle packing. It is clear that
vw(G) ::; TW(G).
However. the equality may not hold in general. In fact. the ratio of Tw(G) (rver l/w(G) can be arbitrarily large even when w(u) = 1 for all vertices u E L as shown by Enl()s and P6sa. Graph G is called cycle Mengenan (CM) if vw(G) = Tw(G) for all non-negative integral w. According to a powerful theorem of Grotschel, Lov;-ls2, and Schrijver, the feedback set problem on CM graphs can be solved in polynomial time. So it is interesting to give a structural description of eM graphs.
In this thesis. a characterization of CM tournaments is presented, followed bv a combinatorial polynomial time algorithm for the feedback vertex set problem on these directed graphs. In addition, CYI undirected graphs are fully characterized in terms of forbidden structures; the proof is constructive and yields a polynomial-time algorithm for recognizing all these undirected graphs.
School:The University of Hong Kong
School Location:China - Hong Kong SAR
Source Type:Master's Thesis
Keywords:maxima and minima graph theory
Date of Publication:01/01/2003