Min-max theorems on feedback vertex sets

by Li, Yin-chiu

Abstract (Summary)
(Uncorrected OCR) Abstract of thesis entitled


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.

Bibliographical Information:


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

© 2009 All Rights Reserved.