Digital Repository

Parameterized Complexity of the Hiding Leader problem

Show simple item record

dc.contributor.advisor MAITY, SOUMEN
dc.contributor.author KARRA, MOHAN
dc.date.accessioned 2023-01-10T12:15:36Z
dc.date.available 2023-01-10T12:15:36Z
dc.date.issued 2023-01
dc.identifier.citation 72 en_US
dc.identifier.uri http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/7553
dc.description.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 en_US
dc.language.iso en en_US
dc.subject parameterized complexity en_US
dc.subject Kernelization en_US
dc.subject Social Network Analysis en_US
dc.subject Hiding Leader en_US
dc.subject Independent set en_US
dc.subject Fixed-parameter Tractable en_US
dc.subject W-[1]-hard en_US
dc.title Parameterized Complexity of the Hiding Leader problem en_US
dc.type Thesis en_US
dc.description.embargo One Year en_US
dc.type.degree BS-MS en_US
dc.contributor.department Dept. of Mathematics en_US
dc.contributor.registration 20161105 en_US


Files in this item

This item appears in the following Collection(s)

  • MS THESES [1705]
    Thesis submitted to IISER Pune in partial fulfilment of the requirements for the BS-MS Dual Degree Programme/MSc. Programme/MS-Exit Programme

Show simple item record

Search Repository


Advanced Search

Browse

My Account