Search

In this paper, we study the Harmless Set problem from a parameterized complexity perspective. Given a graph G = (V , E) , a threshold function t : V → N and an integer k, we study Harmless Set, where the goal is to find a subset of vertices S ⊆ V of size at least k such that every vertex v ∈ V has fewer than t(v) neighbours in S. On the positive side, we obtain fixed-parameter algorithms for the problem when parameterized by the neighbourhood diversity, the twin-cover number and the vertex integrity of the input graph. We complement two of these results from the negative side. On dense graphs, we show that the problem is W[1]-hard parameterized by cluster vertex deletion number—a natural generalization of the twin-cover number. We show that the problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, pathwidth, and treedepth—a natural generalization of the vertex integrity. We thereby resolve one open question stated by Bazgan and Chopin (Discrete Optim 14(C):170–182, 2014) concerning the complexity of Harmless Set parameterized by the treewidth of the input graph. We also show that Harmless Set for a special case where each vertex has the threshold set to half of its degree (the so-called Majority Harmless Set problem) is W[1]-hard when parameterized by the treewidth of the input graph. Given a graph G and an irredundant c-expression of G, we prove that Harmless Set can be solved in XP-time when parameterized by clique-width. [ABSTRACT FROM AUTHOR]

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]

The Maximum Covering Location Problem (MCLP) is a well-studied problem in the field of operations research. Given a network with positive or negative demands on the nodes, a positive integer k, the MCLP seeks to find k potential facility centers in the network such that the neighborhood coverage is maximized. We study the variant of MCLP where edges of the network are subject to random failures due to some disruptive events. One of the popular models capturing the unreliable nature of the facility location is the linear reliability ordering (LRO) model. In this model, with every edge e of the network, we associate its survival probability 0 ≤ pe ≤ 1, or equivalently, its failure probability 1 − pe. The failure correlation in LRO is the following: If an edge e fails then every edge e ′ with p e ′ ≤ p e surely fails. The task is to identify the positions of k facilities that maximize the expected coverage. We refer to this problem as Expected Coverage problem. We study the Expected Coverage problem from the parameterized complexity perspective and obtain the following results. 1. For the parameter pathwidth, we show that the Expected Coverage problem is W[1]-hard. We find this result a bit surprising, because the variant of the problem with non-negative demands is fixed-parameter tractable (FPT) parameterized by the treewidth of the input graph. 2. We complement the lower bound by the proof that Expected Coverage is FPT being parameterized by the treewidth and the maximum vertex degree. We give an algorithm that solves the problem in time 2 O (tw log Δ) n O (1) , where tw is the treewidth, Δ is the maximum vertex degree, and n the number of vertices of the input graph. In particular, since Δ ≤ n, it means the problem is solvable in time n O (tw) , that is, is in XP parameterized by treewidth. [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]

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]