Descriptive complexity of controllable graphs

Aida Abiad; Anuj Dawar; Octavio Zapata

doi:10.1016/j.procs.2023.08.209

Descriptive complexity of controllable graphs

Aida Abiad, Anuj Dawar, Octavio Zapata (Corresponding author)

Algebraic Combinatorics

Research output: Contribution to journal › Conference article › peer-review

34 Downloads (Pure)

Abstract

Let G be a graph on n vertices with adjacency matrix A, and let 1 be the all-ones vector. We call G controllable if the set of vectors 1, A1,., A^n-11 spans the whole space Rⁿ. We characterize the isomorphism problem of controllable graphs in terms of other combinatorial, geometric and logical problems. We also describe a polynomial time algorithm for graph isomorphism that works for almost all graphs.

Original language	English
Pages (from-to)	20-27
Number of pages	8
Journal	Procedia Computer Science
Volume	223
DOIs	https://doi.org/10.1016/j.procs.2023.08.209
Publication status	Published - 2023
Event	12th Latin-American Algorithms, Graphs and Optimization Symposium, LAGOS 2023 - Huatulco, Mexico Duration: 18 Sept 2023 → 22 Sept 2023

Keywords

counting logics
descriptive complexity
finite model theory
isomorphism problems
spectral graph theory

Access to Document

10.1016/j.procs.2023.08.209

pdfFinal published version, 408 KBLicence: CC BY-NC-ND

Cite this

@article{bdbce69584864a39a13fba5feda1800f,

title = "Descriptive complexity of controllable graphs",

abstract = "Let G be a graph on n vertices with adjacency matrix A, and let 1 be the all-ones vector. We call G controllable if the set of vectors 1, A1,., An-11 spans the whole space Rn. We characterize the isomorphism problem of controllable graphs in terms of other combinatorial, geometric and logical problems. We also describe a polynomial time algorithm for graph isomorphism that works for almost all graphs.",

keywords = "counting logics, descriptive complexity, finite model theory, isomorphism problems, spectral graph theory",

author = "Aida Abiad and Anuj Dawar and Octavio Zapata",

year = "2023",

doi = "10.1016/j.procs.2023.08.209",

language = "English",

volume = "223",

pages = "20--27",

journal = "Procedia Computer Science",

issn = "1877-0509",

publisher = "Elsevier",

note = "12th Latin-American Algorithms, Graphs and Optimization Symposium, LAGOS 2023 ; Conference date: 18-09-2023 Through 22-09-2023",

}

TY - JOUR

T1 - Descriptive complexity of controllable graphs

AU - Abiad, Aida

AU - Dawar, Anuj

AU - Zapata, Octavio

PY - 2023

Y1 - 2023

N2 - Let G be a graph on n vertices with adjacency matrix A, and let 1 be the all-ones vector. We call G controllable if the set of vectors 1, A1,., An-11 spans the whole space Rn. We characterize the isomorphism problem of controllable graphs in terms of other combinatorial, geometric and logical problems. We also describe a polynomial time algorithm for graph isomorphism that works for almost all graphs.

AB - Let G be a graph on n vertices with adjacency matrix A, and let 1 be the all-ones vector. We call G controllable if the set of vectors 1, A1,., An-11 spans the whole space Rn. We characterize the isomorphism problem of controllable graphs in terms of other combinatorial, geometric and logical problems. We also describe a polynomial time algorithm for graph isomorphism that works for almost all graphs.

KW - counting logics

KW - descriptive complexity

KW - finite model theory

KW - isomorphism problems

KW - spectral graph theory

UR - http://www.scopus.com/inward/record.url?scp=85174421913&partnerID=8YFLogxK

U2 - 10.1016/j.procs.2023.08.209

DO - 10.1016/j.procs.2023.08.209

M3 - Conference article

AN - SCOPUS:85174421913

SN - 1877-0509

VL - 223

SP - 20

EP - 27

JO - Procedia Computer Science

JF - Procedia Computer Science

T2 - 12th Latin-American Algorithms, Graphs and Optimization Symposium, LAGOS 2023

Y2 - 18 September 2023 through 22 September 2023

ER -

Descriptive complexity of controllable graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this