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
