Independent Feedback Vertex Set, Acyclic Vertex Cover e Connected Near-Bipartiteness em Grafos Bipartidos

O problema da Quase-Bipartição é amplamente estudado na teoria dos grafos e consiste em determinar se o conjunto de vértices de um grafo pode ser particionado em um conjunto independente e uma floresta. Neste trabalho, investigamos três variantes desse problema na classe dos grafos bipartidos: Connected Near-Bipartiteness, Independent Feedback Vertex Set e Acyclic Vertex Cover. Embora grafos bipartidos apresentem uma estrutura restrita, mostramos que essa limitação não implica tratabilidade. Por meio de reduções polinomiais a partir de variações de problemas de satisfabilidade booleana, provamos que Connected Near-Bipartiteness permanece NP-completo mesmo nessa classe. Além disso, demonstramos que os problemas Independent Feedback Vertex Set e Acyclic Vertex Cover, que correspondem à minimização de |S| e |F|, respectivamente, são NP-difíceis em grafos bipartidos. Esses resultados contribuem para a compreensão dos limites de complexidade dessas variantes em classes estruturadas de grafos.