Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR09-093 | 15th April 2010 18:15

Colored Hypergraph Isomorphism is Fixed Parameter Tractable

RSS-Feed




Revision #1
Authors: Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda
Accepted on: 15th April 2010 18:15
Downloads: 3520
Keywords: 


Abstract:

We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism} which has running time 2^{O(b)}N^{O(1)}, where the parameter b is the maximum size of the color classes of the given hypergraphs and N is the input size. We also describe fpt algorithms for certain permutation group problems that are used as subroutines in our algorithm.



Changes to previous version:

By using a divide and conquer technique similar to Luks [Luk99] we improve the running time of our fpt algorithm for Colored Hypergraph Isomorphism from b!2^{O(b)}N^{O(1)} to 2^{O(b)}N^{O(1)}. Further we describe an N^{O(b)} time canonization algorithm for colored hypergraphs.


Paper:

TR09-093 | 8th October 2009 15:39

Colored Hypergraph Isomorphism is Fixed Parameter Tractable





TR09-093
Authors: Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda
Publication: 9th October 2009 20:59
Downloads: 3456
Keywords: 


Abstract:

We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism} which has running time b!2^{O(b)}N^{O(1)}, where the parameter b is the maximum size of the color classes of the given hypergraphs and N is the input size. We also describe fpt algorithms for certain permutation group problems that are used as subroutines in our algorithm.



ISSN 1433-8092 | Imprint