Interval Graph Completion and Polynomial-Time Preprocessing

Date and time: 
Thursday, October 18, 2007 - 15:30
220 Deschutes
Jan Arne Telle
University of Bergen
  • Andrzej Proskurowski


This talk will start by arguing that the complexity class FPT can be used to capture the notion of polynomial-time preprocessing to reduce input size. This is followed by an FPT algorithm with runtime $O(n^{2k}n^{3}m)$ for the following NP-complete problem [GT35 in Garey&Johnson]: Given an arbitrary graph G on n vertices and m edges, can we obtain an interval graph by adding at most k edges to G? The given algorithm answers a question first posed by Kaplan, Shamir and Tarjan in 1994.


Jan Arne Telle is a professor at the University of Bergen and member of its algorithms research group. He earned his doctorate in computer science from the University of Oregon in 1994.