## Abstract

A pseudoforest is a graph where each connected component contains at most one cycle, or alternatively, a graph that can be turned into a forest by removing at most one edge from each connected component. In this paper, we show that the following problem can be solved in O(3^{k}nk^{O}(1)) time: given a graph G and an integer k, can we delete at most k vertices from G such that we obtain a pseudoforest? The result improves upon an earlier result by Philip et al. [MFCS 2015] who gave a (nonlinear) 7.56^{k}n^{O(1)}-time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n.

Original language | English |
---|---|

Title of host publication | 11th International Symposium on Parameterized and Exact Computation, IPEC 2016 |

Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |

Number of pages | 12 |

Volume | 63 |

ISBN (Electronic) | 9783959770231 |

DOIs | |

Publication status | Published - 1 Feb 2017 |

Event | 11th International Symposium on Parameterized and Exact Computation, IPEC 2016 - Aarhus, Denmark Duration: 24 Aug 2016 → 26 Aug 2016 Conference number: 11 http://conferences.au.dk/algo16/ipec |

### Publication series

Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|

Volume | 63 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 11th International Symposium on Parameterized and Exact Computation, IPEC 2016 |
---|---|

Abbreviated title | IPEC 2016 |

Country/Territory | Denmark |

City | Aarhus |

Period | 24/08/16 → 26/08/16 |

Internet address |

## Keywords

- Graph class
- Parameterized complexity
- Pseudoforest deletion
- Width parameter