Ajinkya Gaikwad

Ajinkya Gaikwad

I am a PhD student working in the field of Parameterized Complexity Theory. My research is supported by the Prime Minister's Research Fellowship.

Publications

Structural Parameterizations of the Harmless Set Problem

Published in Algorithmica 2024, 2024

In this paper, we study the {\sc Harmless Set} problem from a parameterized complexity perspective. Given a graph $G = (V,E)$, a threshold function$~t~ :~ V \rightarrow \mathbb{N}$ and an integer $k$, we study {\sc Harmless Set}, where the goal is to find a subset of vertices $S \subseteq V$ of size at least$~k$ such that every vertex $v\in 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 (\emph{Discrete Optimization}, 2014) concerning the complexity of {\sc Harmless Set} parameterized by the treewidth of the input graph. We also show that {\sc Harmless Set} for a special case where each vertex has the threshold set to half of its degree (the so-called {\sc 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 {\sc Harmless Set} can be solved in XP-time when parameterized by clique-width.

Download here

Parameterized Intractability of Defensive Alliance Problem

Published in CALDAM 2022: Algorithms and Discrete Applied Mathematics, 2022

The DEFENSIVE ALLIANCE problem has been studied extensively during the last twenty years. A set R of vertices of a graph is a defensive alliance if, for each element of R, the majority of its neighbours are in R. The problem of finding a defensive alliance of minimum size in a given graph is NP-hard. Fixed-parameter tractability results have been obtained for the solution size and some structural parameters such as the vertex cover number and neighbourhood diversity. For the parameter treewidth the problem is W[1]-hard. However, for the parameters pathwidth and feedback vertex set, the question of whether the problem is FPT has remained open. In this work we prove that (1) the DEFENSIVE ALLIANCE problem is W[1]-hard when parameterized by the pathwidth of the input graph, (2) the EXACT DEFENSIVE ALLIANCE problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, pathwidth, treewidth and treedepth and (3) a generalization of the DEFENSIVE ALLIANCE problem is W[1]-hard parameterized by the size of a vertex deletion set into trees of height at most 6.

Download here

Defensive alliances in graphs

Published in Theoretical Computer Science, 2022

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 algorithm under ETH, and (4) Defensive Alliance on circle graphs is NP-complete.

Download here

Parameterized complexity of satisfactory partition problem

Published in Theoretical Computer Science, 2022

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.

Download here

Globally minimal defensive alliances

Published in Information Processing Letters, 2022

We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that the Globally Minimal Defensive Alliance problem is W[1]-hard when parameterized by the treewidth of the graph. We also present a polynomial-time algorithm when the input graph happens to be a tree.

Download here

On the Harmless Set Problem Parameterized by Treewidth

Published in WALCOM 2022: WALCOM: Algorithms and Computation, 2022

Given a graph G=(V,E), a threshold function t : V→N and an integer k, we study the HARMLESS SET problem, where the goal is to find a subset of vertices S⊆V of size at least k such that every vertex v in V has less than t(v) neighbors in S. We enhance our understanding of the problem from the viewpoint of parameterized complexity. Our focus lies on parameters that measure the structural properties of the input instance. We show that the HARMLESS SET problem with majority thresholds is W[1]-hard when parameterized by the treewidth of the input graph. On the positive side, we obtain a fixed-parameter tractable algorithm for the problem with respect to neighbourhood diversity.

Download here

Parameterized Complexity of Defensive and Offensive Alliances in Graphs

Published in ICDCIT: Distributed Computing and Internet Technology, 2021

The problems of finding small defensive and offensive alliances are NP-complete. We enhance our understanding of the problems from the viewpoint of parameterized complexity. We mainly focus on structural parameterizations of the problem.

Download here

On Structural Parameterizations of the Offensive Alliance Problem

Published in COCOA 2021: Combinatorial Optimization and Applications, 2021

We study the parameterized complexity of the Offensive Alliance problem, where the aim is to find a minimum size offensive alliance. Our focus here lies on parameters that measure the structural properties of the input instance. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that 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.

Download here

The Balanced Satisfactory Partition Problem

Published in SOFSEM: Theory and Practice of Computer Science, 2021

The Satisfactory Partition problem asks whether it is possible to partition the vertex set of a given undirected graph 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 but its parameterized complexity remains open until now. We enhance our understanding of the problem from the viewpoint of parameterized complexity.

Download here

Parameterized Complexity of Satisfactory Partition Problem

Published in COCOA: Combinatorial Optimization and Applications, 2020

The Satisfactory Partition problem consists in deciding if the set of vertices of a given undirected graph can be partitioned into two nonempty parts such that each vertex has at least as many neighbours in its part as in the other part. This problem is known to be NP-complete. It was introduced by Gerber and Kobler and further studied by other authors. We enhance our understanding of the problem from the viewpoint of parameterized complexity.

Download here