Author name cluster

Bireswar Das

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

2 author rows

STOC Conference 2024 Conference Paper

The Minimal Faithful Permutation Degree of Groups without Abelian Normal Subgroups

Bireswar Das
Dhara Thakkar

Cayley’s theorem says that every finite group G can be viewed as a subgroup of a symmetric group S m for some integer m . The minimal faithful permutation degree µ( G ) of a finite group G is the smallest integer m such that there is an injective homomorphism φ from G to S m . The main result of this paper is a randomized polynomial time algorithm for computing the minimal faithful permutation degree of semisimple permutation groups. Semisimple groups are groups without any abelian normal subgroups. Apart from this, we show that: 1. For any primitive permutation group G , µ( G ) can be computed in quasi-polynomial time. 2. Given a permutation group G and an integer k , the problem of deciding if µ( G ) ≤ k is in NP . 3. For a group G given by its Cayley table, µ( G ) can be computed in DSPACE (log 3 | G |).

Details

TCS Journal 2020 Journal Article

Polynomial-time algorithm for isomorphism of graphs with clique-width at most three

Bireswar Das
Murali Krishna Enduri
I. Vinod Reddy

The clique-width is a measure of complexity of decomposing graphs into certain tree-like structures. The class of graphs with bounded clique-width contains bounded tree-width graphs. We give a polynomial time graph isomorphism algorithm for graphs with clique-width at most three. Our work is independent of the work by Grohe et al. [1] showing that the isomorphism problem for graphs of bounded clique-width is polynomial time.

Details DOI

TCS Journal 2019 Journal Article

On structural parameterizations of firefighting

Bireswar Das
Murali Krishna Enduri
Masashi Kiyomi
Neeldhara Misra
Yota Otachi
I. Vinod Reddy
Shunya Yoshimura

The Firefighting problem is defined as follows. At time t = 0, a fire breaks out at a vertex of a graph. At each time step t ≥ 1, a firefighter permanently defends (protects) an unburned vertex, and the fire then spreads to all undefended neighbors from the vertices on fire. This process stops when the fire cannot spread anymore. The goal is to find a sequence of vertices for the firefighter that maximizes the number of saved (non burned) vertices. The Firefighting problem turns out to be NP -hard even when restricted to bipartite graphs or trees of maximum degree three. We study the parameterized complexity of the Firefighting problem for various structural parameterizations. All our parameters measure the distance to a graph class (in terms of vertex deletion) on which the Firefighting problem admits a polynomial-time algorithm. To begin with, we show that the problem is W [ 1 ] -hard when parameterized by the size of a modulator to diameter at most two graphs and split graphs. In contrast to the above intractability results, we show that Firefighting is fixed parameter tractable ( FPT ) when parameterized by the size of a modulator to cographs, threshold graphs and disjoint unions of stars. We further investigate the kernelization complexity of the problem and show that it does not admit a polynomial kernel when parameterized by the size of a modulator to a disjoint union of stars under some complexity-theoretic assumptions.

Details DOI

I&C Journal 2017 Journal Article

CNF and DNF succinct graph encodings

Bireswar Das
Patrick Scharpfenecker
Jacobo Torán

It is well-known that succinct encodings of computational problems – using circuits or formulas to encode large instances – generally result in an exponential complexity blow-up compared to their original complexity. We introduce a new way to encode graph problems, based on CNF or DNF formulas. We show that – contrary to the other existing succinct models – there are examples of problems whose complexity does not increase when encoded in the new form, or increases to an intermediate complexity class less powerful than the exponential blow up. We also study the complexity of the succinct versions of the Graph Isomorphism problem. We show that all the versions are hard for PSPACE. Although the exact complexity of these problems is still unknown, we show that under most existing succinct models the different versions of the problem are equivalent. We also give an algorithm for the DNF encoded version of GI whose running time depends mainly on the number of terms in the succinct representation.

Details DOI

I&C Journal 2017 Journal Article

Zero knowledge and circuit minimization

Eric Allender
Bireswar Das

We show that every problem in the complexity class SZK (Statistical Zero Knowledge) is efficiently reducible to the Minimum Circuit Size Problem ( MCSP ). In particular Graph Isomorphism lies in RP MCSP. This is the first theorem relating the computational power of Graph Isomorphism and MCSP, despite the long history these problems share, as candidate NP -intermediate problems.

Details DOI

I&C Journal 2012 Journal Article

Restricted space algorithms for isomorphism on bounded treewidth graphs

Bireswar Das
Jacobo Torán
Fabian Wagner

The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time. We give restricted space algorithms for these problems proving the following results: • Isomorphism for bounded tree distance width graphs is in L and thus complete for the class. We also show that for this kind of graphs a canon can be computed within logspace. • For bounded treewidth graphs, when both input graphs are given together with a tree decomposition, the problem of whether there is an isomorphism which respects the decompositions (i. e. when only isomorphisms are considered, mapping bags in one decomposition blockwise onto bags in the other decomposition) is in L. • For bounded treewidth graphs, when one of the input graphs is given with a tree decomposition the isomorphism problem is in LogCFL. • As a corollary the isomorphism problem for bounded treewidth graphs is in LogCFL. This improves the known TC1 upper bound for the problem given by Grohe and Verbitsky.

Details DOI

I&C Journal 2012 Journal Article

The isomorphism problem for k-trees is complete for logspace

V. Arvind
Bireswar Das
Johannes Köbler
Sebastian Kuhnert

We show that, for k constant, k-tree isomorphism can be decided in logarithmic space by giving an O ( k log n ) space canonical labeling algorithm. The algorithm computes a unique tree decomposition, uses colors to fully encode the structure of the original graph in the decomposition tree and invokes Lindellʼs tree canonization algorithm. As a consequence, the isomorphism, the automorphism, as well as the canonization problem for k-trees are all complete for deterministic logspace. Completeness for logspace holds even for simple structural properties of k-trees. We also show that a variant of our canonical labeling algorithm runs in time O ( ( k + 1 )! n ), where n is the number of vertices, yielding the fastest known FPT algorithm for k-tree isomorphism.

Details DOI