Search

Given a graph G = (V , E) and a set F of forbidden subgraphs, we study the F -Free Edge Deletion problem, where the goal is to remove a minimum number of edges such that the resulting graph does not contain any F ∈ F as a (not necessarily induced) subgraph. Enright and Meeks (Algorithmica, 2018) gave an algorithm to solve F -Free Edge Deletion whose running time on an n -vertex graph G of treewidth tw (G) is bounded by 2 O (| F | tw (G) r) n , if every graph in F has at most r vertices. We complement this result by showing that F -Free Edge Deletion is W[1]-hard when parameterized by tw (G) + | F |. We also show that F -Free Edge Deletion is W[2]-hard when parameterized by the combined parameters solution size, the feedback vertex set number and pathwidth of the input graph. A special case of particular interest is the situation in which F is the set T h + 1 of all trees on h + 1 vertices, so that we delete edges in order to obtain a graph in which every component contains at most h vertices. This is desirable from the point of view of restricting the spread of a disease in transmission networks [5]. We prove that T h + 1 -Free Edge Deletion is fixed-parameter tractable (FPT) when parameterized by the vertex cover number of the input graph. We also prove that it admits a kernel with 2 k h vertices and 2 k h 2 + k edges, when parameterized by k + h. [ABSTRACT FROM AUTHOR]

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]

• Satisfactory Partition is polynomial-time solvable for block graphs. • Satisfactory Partition is FPT parameterized by neighbourhood diversity. • Satisfactory Partition can be solved in polynomial time for graphs of bounded clique-width. • Balanced Satisfactory Partition is W[1]-hard when parameterized by treewidth. Given an undirected graph G , we study the Satisfactory Partition problem, where the goal is to decide whether it is possible to partition the vertex set of G into two parts such that each vertex has at least as many neighbours in its own part as in the other part. The Balanced Satisfactory Partition problem is a variant of the above problem where the two partite sets are required to have the same cardinality. Both problems are known to be NP-complete. This problem was introduced by Gerber and Kobler (2000) [9] and further studied by other authors, 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) Satisfactory Partition is polynomial-time solvable for block graphs, (2) Satisfactory Partition and Balanced Satisfactory Partition are fixed parameter tractable (FPT) when parameterized by neighbourhood diversity. (3) Satisfactory Partition and its balanced version can be solved in polynomial time for graphs of bounded clique-width, and (4) Balanced Satisfactory Partition is W[1]-hard when parameterized by treewidth. [ABSTRACT FROM AUTHOR]