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]

• Small Set Vertex Expansion is W[1]-hard when parameterized by the solution size. • Small Set Vertex Expansion is FPT when parameterized by neighbourhood diversity of the input graph. • Small Set Vertex Expansion can be solved in polynomial time for graphs of bounded clique-width. • Small Set Vertex Expansion is FPT when parameterized by treewidth of the input graph. In the Small Set Vertex Expansion (SSVE) problem, we are given a graph G = (V , E) and a positive integer k ≤ | V (G) | 2 , the goal is to return a set S ⊂ V (G) of k nodes minimizing the vertex expansion Φ V (S) = | N (S) |. The Small Set Vertex Expansion problem has not been as well studied as its edge-based counterpart Small Set Expansion (SSE). SSE, and SSVE to a less extend, have been studied due to their connection to other hard problems including the Unique Games Conjecture and Graph Colouring. The Small Set Vertex Expansion is known to be NP-complete. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is W[1]-hard when parameterized by the solution size, (2) the problem is fixed-parameter tractable (FPT) when parameterized by the neighbourhood diversity of the input graph, (3) it can be solved in polynomial time for graphs of bounded clique-width, and (4) it is fixed-parameter tractable (FPT) when parameterized by treewidth of the input graph. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) , a subset S ⊆ V (G) is said to be a feedback vertex set of G if G − S is a forest. In the Feedback Vertex Set (FVS) problem, we are given an undirected graph G , and a positive integer k , the question is whether there exists a feedback vertex set of size at most k. In this paper, we study three variants of the FVS problem: Unrestricted Fair FVS , Restricted Fair FVS , and Relaxed Fair FVS. In Unrestricted Fair FVS , we are given a graph G and a positive integer ℓ , the question is does there exist a feedback vertex set S ⊆ V (G) (of any size) such that for every vertex v ∈ V (G) , v has at most ℓ neighbours in S. First, we study Unrestricted Fair FVS from different parameterizations such as treewidth, treedepth, and neighbourhood diversity and obtain several results (both tractability and intractability). Next, we study Restricted Fair FVS , where we are also given an integer k in the input and we demand the size of S to be at most k. This problem is trivially NP-complete; we show that Restricted Fair FVS when parameterized by the solution size k and the maximum degree Δ of the graph G , admits a kernel of size O (Δ k). Finally, we study the Relaxed Fair FVS problem, where we want that the size of S is at most k and for every vertex v outside S , v has at most ℓ neighbours in S. We give an FPT algorithm for Relaxed Fair FVS problem running in time c k n O (1) , for a fixed constant c. [ABSTRACT FROM AUTHOR]

An input to a conflict-free variant of a classical problem Γ , called Conflict-Free Γ , consists of an instance I of Γ coupled with a graph H, called the conflict graph. A solution to Conflict-Free Γ in (I, H) is a solution to I in Γ , 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. [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]

And/or graphs are well-known data structures with several applications in many fields of computer science, such as Artificial Intelligence, Distributed Systems, Software Engineering, and Operations Research. An and/or graph is an acyclic digraph G containing a single source vertex s , where every vertex v ∈ V ( G ) has a label f ( v ) ∈ { and,or }. In an and/or graph, (weighted) edges represent dependency relations between vertices: a vertex labeled and depends on all of its out-neighbors, while a vertex labeled or depends on only one of its out-neighbors. A solution subgraph H of an and/or graph G is a subdigraph of G containing its source vertex and such that if an and -vertex (resp. or -vertex) is included in H then all (resp. one) of its out-edges must also be included in H . In general, solution subgraphs represent feasible solutions of problems modeled by and/or graphs. The optimization problem associated with an and/or graph G consists of finding a minimum weight solution subgraph H of G , where the weight of a solution subgraph is the sum of the weights of its edges. Because of its wide applicability, in this work we develop a multivariate investigation of this optimization problem. In a previous paper (Souza et al., 2013) we have analyzed the complexity of such a problem under various aspects, including parameterized versions of it. However, the main open question has remained open: Is the problem of finding a solution subgraph of weight at most k (where k is the parameter) in FPT? In this paper we answer negatively to this question, proving the W[1]-hardness of the problem, and its W[P]-completeness when zero-weight edges are allowed. We also show that the problem is fixed-parameter tractable when parameterized by the tree-width, but it is W[SAT]-hard with respect to the clique-width and k as aggregated parameters. In addition, we show that when the out-edges of each or -vertex have all the same weight (a condition very common in practice), the problem becomes fixed-parameter tractable by the clique-width. Finally, using a framework developed by Bodlaender et al . (2009) and Fortnow and Santhanam (2011), based upon the notion of compositionality, we show that the tractable cases do not admit a polynomial kernel unless NP ⊆ coNP∕poly , even restricted to instances without or -vertices with out-degree greater than two. [ABSTRACT FROM AUTHOR]

A proper k-coloring of a graph G is a partition c = ( S i ) i ∈ [ 1 , k ] of V ( G ) into k stable sets S 1 , … , S k . Given a weight function w : V ( G ) → R + , the weight of a color S i is defined as w ( i ) = max v ∈ S i ⁡ w ( v ) and the weight of a coloring c as w ( c ) = ∑ i = 1 k w ( i ) . Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair ( G , w ), denoted by σ ( G , w ) , as the minimum weight of a proper coloring of G . For a positive integer r , they also defined σ ( G , w ; r ) as the minimum of w ( c ) among all proper r -colorings c of G . The complexity of determining σ ( G , w ) when G is a tree was open for almost 20 years, until Araújo et al. [SIAM J. Discrete Math., 2014] recently proved that the problem cannot be solved in time n o ( log ⁡ n ) on n -vertex trees unless the Exponential Time Hypothesis (ETH) fails. The objective of this article is to provide hardness results for computing σ ( G , w ) and σ ( G , w ; r ) when G is a tree or a forest, relying on complexity assumptions weaker than the ETH. Namely, we study the problem from the viewpoint of parameterized complexity, and we assume the weaker hypothesis FPT ≠ W [ 1 ] . Building on the techniques of Araújo et al. , we prove that when G is a forest, computing σ ( G , w ) is W [ 1 ] -hard parameterized by the size of a largest connected component of G , and that computing σ ( G , w ; r ) is W [ 2 ] -hard parameterized by r . Our results rule out the existence of FPT algorithms for computing these invariants on trees or forests for many natural choices of the parameter. [ABSTRACT FROM AUTHOR]