BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Soumen Maity

Soumen Maity appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsDiscrete Mathematicsmath.COComputational Complexity

Catalog footprint

What is connected

8works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2022arXiv

Maximum Minimal Feedback Vertex Set: A Parameterized Perspective

In this paper we study a maximization version of the classical Feedback Vertex Set (FVS) problem, namely, the Max Min FVS problem, in the realm of parameterized complexity. In this problem, given an undirected graph $G$, a positive integer $k$, the question is to check whether $G$ has a minimal feedback vertex set of size at least $k$. We obtain following results for Max Min FVS. 1) We first design a fixed parameter tractable (FPT) algorithm for Max Min FVS running in time $10^kn^{\mathcal{O}(1)}$. 2) Next, we consider the problem parameterized by the vertex cover number of the input graph (denoted by $\mathsf{vc}(G)$), and design an algorithm with running time $2^{\mathcal{O}(\mathsf{vc}(G)\log \mathsf{vc}(G))}n^{\mathcal{O}(1)}$. We complement this result by showing that the problem parameterized by $\mathsf{vc}(G)$ does not admit a polynomial compression unless coNP $\subseteq$ NP/poly. 3) Finally, we give an FPT-approximation scheme (fpt-AS) parameterized by $\mathsf{vc}(G)$. That is, we design an algorithm that for every $ε>0$, runs in time $2^{\mathcal{O}\left(\frac{\mathsf{vc}(G)}ε\right)} n^{\mathcal{O}(1)}$ and returns a minimal feedback vertex set of size at least $(1-ε){\sf opt}$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Offensive Alliances in Graphs

A set $S\subseteq V$ of vertices is an offensive alliance in an undirected graph $G=(V,E)$ if each $v\in N(S)$ has at least as many neighbours in $S$ as it has neighbours (including itself) not in $S$. We study the classical and parameterized complexity of the Offensive Alliance problem, where the aim is to find a minimum size offensive alliance. Our focus here lies on natural parameter as well as 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 (1) 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; we thereby resolve an open question stated by Bernhard Bliem and Stefan Woltran (2018) concerning the complexity of Offensive Alliance parameterized by treewidth, (2) unless ETH fails, Offensive Alliance problem cannot be solved in time $\mathcal{O}^{*}(2^{o(k \log k)})$ where $k$ is the solution size, (3) Offensive Alliance problem does not admit a polynomial kernel parameterized by solution size and vertex cover of the input graph. On the positive side we prove that (4) Offensive Alliance can be solved in time $\mathcal{O}^{*}(\tt{vc(G)}^{\mathcal{O}(\tt{vc(G)})})$ where $\tt{vc(G)}$ is the vertex cover number of the input graph. In terms of classical complexity, we prove that (5) Offensive Alliance problem cannot be solved in time $2^{o(n)}$ even when restricted to bipartite graphs, unless ETH fails, (6) Offensive Alliance problem cannot be solved in time $2^{o(\sqrt{n})}$ even when restricted to apex graphs, unless ETH fails. We also prove that (7) Offensive Alliance problem is NP-complete even when restricted to bipartite, chordal, split and circle graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Parameterized Complexity of Upper Edge Domination

In this paper we study a maximization version of the classical Edge Dominating Set (EDS) problem, namely, the Upper EDS problem, in the realm of Parameterized Complexity. In this problem, given an undirected graph $G$, a positive integer $k$, the question is to check whether $G$ has a minimal edge dominating set of size at least $k$. We obtain the following results for Upper EDS. We prove that Upper EDS admits a kernel with at most $4k^2-2$ vertices. We also design a fixed-parameter tractable (FPT) algorithm for Upper EDS running in time $2^{\mathcal{O}(k)} \cdot n^{\mathcal{O}(1)}$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Harmless Set Problem

Given a graph $G = (V,E)$, a threshold function $t~ :~ V \rightarrow \mathbb{N}$ and an integer $k$, we study the Harmless Set problem, 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 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 problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, pathwidth, treedepth, and even the size of a minimum vertex deletion set into graphs of pathwidth and treedepth at most three. On dense graphs, we show that the problem is W[1]-hard parameterized by cluster vertex deletion number. We also show that the Harmless Set problem with majority thresholds is W[1]-hard when parameterized by the treewidth of the input graph. We prove that the Harmless Set problem can be solved in polynomial time on graph with bounded cliquewidth. On the positive side, we obtain fixed-parameter algorithms for the problem with respect to neighbourhood diversity, twin cover and vertex integrity of the input graph. We show that the problem parameterized by the solution size is fixed parameter tractable on planar graphs. We thereby resolve two open questions stated in C. Bazgan and M. Chopin (2014) concerning the complexity of {\sc Harmless Set} parameterized by the treewidth of the input graph and on planar graphs with respect to the solution size.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Edge Deletion to Restrict the Size of an Epidemic

Given a graph $G=(V,E)$, a set $\mathcal{F}$ of forbidden subgraphs, we study $\mathcal{F}$-Free Edge Deletion, where the goal is to remove minimum number of edges such that the resulting graph does not contain any $F\in \mathcal{F}$ as a subgraph. For the parameter treewidth, the question of whether the problem is FPT has remained open. Here we give a negative answer by showing that the problem is W[1]-hard when parameterized by the treewidth, which rules out FPT algorithms under common assumption. Thus we give a solution to the conjecture posted by Jessica Enright and Kitty Meeks in [Algorithmica 80 (2018) 1857-1889]. We also prove that the $\mathcal{F}$-Free Edge Deletion problem is W[2]-hard when parameterized by the solution size $k$, feedback vertex set number or pathwidth of the input graph. A special case of particular interest is the situation in which $\mathcal{F}$ is the set $\mathcal{T}_{h+1}$ of all trees on $h+1$ vertices, so that we delete edges in order to obtain a graph in which every component contains at most $h$ vertices. This is desirable from the point of view of restricting the spread of disease in transmission network. We prove that the $\mathcal{T}_{h+1}$-Free Edge Deletion problem is fixed-parameter tractable (FPT) when parameterized by the vertex cover number. We also prove that it admits a kernel with $O(hk)$ vertices and $O(h^2k)$ edges, when parameterized by combined parameters $h$ and the solution size $k$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Satisfactory Partition Problem

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 was introduced by Gerber and Kobler [European J. Oper. Res. 125 (2000) 283-291] and further studied by other authors, but its parameterized complexity remains open until now. It is known that the Satisfactory Partition problem, as well as a variant where the parts are required to be of the same cardinality, are NP-complete. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is FPT when parameterized by the neighbourhood diversity of the input graph, (2) it can be solved in $O(n^{8 {\tt cw}})$ where ${\tt cw}$ is the clique-width,(3) a generalized version of the problem is W[1]-hard when parameterized by the treewidth.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Improved Strength Four Covering Arrays with Three Symbols

A covering array $t$-$CA(n,k,g)$, of size $n$, strength $t$, degree $k$, and order $g$, is a $k\times n$ array on $g$ symbols such that every $t\times n$ sub-array contains every $t\times 1$ column on $g$ symbols at least once. Covering arrays have been studied for their applications to software testing, hardware testing, drug screening, and in areas where interactions of multiple parameters are to be tested. In this paper, we present an algebraic construction that improves many of the best known upper bounds on $n$ for covering arrays 4-$CA(n,k,g)$ with $g=3$. The $coverage$ $measure$ $μ_t(A)$ of a testing array $A$ is defined by the ratio between the number of distinct $t$-tuples contained in the column vectors of $A$ and the total number of $t$-tuples. A covering array is a testing array with full coverage. The $covering$ $arrays$ $with$ $budget$ $constraints$ $problem$ is the problem of constructing a testing array of size at most $n$ having largest possible coverage measure, given values of $k,g$ and $n$. This paper presents several strength four testing arrays with high coverage. The construction here is a generalisation of the construction methods used by Chateauneuf, Colbourn and Kreher, and Meagher and Stevens.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Mixed Covering Arrays on 3-Uniform Hypergraphs

Covering arrays are combinatorial objects that have been successfully applied in the design of test suites for testing systems such as software, circuits and networks, where failures can be caused by the interaction between their parameters. In this paper, we perform a new generalization of covering arrays called covering arrays on 3-uniform hypergraphs. Let $n, k$ be positive integers with $k\geq 3$. Three vectors $x\in \mathbb Z_{g_1}^n$, $y\in \mathbb Z_{g_2}^n$, $z\in \mathbb Z_{g_3}^n$ are {\it 3-qualitatively independent} if for any triplet $(a, b, c) \in \mathbb Z_{g_1}\,\times\, \mathbb Z_{g_2}\,\times\,\mathbb Z_{g_3}$, there exists an index $ j\in \lbrace 1, 2,...,n \rbrace $ such that $( x(j), y(j), z(j)) = (a, b, c)$. Let $H$ be a 3-uniform hypergraph with $k$ vertices $v_1,v_2,\ldots,v_k$ with respective vertex weights $g_1,g_2,\ldots,g_k$. A mixed covering array on $H$, denoted by $3-CA(n,H, \prod_{i=1}^{k}g_{i})$, is a $k\times n$ array such that row $i$ corresponds to vertex $v_i$, entries in row $i$ are from $Z_{g_i}$; and if $\{v_x,v_y,v_z\}$ is a hyperedge in $H$, then the rows $x,y,z$ are 3-qualitatively independent. The parameter $n$ is called the size of the array. Given a weighted 3-uniform hypergraph $H$, a mixed covering array on $H$ with minimum size is called optimal. We outline necessary background in the theory of hypergraphs that is relevant to the study of covering arrays on hypergraphs. In this article, we introduce five basic hypergraph operations to construct optimal mixed covering arrays on hypergraphs. Using these operations, we provide constructions for optimal mixed covering arrays on $α$-acyclic 3-uniform hypergraphs, conformal 3-uniform hypertrees having a binary tree as host tree, and on some specific 3-uniform cycle hypergraphs.

0 citations0 reviewsNo code linkedOpen access