Document

**Published in:** LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

We show that a canonical labeling of a random n-vertex graph can be obtained by assigning to each vertex x the triple (w₁(x),w₂(x),w₃(x)), where w_k(x) is the number of walks of length k starting from x. This takes time 𝒪(n²), where n² is the input size, by using just two matrix-vector multiplications. The linear-time canonization of a random graph is the classical result of Babai, Erdős, and Selkow. For this purpose they use the well-known combinatorial color refinement procedure, and we make a comparative analysis of the two algorithmic approaches.

Oleg Verbitsky and Maksim Zhukovskii. Canonization of a Random Graph by Two Matrix-Vector Multiplications. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 100:1-100:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{verbitsky_et_al:LIPIcs.ESA.2023.100, author = {Verbitsky, Oleg and Zhukovskii, Maksim}, title = {{Canonization of a Random Graph by Two Matrix-Vector Multiplications}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {100:1--100:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.100}, URN = {urn:nbn:de:0030-drops-187536}, doi = {10.4230/LIPIcs.ESA.2023.100}, annote = {Keywords: Graph Isomorphism, canonical labeling, random graphs, walk matrix, color refinement, linear time} }

Document

**Published in:** LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)

Given a graph F, let I(F) be the class of graphs containing F
as an induced subgraph. Let W[F] denote the minimum k such that
I(F) is definable in k-variable first-order logic. The recognition
problem of I(F), known as Induced Subgraph Isomorphism (for the pattern graph F), is solvable in time O(n^{W[F]}). Motivated by this fact, we are interested in determining or estimating the value of W[F]. Using Olariu's characterization of paw-free graphs, we show that I(K_3+e) is definable by a first-order sentence of quantifier depth 3, where K_3+e denotes the paw graph. This provides an example of a graph F with W[F] strictly less than the number of vertices in F.
On the other hand, we prove that W[F]=4 for all F on 4 vertices
except the paw graph and its complement. If F is a graph on t vertices, we prove a general lower bound W[F]>(1/2-o(1))t, where the function in the little-o notation approaches 0 as t increases. This bound holds true even for a related parameter W^*[F], which is
defined as the minimum k such that I(F) is definable in the k-variable
infinitary logic. We show that W^*[F] can be strictly less than W[F]. Specifically, W^*[P_4]=3 for P_4 being the path graph on 4 vertices.

Oleg Verbitsky and Maksim Zhukovskii. On the First-Order Complexity of Induced Subgraph Isomorphism. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{verbitsky_et_al:LIPIcs.CSL.2017.40, author = {Verbitsky, Oleg and Zhukovskii, Maksim}, title = {{On the First-Order Complexity of Induced Subgraph Isomorphism}}, booktitle = {26th EACSL Annual Conference on Computer Science Logic (CSL 2017)}, pages = {40:1--40:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-045-3}, ISSN = {1868-8969}, year = {2017}, volume = {82}, editor = {Goranko, Valentin and Dam, Mads}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.40}, URN = {urn:nbn:de:0030-drops-76841}, doi = {10.4230/LIPIcs.CSL.2017.40}, annote = {Keywords: the induced subgraph isomorphism problem, descriptive and computational complexity, finite-variable first-order logic, quantifier depth and variable w} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail