Search

In this paper we study a maximization version of the classical Feedback Vertex Set (FVS) problem, namely, the Max Min FVS problem, in the realm of parameterized complexity. In this problem, given an undirected graph $G$, a positive integer $k$, the question is to check whether $G$ has a minimal feedback vertex set of size at least $k$. We obtain following results for Max Min FVS. 1) We first design a fixed parameter tractable (FPT) algorithm for Max Min FVS running in time $10^kn^{\mathcal{O}(1)}$. 2) Next, we consider the problem parameterized by the vertex cover number of the input graph (denoted by $\mathsf{vc}(G)$), and design an algorithm with running time $2^{\mathcal{O}(\mathsf{vc}(G)\log \mathsf{vc}(G))}n^{\mathcal{O}(1)}$. We complement this result by showing that the problem parameterized by $\mathsf{vc}(G)$ does not admit a polynomial compression unless coNP $\subseteq$ NP/poly. 3) Finally, we give an FPT-approximation scheme (fpt-AS) parameterized by $\mathsf{vc}(G)$. That is, we design an algorithm that for every $\epsilon >0$, runs in time $2^{\mathcal{O}\left(\frac{\mathsf{vc}(G)}{\epsilon}\right)} n^{\mathcal{O}(1)}$ and returns a minimal feedback vertex set of size at least $(1-\epsilon){\sf opt}$.

A set $S$ of vertices of a graph is a defensive alliance if, for each element of $S$, the majority of its neighbours is in $S$. We consider the notion of local minimality in this paper. We are interested in locally minimal defensive alliance of maximum size. We also look at connected version of defensive alliance. This problem is known to be NP-hard but its parameterized complexity remains open until now. We enhance our understanding of the problem from the viewpoint of parameterized complexity. The main results of the paper are the following: (1) Locally Minimal Defensive Alliance is NP-complete, even when restricted to planar graphs, (2) a randomized FPT algorithm for Exact Connected Locally Minimal Defensive Alliance parameterized by solution size, (3) Locally Minimal Defensive Alliance is fixed-parameter tractable (FPT) when parametrized by neighbourhood diversity, (4) Locally Minimal Defensive Alliance parameterized by treewidth is W[1]-hard and thus not FPT (unless FPT=W[1]), (5) Locally Minimal Defensive Alliance can be solved in polynomial time for graphs of bounded treewidth.

The Satisfactory Partition problem consists in deciding if the set of vertices of a given undirected graph can be partitioned into two nonempty parts such that each vertex has at least as many neighbours in its part as in the other part. This problem was introduced by Gerber and Kobler [European J. Oper. Res. 125 (2000) 283-291] and further studied by other authors, but its parameterized complexity remains open until now. It is known that the Satisfactory Partition problem, as well as a variant where the parts are required to be of the same cardinality, are NP-complete. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is FPT when parameterized by the neighbourhood diversity of the input graph, (2) it can be solved in $O(n^{8 {\tt cw}})$ where ${\tt cw}$ is the clique-width,(3) a generalized version of the problem is W[1]-hard when parameterized by the treewidth., Comment: 1-15 pages, 2 figures