The isomorphism problem for k-trees is complete for logspace

详细信息    查看全文

• 作者：V. Arvind ; Bireswar Das ; Johannes K?bler ; Sebastian Kuhnert
• 关键词：Graph isomorphism ; Graph canonization ; k-Trees ; Space complexity ; Logspace completeness
• 刊名：Information and Computation
• 出版年：2012
• 出版时间：August, 2012
• 年：2012
• 卷：217
• 期：Complete
• 页码：1-11
• 全文大小：295 K

文摘

We show that, for k constant, k-tree isomorphism can be decided in logarithmic space by giving an 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 , where n is the number of vertices, yielding the fastest known FPT algorithm for k-tree isomorphism.