Max-SAT with cardinality constraint ( CC-Max-Sat ) is one of the classical NP-complete problems, that generalizes Maximum Coverage , Partial Vertex Cover , Max-2-SAT with bisection constraints, and has been extensively studied across all algorithmic paradigms. In this problem, we are given a CNF formula \(\Phi\) , and a positive integer \( k \) , and the goal is to find an assignment \(\beta\) with at most \( k \) variables set to true (also called a \( k \) -weight assignment) such that the number of clauses satisfied by \(\beta\) is maximized. The problem is known to admit an approximation algorithm with factor \(1-\frac{1}{e}\) , which is probably optimal. Furthermore, assuming Gap-Exponential Time Hypothesis (Gap-ETH), for any \(\epsilon > 0\) and any function \( h \) , no \(h(k)(n+m)^{o(k)}\) time algorithm can approximate Maximum Coverage (a monotone version of CC-Max-Sat ) with \( n \) elements and \( m \) sets to within a factor \((1-\frac{1}{e}+\epsilon)\) , even with a promise that there exist \( k \) sets that fully cover the whole universe. In fact, the problem is hard to approximate within 0.929, assuming Unique Games Conjecture, even when the input formula is 2-CNF. These intractable results lead us to explore families of formula, where we can circumvent these barriers. Toward this, we consider \(K_{d,d}\) -free formulas (that is, the clause-variable incidence bipartite graph of the formula excludes \(K_{d,d}\) as an induced subgraph). We show that for every \(\epsilon > 0\) , there exists an algorithm for CC-Max-Sat on \(K_{d,d}\) -free formulas with approximation ratio \((1-\epsilon)\) and running in time \(2^{{\mathcal{O}}((\frac{dk}{\epsilon})^{d})}(n+m)^{{\mathcal{O}}(1)}\) (these algorithms are called FPT-AS). For Maximum Coverage on \(K_{d,d}\) -free set families, we obtain FPT-AS with running time \((\frac{dk}{\epsilon})^{{\mathcal{O}}(dk)}n^{{\mathcal{O}}(1)}\) . Our second result considers “optimizing \( k \) ,” with fixed covering constraint for the Maximum Coverage problem. To explain our result, we first recast the Maximum Coverage problem as the Max Red Blue Dominating Set with Covering Constraint problem. Here, the input is a bipartite graph \(G=(A,B,E)\) , a positive integer \( t \) , and the objective is to find a minimum sized subset \(S\subseteq A\) , such that \(|N(S)|\) (the size of the set of neighbors of \( S \) ) is at least \( t \) . We design an additive approximation algorithm for Max Red Blue Dominating Set with Covering Constraint , on \(K_{d,d}\) -free bipartite graphs, running in FPT time. In particular, if

Majority illusion occurs in a social network when the majority of the network vertices belong to a certain type but the majority of each vertex's neighbours belong to a different type, therefore creating the wrong perception, i.e., the illusion, that the majority type is different from the actual one. From a system engineering point of view, this motivates the search for algorithms to detect and, where possible, correct this often undesirable phenomenon. In this we provide a computational study of majority illusion in social networks, paying particular attention to the problem of its verification, i.e., whether majority illusion can occur on social networks, and elimination, i.e., how can we eliminate majority illusion by social network rewiring. While we show that the problems we consider are generally NP-complete, we also provide a parameterised complexity analysis, showing FPT-algorithms for the detection problem and W[1]-hardness for the elimination problem, using natural graph-theoretic parameters.

Abstract In this paper, we introduce a directed variant of the classical Bandwidthproblem and study it from the view-point of moderately exponential time algorithms, both exactly and approximately. Motivated by the definitions of the directed variants of the classical Cutwidth and Pathwidth problems, we define Digraph Bandwidth as follows. Given a digraph $$\varvec{D}$$ D and an ordering $$\varvec{\sigma }$$ σ of its vertices, the digraph bandwidth of $$\varvec{\sigma }$$ σ with respect to $$\varvec{D}$$ D is equal to the maximum value of $$\varvec{\sigma (v)}-\varvec{\sigma (u)}$$ σ ( v ) - σ ( u ) over all arcs $$\varvec{(u,v)}$$ ( u , v ) of $$\varvec{D}$$ D going forward along $$\varvec{\sigma }$$ σ (that is, when $$\varvec{\sigma (u)} < \varvec{\sigma (v)}$$ σ ( u ) < σ ( v ) ). The Digraph Bandwidth problem takes as input a digraph $$\varvec{D}$$ D and asks to output an ordering with the minimum digraph bandwidth. The undirected Bandwidtheasily reduces to Digraph Bandwidth and thus, it immediately implies that Digraph Bandwidth is -hard. While an $$\varvec{\mathcal {O}}^{\star }\varvec{(n!)}$$ O ⋆ ( n ! ) time algorithm for the problem is trivial, the goal of this paper is to design algorithms for Digraph Bandwidth which have running times of the form $$\varvec{2}^{\varvec{\mathcal {O}(n)}}$$ 2 O ( n ) . In particular, we obtain the following results. Here, $$\varvec{n}$$ n and $$\varvec{m}$$ m denote the number of vertices and arcs of the input digraph $$\varvec{D}$$ D , respectively. Digraph Bandwidth can be solved in $$\varvec{\mathcal {O}}^\star (\varvec{3}^{\varvec{n}} \cdot \varvec{2}^{\varvec{m}})$$ O ⋆ ( 3

Majority illusion occurs in a social network when the majority of the network vertices belong to a certain type but the majority of each vertex's neighbours belong to a different type, therefore creating the wrong perception, i.e., the illusion, that the majority type is different from the actual one. From a system engineering point of view, this motivates the search for algorithms to detect and, where possible, correct this undesirable phenomenon. In this paper we initiate the computational study of majority illusion in social networks, providing NP-hardness and parametrised complexity results for its occurrence and elimination.

For numerous graph problems in the realm of parameterized algorithms, using the size of a smallest deletion set (called a modulator) into well-understood graph families as parameterization has led to a long and successful line of research. Recently, however, there has been an extensive study of structural parameters that are potentially much smaller than the modulator size. In particular, recent papers [Jansen et al. STOC 2021; Agrawal et al. SODA 2022] have studied parameterization by the size of the modulator to a graph family $\mathcal{H}$ ($\textbf{mod}_{\mathcal{H}}$), elimination distance to $\mathcal{H}$ ($\textbf{ed}_{\mathcal{H}}$), and $\mathcal{H}$-treewidth ($\textbf{tw}_{\mathcal{H}}$). While these new parameters have been successfully exploited to design fast exact algorithms their utility (especially that of latter two) in the context of approximation algorithms is mostly unexplored. The conceptual contribution of this paper is to present novel algorithmic meta-theorems that expand the impact of these structural parameters to the area of FPT Approximation, mirroring their utility in the design of exact FPT algorithms. Precisely, we show that if a covering or packing problem is definable in Monadic Second Order Logic and has a property called Finite Integer Index, then the existence of an FPT Approximation Scheme (FPT-AS, i.e., ($1\pm ε$)-approximation) parameterized these three parameters is in fact equivalent. As concrete exemplifications of our meta-theorems, we obtain FPT-ASes for well-studied graph problems such as Vertex Cover, Feedback Vertex Set, Cycle Packing and Dominating Set, parameterized by these three parameters.

Selection of a group of representatives satisfying certain fairness constraints, is a commonly occurring scenario. Motivated by this, we initiate a systematic algorithmic study of a \emph{fair} version of \textsc{Hitting Set}. In the classical \textsc{Hitting Set} problem, the input is a universe $\mathcal{U}$, a family $\mathcal{F}$ of subsets of $\mathcal{U}$, and a non-negative integer $k$. The goal is to determine whether there exists a subset $S \subseteq \mathcal{U}$ of size $k$ that \emph{hits} (i.e., intersects) every set in $\mathcal{F}$. Inspired by several recent works, we formulate a fair version of this problem, as follows. The input additionally contains a family $\mathcal{B}$ of subsets of $\mathcal{U}$, where each subset in $\mathcal{B}$ can be thought of as the group of elements of the same \emph{type}. We want to find a set $S \subseteq \mathcal{U}$ of size $k$ that (i) hits all sets of $\mathcal{F}$, and (ii) does not contain \emph{too many} elements of each type. We call this problem \textsc{Fair Hitting Set}, and chart out its tractability boundary from both classical as well as multivariate perspective. Our results use a multitude of techniques from parameterized complexity including classical to advanced tools, such as, methods of representative sets for matroids, FO model checking, and a generalization of best known kernels for \textsc{Hitting Set}.

MAX-SAT with cardinality constraint (CC-MAX-SAT) is one of the classical NP-complete problems, that generalizes MAXIMUM COVERAGE, PARTIAL VERTEX COYER, MAX-2-SAT with bisection constraints, and has been extensively studied across all algorithmic paradigms. In this problem, we are given a CNF-formula Φ, and a positive integer k, and the goal is to find an assignment β with at most k variables set to true (also called a weight k-assignment) such that the number of clauses satisfied by β is maximized. The problem is known to admit an approximation algorithm with factor , which is probably optimal. In fact, the problem is hard to approximate within 0.944, assuming Unique Games Conjecture, even when the input formula is 2-CNF. Furthermore, assuming Gap-Exponential Time Hypothesis (Gap-ETH), for any ε > 0 and any function h, no h(k)(n + m)o(k) time algorithm can approximate MAXIMUM COVERAGE (a monotone version of CC-MAX-SAT) with n elements and m sets to within a factor , even with a promise that there exist k sets that fully cover the whole universe. These intractable results lead us to explore families of formula, where we can circumvent these barriers. Towards this we consider Kd,d-free formulas (that is, the clause-variable incidence bipartite graph of the formula excludes Kd,d as an induced subgraph). We show that for every ε > 0, there exists an algorithm for CC-MAX-SAT on Kd,d-free formulas with approximation ratio (1 — ε) and running in time (these algorithms are called FPT-AS). For, MAXIMUM COVERAGE on Kd,d-free set families, we obtain FPT-AS with running time . Our second result considers “optimizing k”, with fixed covering constraint for the Maximum Coverage problem. To explain our result, we first recast the MAXIMUM COVERAGE problem as the MAX RED BLUE DOMINATING SET WITH COVERING CONSTRAINT problem. Here, input is a bipartite graph G = (A, B, E), a positive integer t, and the objective is to find a minimum sized subset S ⊆ A, such that |N(S)| (the size of the set of neighbors of S) is at least t. We design an additive approximation algorithm for MAX RED BLUE DOMINATING SET WITH COVERING CONSTRAINT, on Kd,d-free bipartite graphs, running in FPT time. In particular, if k denotes the minimum size of S ⊆ A, such that |N(S)| ≥ t, then our algorithm runs in time (kd)O(kd)nO(1) and returns a set S' such that |N(S')| ≥ t and |S'| ≤ k +1. This is in sharp contrast to the fact that, even a special case of our problem, namely, the PARTIAL VERTEX COVER problem (or MAX k-VC) is W[1]-hard, parameterized by k. Thus, we get the best possible parameterized approximation algorithm for the MAXIMUM COVERAGE problem on Kd,d-free bipartite graphs. * Pallavi Jain is supported by Seed Grant (IITJ/R&D/2022-23/07) and SERB-SUPRA Grant(SPR/2021/000860). Lawqueen Kanesh is supported by EPSRC Standard Research Grant (EP/V044621/1). Saket Saurabh is supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 819416); and he also acknowledges the support of Swarnajayanti Fellowship grant DST/SJF/MSA-01/2017-18.

Abstract. For a positive integer [Formula: see text], a graph [Formula: see text] is said to be [Formula: see text]-closed if every pair of nonadjacent vertices in [Formula: see text] have at most [Formula: see text] neighbors in common. The closure of a graph [Formula: see text], denoted by [Formula: see text], is the least positive integer [Formula: see text] for which [Formula: see text] is [Formula: see text]-closed. The class of [Formula: see text]-closed graphs was introduced by J. Fox, T. Roughgarden, C. Seshadhri, F. Wei, and N. Wein [Proceedings of the International Colloquium on Automata, Languages, and Programming (2018), 55; SIAM J. Comput., 49 (2020), pp. 448–464]. T. Koana, C. Komusiewicz, and F. Sommer [Proceedings of the European Symposium on Algorithms (2020), 65; SIAM J. Discrete Math., 36 (2022), pp. 2798–2821] started the study of using [Formula: see text] as an additional structural parameter to design kernels for problems that are W -hard under standard parameterizations. In particular, they studied problems such as Independent Set, Induced Matching, Irredundant Set, and (Threshold) Dominating Set and showed that each of these problems admits a polynomial kernel when parameterized either by [Formula: see text] or by [Formula: see text] for each fixed value of [Formula: see text]. Here, [Formula: see text] is the solution size and [Formula: see text]. The work of Koana et al. left several questions open, one of which was whether the Perfect Code problem admits a fixed-parameter tractable ( FPT ) algorithm and a polynomial kernel on [Formula: see text]-closed graphs. In this paper, among other results, we answer this question in the affirmative. Inspired by the FPT algorithm for Perfect Code, we further explore two more domination problems on the graphs of bounded closure. The other problems that we study are Connected Dominating Set and Partial Dominating Set. We show that Perfect Code and Connected Dominating Set are fixed-parameter tractable when parameterized by [Formula: see text], whereas Partial Dominating Set, parameterized by [Formula: see text] is [Formula: see text]-hard even when [Formula: see text]. We also show that for each fixed [Formula: see text], Perfect Code admits a polynomial kernel on the class of [Formula: see text]-closed graphs. And we observe that Connected Dominating Set has no polynomial kernel even on 2-closed graphs unless NP [Formula: see text] co- NP /poly.

Vertex-deletion problems have been at the heart of parameterized complexity throughout its history. Here, the aim is to determine the minimum size (denoted by modℋ) of a modulator to a graph class ℋ, i.e., a set of vertices whose deletion results in a graph in ℋ. Recent years have seen the development of a research programme where the complexity of modulators is measured in ways other than size. For instance, for a graph class ℋ, the graph parameters elimination distance to ℋ (denoted by edℋ) [Bulian and Dawar, Algorithmica, 2016] and ℋ-treewidth (denoted by twℋ) [Eiben et al. JCSS, 2021] aim to minimize the treedepth and treewidth, respectively, of the “torso” of the graph induced on a modulator to the graph class ℋ. Here, the torso of a vertex set S in a graph G is the graph with vertex set S and an edge between two vertices u, v ∊ S if there is a path between u and v in G whose internal vertices all lie outside S. In this paper, we show that from the perspective of (non-uniform) fixed-parameter tractability (FPT), the three parameters described above give equally powerful parameterizations for every hereditary graph class ℋ that satisfies mild additional conditions. In fact, we show that for every hereditary graph class ℋ satisfying mild additional conditions, with the exception of edℋ parameterized by twℋ, for every pair of these parameters, computing one parameterized by itself or any of the others is FPT-equivalent to the standard vertex-deletion (to ℋ) problem. As an example, we prove that an FPT algorithm for the vertex-deletion problem implies a non-uniform FPT algorithm for computing edℋ and twℋ. The conclusions of non-uniform FPT algorithms being somewhat unsatisfactory, we essentially prove that if ℋ is hereditary, union-closed, CMSO-definable, and (a) the canonical equivalence relation (or any refinement thereof) for membership in the class can be efficiently computed, or (b) the class admits a “strong irrelevant vertex rule”, then there exists a uniform FPT algorithm for edℋ. Using these sufficient conditions, we obtain uniform FPT algorithms for computing edℋ, when ℋ is defined by excluding a finite number of connected (a) minors, or (b) topological minors, or (c) induced subgraphs, or when ℋ is any of bipartite, chordal or interval graphs. For most of these problems, the existence of a uniform FPT algorithm has remained open in the literature. In fact, for some of them, even a non-uniform FPT algorithm was not known. For example, Jansen et al. [STOC 2021] ask for such an algorithm when ℋ is defined by excluding a finite number of connected topological minors. We resolve their question in the affirmative.

Finding large cliques or cliques missing a few edges is a fundamental algorithmic task in the study of real-world graphs, with applications in community detection, pattern recognition, and clustering. A number of effective backtracking-based heuristics for these problems have emerged from recent empirical work in social network analysis. Given the NP-hardness of variants of clique counting, these results raise a challenge for beyond worst-case analysis of these problems. Inspired by the triadic closure of real-world graphs, Fox et al. (SICOMP 2020) introduced the notion of $c$-closed graphs and proved that maximal clique enumeration is fixed-parameter tractable with respect to $c$. In practice, due to noise in data, one wishes to actually discover "near-cliques", which can be characterized as cliques with a sparse subgraph removed. In this work, we prove that many different kinds of maximal near-cliques can be enumerated in polynomial time (and FPT in $c$) for $c$-closed graphs. We study various established notions of such substructures, including $k$-plexes, complements of bounded-degeneracy and bounded-treewidth graphs. Interestingly, our algorithms follow relatively simple backtracking procedures, analogous to what is done in practice. Our results underscore the significance of the $c$-closed graph class for theoretical understanding of social network analysis.

In the literature on parameterized graph problems, there has been an increased effort in recent years aimed at exploring novel notions of graph edit-distance that are more powerful than the size of a modulator to a specific graph class. In this line of research, Bulian and Dawar [ Algorithmica, 75 (2016), pp. 363--382] introduced the notion of elimination distance and showed that deciding whether a given graph has elimination distance at most $k$ to any minor-closed class of graphs is fixed-parameter tractable parameterized by $k$ [ Algorithmica, 79 (2017), pp. 139--158]. They showed that graph isomorphism parameterized by the elimination distance to bounded degree graphs is fixed-parameter tractable and asked whether determining the elimination distance to the class of bounded degree graphs is fixed-parameter tractable. Recently, Lindermayr, Siebertz, and Vigny [MFCS 2020, LIPIcs Leibniz Int. Proc. Inform. 170, Wadern Germany, 2020, 65] obtained a fixed-parameter algorithm for this problem in the special case where the input is restricted to $K_5$-minor free graphs. In this paper, we answer the question of Bulian and Dawar in the affirmative for general graphs. In fact, we give a more general result capturing elimination distance to any graph class characterized by a finite set of graphs as forbidden induced subgraphs.

In the literature on parameterized graph problems, there has been an increased effort in recent years aimed at exploring novel notions of graph edit-distance that are more powerful than the size of a modulator to a specific graph class. In this line of research, Bulian and Dawar [Algorithmica, 2016] introduced the notion of elimination distance and showed that deciding whether a given graph has elimination distance at most k to any minor-closed class of graphs is fixed-parameter tractable parameterized by k [Algorithmica, 2017]. They showed that Graph Isomorphism parameterized by the elimination distance to bounded degree graphs is fixed-parameter tractable and asked whether determining the elimination distance to the class of bounded degree graphs is fixed-parameter tractable. Recently, Lindermayr et al. [MFCS 2020] obtained a fixed-parameter algorithm for this problem in the special case where the input is restricted to K₅-minor free graphs. In this paper, we answer the question of Bulian and Dawar in the affirmative for general graphs. In fact, we give a more general result capturing elimination distance to any graph class characterized by a finite set of graphs as forbidden induced subgraphs.

A feedback vertex set in a hypergraph H is a set of vertices S such that deleting S from H results in an acyclic hypergraph. Here, deleting a vertex means removing the vertex and all incident hyperedges, and a hypergraph is acyclic if its vertex-edge incidence graph is acyclic. We study the (parameterized complexity of) the Hypergraph Feedback Vertex Set (HFVS) problem: given as input a hypergraph H and an integer k, determine whether H has a feedback vertex set of size at most k. It is easy to see that this problem generalizes the classic Feedback Vertex Set (FVS) problem on graphs. Remarkably, despite the central role of FVS in parameterized algorithms and complexity, the parameterized complexity of a generalization of FVS to hypergraphs has not been studied previously. In this paper, we fill this void. Our main results are as follows - HFVS is W[2]-hard (as opposed to FVS, which is fixed parameter tractable). - If the input hypergraph is restricted to a linear hypergraph (no two hyperedges intersect in more than one vertex), HFVS admits a randomized algorithm with running time 2^{𝒪(k³log k)}n^{𝒪(1)}. - If the input hypergraph is restricted to a d-hypergraph (hyperedges have cardinality at most d), then HFVS admits a deterministic algorithm with running time d^{𝒪(k)}n^{𝒪(1)}. The algorithm for linear hypergraphs combines ideas from the randomized algorithm for FVS by Becker et al. [J. Artif. Intell. Res., 2000] with the branching algorithm for Point Line Cover by Langerman and Morin [Discrete & Computational Geometry, 2005].

An input to a conflict-free variant of a classical problem $$\Gamma $$ , called Conflict-Free $$\Gamma $$ , consists of an instance I of $$\Gamma $$ coupled with a graph H, called the conflict graph. A solution to Conflict-Free $$\Gamma $$ in (I, H) is a solution to I in $$\Gamma $$ , which is also an independent set in H. In this paper, we study conflict-free variants of Maximum Matching and Shortest Path, which we call Conflict-Free Maximum Matching (CF-MM) and Conflict-Free Shortest Path (CF-SP), respectively. We show that both CF-MM and CF-SP are W[1]-hard, when parameterized by the solution size. Moreover, W[1]-hardness for CF-MM holds even when the input graph where we want to find a matching is itself a matching, and W[1]-hardness for CF-SP holds for conflict graph being a unit-interval graph. Next, we study these problems with restriction on the conflict graphs. We give FPT algorithms for CF-MM when the conflict graph is chordal. Also, we give FPT algorithms for both CF-MM and CF-SP, when the conflict graph is d-degenerate. Finally, we design FPT algorithms for variants of CF-MM and CF-SP, where the conflicting conditions are given by a (representable) matroid.

In this paper, we introduce a directed variant of the classical Bandwidth problem and study it from the view-point of moderately exponential time algorithms, both exactly and approximately. Motivated by the definitions of the directed variants of the classical Cutwidth and Pathwidth problems, we define Digraph Bandwidth as follows. Given a digraph D and an ordering sigma of its vertices, the digraph bandwidth of sigma with respect to D is equal to the maximum value of sigma(v)-sigma(u) over all arcs (u,v) of D going forward along sigma (that is, when sigma(u) < sigma (v)). The Digraph Bandwidth problem takes as input a digraph D and asks to output an ordering with the minimum digraph bandwidth. The undirected Bandwidth easily reduces to Digraph Bandwidth and thus, it immediately implies that Directed Bandwidth is {NP-hard}. While an O^*(n!) time algorithm for the problem is trivial, the goal of this paper is to design algorithms for Digraph Bandwidth which have running times of the form 2^O(n). In particular, we obtain the following results. Here, n and m denote the number of vertices and arcs of the input digraph D, respectively. - Digraph Bandwidth can be solved in O^*(3^n * 2^m) time. This result implies a 2^O(n) time algorithm on sparse graphs, such as graphs of bounded average degree. - Let G be the underlying undirected graph of the input digraph. If the treewidth of G is at most t, then Digraph Bandwidth can be solved in time O^*(2^(n + (t+2) log n)). This result implies a 2^(n+O(sqrt(n) log n)) algorithm for directed planar graphs and, in general, for the class of digraphs whose underlying undirected graph excludes some fixed graph H as a minor. - Digraph Bandwidth can be solved in min{O^*(4^n * b^n), O^*(4^n * 2^(b log b log n))} time, where b denotes the optimal digraph bandwidth of D. This allow us to deduce a 2^O(n) algorithm in many cases, for example when b <= n/(log^2n). - Finally, we give a (Single) Exponential Time Approximation Scheme for Digraph Bandwidth. In particular, we show that for any fixed real epsilon > 0, we can find an ordering whose digraph bandwidth is at most (1+epsilon) times the optimal digraph bandwidth, in time O^*(4^n * (ceil[4/epsilon])^n).

A generalization of classical cycle hitting problems, called conflict version of the problem, is defined as follows. An input is undirected graphs G and H on the same vertex set, and a positive integer k, and the objective is to decide whether there exists a vertex subset X subseteq V(G) such that it intersects all desired "cycles" (all cycles or all odd cycles or all even cycles) and X is an independent set in H. In this paper we study the conflict version of classical Feedback Vertex Set, and Odd Cycle Transversal problems, from the view point of kernelization complexity. In particular, we obtain the following results, when the conflict graph H belongs to the family of d-degenerate graphs. 1) CF-FVS admits a O(k^{O(d)}) kernel. 2) CF-OCT does not admit polynomial kernel (even when H is 1-degenerate), unless NP subseteq coNP/poly. For our kernelization algorithm we exploit ideas developed for designing polynomial kernels for the classical Feedback Vertex Set problem, as well as, devise new reduction rules that exploit degeneracy crucially. Our main conceptual contribution here is the notion of "k-independence preserver". Informally, it is a set of "important" vertices for a given subset X subseteq V(H), that is enough to capture the independent set property in H. We show that for d-degenerate graph independence preserver of size k^{O(d)} exists, and can be used in designing polynomial kernel.

In this paper we study recently introduced conflict version of the classical Feedback Vertex Set (FVS) problem. For a family of graphs F, we consider the problem F-CF-Feedback Vertex Set (F-CF-FVS, for short). The F-CF-FVS problem takes as an input a graph G, a graph H in F (where V(G)=V(H)), and an integer k, and the objective is to decide if there is a set S subseteq V(G) of size at most k such that G-S is a forest and S is an independent set in H. Observe that if we instantiate F to be the family of edgeless graphs then we get the classical FVS problem. Jain, Kanesh, and Misra [CSR 2018] showed that in contrast to FVS, F-CF-FVS is W[1]-hard on general graphs and admits an FPT algorithm if F is the family of d-degenerate graphs. In this paper, we relate F-CF-FVS to the Independent Set problem on special classes of graphs, and obtain a complete dichotomy result on the Parameterized Complexity of the problem F-CF-FVS, when F is a hereditary graph family. In particular, we show that F-CF-FVS is FPT parameterized by the solution size if and only if F+Cluster IS is FPT parameterized by the solution size. Here, F+Cluster IS is the Independent Set problem in the (edge) union of a graph G in F and a cluster graph H (G and H are explicitly given). Next, we exploit this characterization to obtain new FPT results as well as intractability results for F-CF-FVS. In particular, we give an FPT algorithm for F+Cluster IS when F is the family of K_{i,j}-free graphs. We show that for the family of bipartite graph B, B-CF-FVS is W[1]-hard, when parameterized by the solution size. Finally, we consider, for each 0< epsilon<1, the family of graphs F_epsilon, which comprise of graphs G such that |E(G)| <= |V(G)|^(2-epsilon), and show that F_epsilon-CF-FVS is W[1]-hard, when parameterized by the solution size, for every 0<epsilon<1.