Cover Image

Simple inexpensive vertex and edge invariants distinguishing dataset strongly regular graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Duda, Jarek
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges
by: Bok, Jan, et al.
Published: (2021)

Monitoring graph edges via shortest paths: computational complexity and approximation algorithms
by: Colli, Giordano
Published: (2025)

The complexity of strong conflict-free vertex-connection $k$-colorability
by: Hsieh, Sun-Yuan, et al.
Published: (2024)

Higher order PCA-like rotation-invariant features for detailed shape descriptors modulo rotation
by: Duda, Jarek
Published: (2026)

A (1.999999)-approximation ratio for vertex cover problem
by: Zohrehbandian, Majid
Published: (2024)

On optimal distinguishers for Planted Clique
by: Nagda, Ansh, et al.
Published: (2025)

Polynomial kernels for edge modification problems towards block and strictly chordal graphs
by: Dumas, Maël, et al.
Published: (2022)

Random regular graph states are complex at almost any depth
by: Ghosh, Soumik, et al.
Published: (2024)

Simple Circuit Extensions for XOR in PTIME
by: Carmosino, Marco, et al.
Published: (2025)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
by: Esmer, Barış Can, et al.
Published: (2022)

Simple general magnification of circuit lower bounds
by: Atserias, Albert, et al.
Published: (2025)

On the complexity of the Maker-Breaker happy vertex game
by: Hilaire, Mathieu, et al.
Published: (2026)

On the Complexity of Target Set Selection in Simple Geometric Networks
by: Dvořák, Michal, et al.
Published: (2023)

Algorithms and complexity for monitoring edge-geodetic sets in graphs
by: Foucaud, Florent, et al.
Published: (2024)

On the approximability of graph visibility problems
by: Bilò, Davide, et al.
Published: (2024)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
by: Kunisky, Dmitriy, et al.
Published: (2024)

Disjoint covering of bipartite graphs with $s$-clubs
by: Monti, Angelo, et al.
Published: (2024)

Reachability In Simple Neural Networks
by: Sälzer, Marco, et al.
Published: (2022)

Simple Norm Bounds for Polynomial Random Matrices via Decoupling
by: Tulsiani, Madhur, et al.
Published: (2024)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
by: Eagling-Vose, Tala, et al.
Published: (2025)

Between proper and square coloring of planar graphs, hardness and extremal graphs
by: Delépine, Thomas
Published: (2026)

Canonization of a random circulant graph by counting walks
by: Verbitsky, Oleg, et al.
Published: (2023)

Sensitivity and Hamming graphs
by: Asensio, Sara, et al.
Published: (2025)

Two Simple Proofs of Müller's Theorem
by: Epstein, Samuel
Published: (2024)

Proportionally dense subgraphs of maximum size in degree-constrained graphs
by: Baghirova, Narmina, et al.
Published: (2024)

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
by: Cai, Jin-Yi, et al.
Published: (2024)

Canonization of a random graph by two matrix-vector multiplications
by: Verbitsky, Oleg, et al.
Published: (2023)

Dichotomies for \#CSP on graphs that forbid a clique as a minor
by: Meng, Boning, et al.
Published: (2025)

The edge of the asymptotic spectrum of tensors
by: Alman, Josh, et al.
Published: (2026)

On the complexity of embedding in graph products
by: Biedl, Therese, et al.
Published: (2023)

Simple Linear Loops: Algebraic Invariants and Applications
by: Manssour, Rida Ait El, et al.
Published: (2024)

Determining unit distance graphs with coordinates in $\mathbb{Z}^2$ is NP-complete
by: Binnendyk, Eric
Published: (2025)

Precise estimates of invariant distances on strongly pseudoconvex domains
by: Kosiński, Łukasz, et al.
Published: (2023)

Non-real Poles and Irregularity of Distribution
by: Lowry-Duda, David
Published: (2019)

Simple approximation algorithms for Polyamorous Scheduling
by: Biktairov, Yuriy, et al.
Published: (2024)

The rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete
by: Nelson, Jon, et al.
Published: (2025)

The Borsuk number of a graph
by: Cáceres, José, et al.
Published: (2026)

$C_{2k+1}$-coloring of bounded-diameter graphs
by: Piecyk, Marta
Published: (2024)

Complexity of learning matchings and half graphs via edge queries
by: Mande, Nikhil S., et al.
Published: (2025)

A Simple Constructive Bound on Circuit Size Change Under Truth Table Perturbation
by: Krinkin, Kirill
Published: (2026)