Paper Info
Title
Reduction Techniques for Graph Isomorphism in the Context of Width Parameters.
Abstract
We study the parameterized complexity of the graph isomorphism problem when parameterized by width parameters related to tree decompositions. We apply the following technique to obtain fixed-parameter tractability for such parameters. We first compute an isomorphism invariant set of potential bags for a decomposition and then apply a restricted version of the Weisfeiler-Lehman algorithm to solve isomorphism. With this we show fixed-parameter tractability for several parameters and provide a unified explanation for various isomorphism results concerned with parameters related to tree decompositions. As a possibly first step towards intractability results for parameterized graph isomorphism we develop an fpt Turing-reduction from strong tree width to the a priori unrelated parameter maximum degree.
Year
DOI
Venue
2014
10.1007/978-3-319-08404-6_32
ALGORITHM THEORY - SWAT 2014
DocType
Volume
ISSN
Journal
8503
0302-9743
Citations 
PageRank 
References 
7
0.46
21
Authors
2
Name
Order
Citations
PageRank
Yota Otachi116137.16
Pascal Schweitzer221416.94