2023/03/14 by Levet, Michael, Rombach, Puck, Sieger, Nicholas
#05C60 #68Q19 #68Q25 #68R10 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.2303.07985
In this paper, we show that the (3k+4)-dimensional Weisfeiler--Leman algorithm can identify graphs of treewidth k in O(log n) rounds. This improves the result of Grohe & Verbitsky (ICALP 2006), who previously established the analogous result for (4k+3)-dimensional Weisfeiler--Leman. In light of the equivalence between Weisfeiler--Leman and the logic \textsfFO + \textsfC (Cai, Fürer, & Immerman, Combinatorica 1992), we obtain an improvement in the descriptive complexity for graphs of treewidth k. Precisely, if G is a graph of treewidth k, then there exists a (3k+5)-variable formula φ in \textsfFO + \textsfC with quantifier depth O(log n) that identifies G up to isomorphism.