On the parallel parameterized complexity of the graph isomorphism problem

Show simple item record

dc.contributor.author Das, Bireswar
dc.contributor.author Enduri, Murali Krishna
dc.contributor.author Reddy, I. Vinod
dc.date.accessioned 2018-01-30T11:28:22Z
dc.date.available 2018-01-30T11:28:22Z
dc.date.issued 2017-12
dc.identifier.citation Das, Bireswar; Enduri, Murali Krishna; and Reddy, I. Vinod, "On the parallel parameterized complexity of the graph isomorphism problem", arXiv, Cornell University Library, DOI: arXiv:1711.08885, Dec. 2017. en_US
dc.identifier.uri http://arxiv.org/abs/1711.08885
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/3436
dc.description.abstract In this paper, we study the parallel and the space complexity of the graph isomorphism problem (\GI{}) for several parameterizations. Let H={H1,H2,?,Hl} be a finite set of graphs where |V(Hi)|?d for all i and for some constant d. Let G be an H-free graph class i.e., none of the graphs G?G contain any H?H as an induced subgraph. We show that \GI{} parameterized by vertex deletion distance to G is in a parameterized version of $\AC^1$, denoted $\PL$-$\AC^1$, provided the colored graph isomorphism problem for graphs in G is in $\AC^1$. From this, we deduce that \GI{} parameterized by the vertex deletion distance to cographs is in $\PL$-$\AC^1$. The parallel parameterized complexity of \GI{} parameterized by the size of a feedback vertex set remains an open problem. Towards this direction we show that the graph isomorphism problem is in $\PL$-$\TC^0$ when parameterized by vertex cover or by twin-cover. Let G? be a graph class such that recognizing graphs from G? and the colored version of \GI{} for G? is in logspace ($\L$). We show that \GI{} for bounded vertex deletion distance to G? is in $\L$. From this, we obtain logspace algorithms for \GI{} for graphs with bounded vertex deletion distance to interval graphs and graphs with bounded vertex deletion distance to cographs.
dc.description.statementofresponsibility by Bireswar Das, Murali Krishna Enduri and I. Vinod Reddy
dc.language.iso en en_US
dc.publisher Cornell University Library en_US
dc.subject Computational Complexity en_US
dc.subject Data Structures and Algorithms en_US
dc.subject Combinatorics en_US
dc.title On the parallel parameterized complexity of the graph isomorphism problem en_US
dc.type Preprint en_US


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


Browse

My Account