Talk Title: An O(n%5E4) Time Algorithm
for Bounded Feedback Vertex Set

Talk Abstract:
Deadlock problem

is among the most well-known problems studied in
computer science and in

formation management. A system cannot proceed
when a deadlock occurs. Th

us a set of processes in the system needs to be
rolled back in order to
recover from the deadlock. It is desired that only a small
set of proce

sses is rolled back because process rolling back is expensive.
Theoretic

ally the problem is formulated as the Feedback Vertex Set problem
(give

n a directed graph G remove k vertices from G so that the resulting
gra

ph is acyclic where k is expected to be small). The problem is a well-know

n
NP-complete problem. An outstanding open problem (mentioned so in more

than 20 published papers in the literature) is whether there is a polyn

omial
time algorithm for the problem if k is a constant.

In this
talk we resolve this open problem and present an O(n%5E4) time
algori

thm for the Feedback Vertex Set problem for any constant k.

This is
a joint work with Y. Liu and S. Lu of Texas A&M University and B.
O''s