Parameterized Complexity of the Hiding Leader problem

Abstract

In this thesis, we study the theory of parametrized complexity and examine parameterized complexity of the Hiding Leader problem. We discuss standard tools and techniques for showing the fixed-parameter tractability of parameterized problems like kernelization and branching. We review fixed-parameter intractability and show, using parameterized reductions and W-hierarchy, that some problems are unlikely to be fixed-parameter tractable. Given a graph G = (V,E), a subset L ⊆ V of leaders, an integer k that denotes the maximum number of edges that we are allowed to add in G, an integer d that denotes the least number of followers in F = V \ L whose final centrality should be at least as high as any leader, the goal is to compute if there exists a subset W ⊆ F × F such that (i) |W| ≤ k, and (ii) there exists a F′ ⊆ F with |F′| ≥ d satisfying c(G′, f) ≥ c(G′, ℓ) for all f ∈ F′ and ℓ ∈ L where G′ = (V,E ∪ W). We study the parameterized complexity of the problem in the setting of degree centrality for a few sets of parameters and shed light on its fixed-parameter intractability using tools discussed apriori. We obtain the following results for the Hiding Leader problem: 1. The Hiding Leader problem is W[1]-hard when parameterized by d + k. Therefore, the problem is W[1]-hard when parameterized by only d or k. 2. The Hiding Leader problem admits a kernel of size (d − 1)(Δ + 1) + 1, where Δ denotes the maximum degree of G. 3. The Hiding Leader problem in the setting of core centrality is W[1]-hard when parameterized by k + d. 4. Finally, we briefly touch upon the problem and some results in the core-centrality setting. xi