Subject

Sort by: Order: Results:

  • Parameterized Complexity of Fair Feedback Vertex Set Problem 
    MULUK, KOMAL (2019-05)
    Feedback Vertex Set (FVS) problem is a well known NP-complete problem in computational complexity theory. This is a vertex deletion problem in which given a graph G=(V,E) and an integer k, we are asked to find a subset ...
  • Parameterized Complexity of Fair Feedback Vertex Set Problem 
    Kanesh, Lawqueen; MAITY, SOUMEN; MULUK, KOMAL; Saurabh, Saket (Springer, 2020-06)
    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 ...
  • Parameterized Complexity of Satisfactory Partition Problem 
    GAIKWAD, AJINKYA; MAITY, SOUMEN; TRIPATHI, SHUVAM KANT (Springer Nature, 2020-12)
    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 Small Set Vertex Expansion Problem 
    MAITY, SOUMEN (Springer Nature, 2020-12)
    Given a graph G=(V,E) , the vertex expansion of a set S⊂V is defined as ΦV(S)=|N(S)
  • Parameterized Complexity of Defensive and Offensive Alliances in Graphs 
    GAIKWAD, AJINKYA; MAITY, SOUMEN; TRIPATHI, SHUVAM KANT (Springer Nature, 2021-01)
    In this paper we study the problem of finding small defensive and offensive alliances in a simple graph. Given a graph G=(V,E) and a subset S⊆V(G) , we denote by dS(v) the degree of a vertex v∈V in G[S], the subgraph of G ...
  • The Balanced Satisfactory Partition Problem 
    GAIKWAD, AJINKYA; MAITY, SOUMEN; TRIPATHI, SHUVAM KANT (Springer Nature, 2021-01)
    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 ...
  • Parameterized complexity of fair feedback vertex set problem 
    Kanesh, Lawqueen; MAITY, SOUMEN; Muluk, Komal; Saurabh, Saket (Elsevier B.V., 2021-05)
    Given a graph , a subset is said to be a feedback vertex set of G if 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 ...
  • The Small Set Vertex Expansion Problem 
    AGRAWAL, GARIMA; MAITY, SOUMEN (Elsevier B.V., 2021-09)
    In the Small Set Vertex Expansion (SSVE) problem, we are given a graph and a positive integer , the goal is to return a set of k nodes minimizing the vertex expansion . The Small Set Vertex Expansion problem has not been ...
  • On Structural Parameterizations of the Offensive Alliance Problem 
    GAIKWAD, AJINKYA; MAITY, SOUMEN (Springer Nature, 2021-12)
    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 neighbours in S ...
  • Parameterized Intractability of Defensive Alliance Problem 
    GAIKWAD, AJINKYA; MAITY, SOUMEN; TRIPATHI, SHUVAM KANT (Springer Nature, 2022-01)
    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 ...
  • Parameterized complexity of satisfactory partition problem 
    GAIKWAD, AJINKYA; MAITY, SOUMEN; TRIPATHI, SHUVAM KANT (Elsevier B.V., 2022-03)
    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 ...
  • On the Harmless Set Problem Parameterized by Treewidth 
    GAIKWAD, AJINKYA; MAITY, SOUMEN (Springer Nature, 2022-03)
    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 ...
  • Globally minimal defensive alliances 
    GAIKWAD, AJINKYA; MAITY, SOUMEN (Elsevier B.V., 2022-08)
    A defensive alliance in an undirected graph is a nonempty set of vertices S satisfying the condition that every vertex has at least as many neighbours (including itself) in S as it has in . We consider the notion of ...
  • Defensive alliances in graphs 
    GAIKWAD, AJINKYA; MAITY, SOUMEN (Elsevier B.V., 2022-09)
    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 ...
  • Further parameterized algorithms for the -free edge deletion problem 
    GAIKWAD, AJINKYA; MAITY, SOUMEN (Elsevier B.V., 2022-10)
    Given a graph �=(�,�) and a set � of forbidden subgraphs, we study the �-FREE EDGE DELETION problem, where the goal is to remove a minimum number of edges such that the resulting graph does not contain any �∈� as a (not ...
  • On Structural Parameterizations of the Harmless Set Problem 
    GAIKWAD, AJINKYA; MAITY, SOUMEN (Springer Nature, 2024-01)
    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 ...
  • Offensive alliances in graphs 
    GAIKWAD, AJINKYA; MAITY, SOUMEN (Elsevier B.V., 2024-03)
  • Parameterized complexity of locally minimal defensive alliances 
    GAIKWAD, AJINKYA; MAITY, SOUMEN; TRIPATHI, SHUVAM KANT (Elsevier B.V., 2025-09)
    A set S of vertices of a graph is a defensive alliance if, for each element of S, the majority of its neighbours is in S. We consider the notion of local minimality in this paper. We are interested in locally minimal ...