7 papers
An Improved Time-Efficient Approximate Kernelization for Connected Treedepth Deletion Set
Eduard Eiben, Diptapriyo Majumdar, M. S. Ramanujan
We study the CONNECTED η-TREEDEPTH DELETION problem where the input instance is an undireted graph G = (V, E) and an integer k. The objective is to decide if G has a set S \subsete…
Valued Authorization Policy Existence Problem: Theory and Experiments
Jason Crampton, Eduard Eiben, Gregory Gutin +2
Recent work has shown that many problems of satisfiability and resiliency in workflows may be viewed as special cases of the authorization policy existence problem (APEP), which re…
Towards Better Understanding of User Authorization Query Problem via Multi-variable Complexity Analysis
Jason Crampton, Gregory Gutin, Diptapriyo Majumdar
User authorization queries in the context of role-based access control have attracted considerable interest in the last 15 years. Such queries are used to determine whether it is p…
Parameterized Pre-coloring Extension and List Coloring Problems
Gregory Gutin, Diptapriyo Majumdar, Sebastian Ordyniak +1
Golovach, Paulusma and Song (Inf. Comput. 2014) asked to determine the parameterized complexity of the following problems parameterized by : (1) Given a graph , a clique modu…
On the Approximate Compressibility of Connected Vertex Cover
Diptapriyo Majumdar, M. S. Ramanujan, Saket Saurabh
The Connected Vertex Cover problem, where the goal is to compute a minimum set of vertices in a given graph which forms a vertex cover and induces a connected subgraph, is a fundam…
Bounded and Approximate Strong Satisfiability in Workflows
Jason Crampton, Gregory Gutin, Diptapriyo Majumdar
There has been a considerable amount of interest in recent years in the problem of workflow satisfiability, which asks whether the existence of constraints in a workflow specificat…