5 citations · 17 across the 10 of their papers we have counts for
11 papers · 1 filter
On the Expressibility of the Reconstructional Color Refinement
V. Arvind, Johannes Köbler, Oleg Verbitsky
One of the most basic facts related to the famous Ulam reconstruction conjecture is that the connectedness of a graph can be determined by the deck of its vertex-deleted subgraphs,…
On a Hierarchy of Spectral Invariants for Graphs
V. Arvind, Frank Fuhlbrück, Johannes Köbler +1
We consider a hierarchy of graph invariants that naturally extends the spectral invariants defined by Fürer (Lin. Alg. Appl. 2010) based on the angles formed by the set of standard…
Local WL Invariance and Hidden Shades of Regularity
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
The -dimensional Weisfeiler-Leman algorithm is a powerful tool in graph isomorphism testing. For an input graph , the algorithm determines a canonical coloring of -tuples…
On the Weisfeiler-Leman Dimension of Fractional Packing
V. Arvind, Frank Fuhlbrück, Johannes Köbler +1
The -dimensional Weisfeiler-Leman procedure (-WL), which colors -tuples of vertices in rounds based on the neighborhood structure in the graph, has proven to be immensely…
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
As it is well known, the isomorphism problem for vertex-colored graphs with color multiplicity at most 3 is solvable by the classical 2-dimensional Weisfeiler-Leman algorithm (2-WL…
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable
V. Arvind, Johannes Köbler, Sebastian Kuhnert +1
Lubiw showed that several variants of Graph Isomorphism are NP-complete, where the solutions are required to satisfy certain additional constraints [SICOMP 10, 1981]. One of these,…
The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs
V. Arvind, Frank Fuhlbrück, Johannes Köbler +2
In this paper we study the complexity of the following problems: Given a colored graph X=(V,E,c), compute a minimum cardinality set S of vertices such that no nontrivial automorphi…
Graph Isomorphism, Color Refinement, and Compactness
V. Arvind, Johannes Köbler, Gaurav Rattan +1
Color refinement is a classical technique used to show that two given graphs G and H are non-isomorphic; it is very efficient, although it does not succeed on all graphs. We call a…
On the Isomorphism Problem for Helly Circular-Arc Graphs
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
The isomorphism problem is known to be efficiently solvable for interval graphs, while for the larger class of circular-arc graphs its complexity status stays open. We consider the…
Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
We present a logspace algorithm that constructs a canonical intersection model for a given proper circular-arc graph, where `canonical' means that models of isomorphic graphs are e…
From Invariants to Canonization in Parallel
Johannes Koebler, Oleg Verbitsky
A function of a graph is called a complete graph invariant if the isomorphism of graphs and is equivalent to the equality . If, in addition, is a grap…