Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Computational complexity of reconstruction and isomorphism testing for
  designs and line graphs   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.

0
The categories of this paper are: hep-ph
28
The categories of this paper are: alg-geom
33
The categories of this paper are: plasm-ph
2
The categories of this paper are: math
7
The categories of this paper are: hep-th
30
The categories of this paper are: q-alg
23
The categories of this paper are: solv-int
8
The categories of this paper are: hep-ex
22
The categories of this paper are: chao-dyn
37
The categories of this paper are: supr-con
13
The categories of this paper are: quant-ph
26
The categories of this paper are: bayes-an
16
The categories of this paper are: stat
3
The categories of this paper are: physics
9
The categories of this paper are: nlin
27
The categories of this paper are: comp-gas