Computer Science – Computational Complexity
Scientific paper
2010-06-30
Computer Science
Computational Complexity
12 pages; to appear in: "Journal of Combinatorial Theory, Series A"
Scientific paper
Graphs with high symmetry or regularity are the main source for experimentally hard instances of the notoriously difficult graph isomorphism problem. In this paper, we study the computational complexity of isomorphism testing for line graphs of $t$-$(v,k,\lambda)$ designs. For this class of highly regular graphs, we obtain a worst-case running time of $O(v^{\log v + O(1)})$ for bounded parameters $t,k,\lambda$. In a first step, our approach makes use of the Babai--Luks algorithm to compute canonical forms of $t$-designs. In a second step, we show that $t$-designs can be reconstructed from their line graphs in polynomial-time. The first is algebraic in nature, the second purely combinatorial. For both, profound structural knowledge in design theory is required. Our results extend earlier complexity results about isomorphism testing of graphs generated from Steiner triple systems and block designs.
No associations
LandOfFree
Computational complexity of reconstruction and isomorphism testing for designs and line graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Computational complexity of reconstruction and isomorphism testing for designs and line graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computational complexity of reconstruction and isomorphism testing for designs and line graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-154281