Search

A set S of vertices of a graph is a defensive alliance if, for each element of S , the majority of its neighbours are in S. We study the parameterised complexity of Defensive Alliance , where the aim is to find a minimum size defensive alliance. Our main results are the following: (1) Defensive Alliance has been studied extensively during the last twenty years, but the question whether it is FPT when parameterised by feedback vertex set has still remained open. We prove that the problem is W[1]-hard parameterised by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, treewidth, pathwidth, and treedepth of the input graph; (2) the problem parameterised by the vertex cover number of the input graph does not admit a polynomial compression unless coNP ⊆ NP/poly, (3) it does not admit 2 o (n) algorithm under ETH, and (4) Defensive Alliance on circle graphs is NP-complete. [ABSTRACT FROM AUTHOR]

A knot in a directed graph G is a strongly connected subgraph Q of G with size at least two, such that no vertex in V (Q) is an in-neighbor of a vertex in V (G) ∖ V (Q). Knots are important graph structures in Computer Science because they characterize the existence of deadlocks in a classical distributed computation model, the so-called OR-model. Given a directed graph G , and a positive integer k , the Knot-Free Vertex Deletion (KFVD) problem consists of determining whether G has a subset S ⊆ V (G) with size at most k such that G [ V ∖ S ] contains no knot. KFVD is an NP-complete graph problem with natural applications in deadlock resolution. In this paper, we present a parameterized complexity analysis of KFVD. We prove that: KFVD is W[1]-hard when parameterized by the size of the solution; it can be solved in 2 k log ⁡ φ ⋅ n O (1) time, but assuming SETH, it cannot be solved in (2 − ϵ) k log ⁡ φ ⋅ n O (1) time, where φ is the size of the largest strongly connected subgraph of G ; it can be solved in 2 ϕ ⋅ n O (1) time, but assuming ETH, it cannot be solved in 2 o (ϕ) ⋅ n O (1) time, where ϕ is the number of vertices with out-degree at most k ; it can be solved in 2 O (t w log ⁡ t w) ⋅ n O (1) time, but assuming ETH it cannot be solved in 2 o (t w) ⋅ n O (1) time, where tw is the treewidth of the underlying undirected graph; and, it can be solved in FPT time when parameterized by the clique-width of the directed graph. In addition, lower bounds for kernelization are also provided. [ABSTRACT FROM AUTHOR]

The Offensive Alliance problem has been studied extensively during the last twenty years. A set S ⊆ V of vertices is an offensive alliance in an undirected graph G = (V , E) if each v ∈ N (S) has at least as many neighbors in S as it has neighbors (including itself) not in S. We study the classical and parameterized complexity of the Offensive Alliance problem, where the aim is to find a minimum size offensive alliance. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, treewidth, pathwidth, and treedepth of the input graph; this puts it among the few problems that are FPT when parameterized by solution size but not when parameterized by treewidth (unless FPT=W[1]), (2) the problem cannot be solved in time O ⁎ (2 o (k log ⁡ k)) where k is the solution size, unless ETH fails, (3) it does not admit a polynomial kernel parameterized by solution size and vertex cover of the input graph. On the positive side we prove that (4) it can be solved in time O ⁎ (vc (G) O (vc (G)) ) where vc (G) is the vertex cover number of the input graph. (5) it admits an FPT algorithm when parameterized by vertex integrity of input graph. In terms of classical complexity, we prove that (6) the problem cannot be solved in time 2 o (n) even when restricted to bipartite graphs, unless ETH fails, (7) it cannot be solved in time 2 o (n) even when restricted to apex graphs, unless ETH fails. We also prove that (8) it is NP-complete even when restricted to bipartite, chordal, split and circle graphs. [ABSTRACT FROM AUTHOR]