Parameterized Complexity of Fair Feedback Vertex Set Problem

Abstract

Feedback Vertex Set (FVS) problem is a well known NP-complete problem in computational complexity theory. This is a vertex deletion problem in which given a graph G=(V,E) and an integer k, we are asked to find a subset S⊆V(G) with |S|≤k for which the remaining graph G\S is a forest. In this project, we study the fairness property of Feedback Vertex Set problem. Fair Feedback Vertex Set problem (FFVS) is another vertex deletion problem which also demands to find a set S⊆V(G) such that G\S is acyclic, along with an extra condition, that no vertex in the graph should contribute too much to the set S. In order to measure the bound on this condition, we give an integer l, along with the graph G= (V,E) as an input of FFVS problem and we formulate the condition as |N(v)∩S|≤l for all v∈V(G). Here N(v)={u|(u,v)∈E(G)}. The objective here is to equidistribute the solution. This project includes the study of this problem, along with some other variants of this problem, on the realms of parameterized complexity theory. Parameters which we use throughout this project are the structural graph parameters. We show that FFVS is W[1]-hard when parameterized by treewidth and treedepth of the graph. We also prove that it admits an FPT algorithm when parameterized by neighbourhood diversity. Another problem which we study here is Minimum Fair Feedback Vertex Set (Min-FFVS). This is a restriction of FFVS problem with one more condition applied. In Min-FFVS problem, given a graph G=(V,E) and two positive integers k and l, the task is to find S⊆V(G), |S|≤k such that G\S is acyclic and all vertices in the graph fulfill the condition that |N(v)∩S|≤l . For Min-FFVS problem, we first show that it is NP-complete. Then we find a kernel using parameter (∆ +k), where ∆ is the maximum degree of G. Later, we relax one condition and try to find a FFVS which is fair on the remaining graph, that is, |N(v)∩S|≤l for all v∈V(G)\S, if S is the FFVS. This problem, Relaxed Fair Feedback Vertex Set (Relax-FFVS), is tractable if we consider the solution size as a parameter. We obtain an FPT algorithm with respect to solution size for this problem.