UTCS Colloquium/ACT Seminar: Jianer Chen Texas A&M University An O(n%5E4) Time Algorithm for Bounded Feedback Vertex Set ACES 3.408 Friday November 30 2007 10:00 a.m.

Contact Name: 
Jenna Whitney
Date: 
Nov 30, 2007 10:00am - 10:00pm

Type of Talk: UTCS Colloquium/ACT Seminar

Speaker Name/Affiliation: Jianer Chen/Texas A&M University

Date/Tim

e: Friday November 30 2007 10:00 a.m.

Location: ACES 3.408
Host: Vijaya Ramachandran

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

ullivan and I. Razgon of University College Cork Ireland.