2 Search Results for "Zhukovskii, Maksim"

Document
DOI: 10.4230/LIPIcs.ESA.2023.100
Canonization of a Random Graph by Two Matrix-Vector Multiplications

Authors: Oleg Verbitsky and Maksim Zhukovskii

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.CSL.2017.40
On the First-Order Complexity of Induced Subgraph Isomorphism

Authors: Oleg Verbitsky and Maksim Zhukovskii

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

Abstract
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.
Cite as

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}
}
  • Refine by Author
  • 2 Verbitsky, Oleg
  • 2 Zhukovskii, Maksim

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Random graphs

  • Refine by Keyword
  • 1 Graph Isomorphism
  • 1 canonical labeling
  • 1 color refinement
  • 1 descriptive and computational complexity
  • 1 finite-variable first-order logic
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2017
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact