Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science

Profile

Publication details for Professor Matthew Johnson

Bonamy, M., Dabrowski, K.K., Feghali, C., Johnson, M. & Paulusma, D. (2019). Independent Feedback Vertex Set for P5-free Graphs. Algorithmica 81(4): 1342-1369.

Author(s) from Durham

Abstract

The NP-complete problem Feedback Vertex Set is that of deciding whether or not it is possible, for a given integer k≥0 , to delete at most k vertices from a given graph so that what remains is a forest. The variant in which the deleted vertices must form an independent set is called Independent Feedback Vertex Set and is also NP-complete. In fact, even deciding if an independent feedback vertex set exists is NP-complete and this problem is closely related to the 3-Colouring problem, or equivalently, to the problem of deciding whether or not a graph has an independent odd cycle transversal, that is, an independent set of vertices whose deletion makes the graph bipartite. We initiate a systematic study of the complexity of Independent Feedback Vertex Set for H-free graphs. We prove that it is NP-complete if H contains a claw or cycle. Tamura, Ito and Zhou proved that it is polynomial-time solvable for P4 -free graphs. We show that it remains polynomial-time solvable for P5 -free graphs. We prove analogous results for the Independent Odd Cycle Transversal problem, which asks whether or not a graph has an independent odd cycle transversal of size at most k for a given integer k≥0 . Finally, in line with our underlying research aim, we compare the complexity of Independent Feedback Vertex Set for H-free graphs with the complexity of 3-Colouring, Independent Odd Cycle Transversal and other related problems.