Subject

Sort by: Order: Results:

  • 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 ...
  • 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 ...
  • 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 ...
  • 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)
  • 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 ...
  • 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 ...
  • 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 ...
  • 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 ...
  • 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 ...
  • 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 ...
  • 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 ...
  • 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 ...
  • 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 ...
  • 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 ...
  • 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 ...
  • 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 ...