---
abstract: 'The [Near-Bipartiteness]{} problem is that of deciding whether or not the vertices of a graph can be partitioned into sets $A$ and $B$, where $A$ is an independent set and $B$ induces a forest. The set $A$ in such a partition is said to be an independent feedback vertex set. Yang and Yuan proved that [Near-Bipartiteness]{} is polynomial-time solvable for graphs of diameter $2$ and [[NP]{}]{}-complete for graphs of diameter $4$. We show that [Near-Bipartiteness]{} is [[NP]{}]{}-complete for graphs of diameter $3$, resolving their open problem. We also generalise their result for diameter $2$ by proving that even the problem of computing a minimum independent feedback vertex is polynomial-time solvable for graphs of diameter $2$.'
author:
- Marthe Bonamy
- 'Konrad K. Dabrowski'
- Carl Feghali
- |
    \
    Matthew Johnson
- Daniël Paulusma
bibliography:
- 'mybib.bib'
title: |
    Independent Feedback Vertex Sets for\
    Graphs of Bounded Diameter[^1]
---

Introduction
============

A graph is [*near-bipartite*]{} if its vertex set can be partitioned into sets $A$ and $B$, where $A$ is an independent set and $B$ induces a forest. The set $A$ is said to be an [*independent feedback vertex set*]{} and the pair $(A,B)$ is said to be 