Source author record

Frank Fuhlbrück

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity math.CO Logic in Computer Science

Catalog footprint

Research overview

5works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm

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). On the other hand, the prominent Cai-Fürer-Immerman construction shows that even the multidimensional version of the algorithm does not suffice for graphs with color multiplicity 4. We give an efficient decision procedure that, given a graph $G$ of color multiplicity 4, recognizes whether or not $G$ is identifiable by 2-WL, that is, whether or not 2-WL distinguishes $G$ from any non-isomorphic graph. In fact, we solve the much more general problem of recognizing whether or not a given coherent configuration of maximum fiber size 4 is separable. This extends our recognition algorithm to graphs of color multiplicity 4 with directed and colored edges. Our decision procedure is based on an explicit description of the class of graphs with color multiplicity 4 that are not identifiable by 2-WL. The Cai-Fürer-Immerman graphs of color multiplicity 4 distinctly appear here as a natural subclass, which demonstrates that the Cai-Fürer-Immerman construction is not ad hoc. Our classification reveals also other types of graphs that are hard for 2-WL. One of them arises from patterns known as $(n_3)$ -configurations in incidence geometry.

preprint2020arXiv

Local WL Invariance and Hidden Shades of Regularity

The $k$ -dimensional Weisfeiler-Leman algorithm is a powerful tool in graph isomorphism testing. For an input graph $G$ , the algorithm determines a canonical coloring of $s$ -tuples of vertices of $G$ for each $s$ between 1 and $k$ . We say that a numerical parameter of $s$ -tuples is $k$ -WL-invariant if it is determined by the tuple color. As an application of Dvořák's result on $k$ -WL-invariance of homomorphism counts, we spot some non-obvious regularity properties of strongly regular graphs and related graph families. For example, if $G$ is a strongly regular graph, then the number of paths of length 6 between vertices $x$ and $y$ in $G$ depends only on whether or not $x$ and $y$ are adjacent (and the length 6 is here optimal). Or, the number of cycles of length 7 passing through a vertex $x$ in $G$ is the same for every $x$ (where the length 7 is also optimal).

preprint2020arXiv

On the Weisfeiler-Leman Dimension of Fractional Packing

The $k$ -dimensional Weisfeiler-Leman procedure ( $k$ -WL), which colors $k$ -tuples of vertices in rounds based on the neighborhood structure in the graph, has proven to be immensely fruitful in the algorithmic study of Graph Isomorphism. More generally, it is of fundamental importance in understanding and exploiting symmetries in graphs in various settings. Two graphs are $k$ -WL-equivalent if the $k$ -dimensional Weisfeiler-Leman procedure produces the same final coloring on both graphs. 1-WL-equivalence is known as fractional isomorphism of graphs, and the $k$ -WL-equivalence relation becomes finer as $k$ increases. We investigate to what extent standard graph parameters are preserved by $k$ -WL-equivalence, focusing on fractional graph packing numbers. The integral packing numbers are typically NP-hard to compute, and we discuss applicability of $k$ -WL-invariance for estimating the integrality gap of the LP relaxation provided by their fractional counterparts.

preprint2020arXiv

The Weisfeiler-Leman Algorithm and Recognition of Graph Properties

The $k$ -dimensional Weisfeiler-Leman algorithm ( $k$ -WL) is a very useful combinatorial tool in graph isomorphism testing. We address the applicability of $k$ -WL to recognition of graph properties. Let $G$ be an input graph with $n$ vertices. We show that, if $n$ is prime, then vertex-transitivity of $G$ can be seen in a straightforward way from the output of 2-WL on $G$ and on the vertex-individualized copies of $G$ . However, if $n$ is divisible by 16, then $k$ -WL is unable to distinguish between vertex-transitive and non-vertex-transitive graphs with $n$ vertices as long as $k=o(\sqrt n)$ . Similar results are obtained for recognition of arc-transitivity.

preprint2016arXiv

The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs

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 automorphism of X fixes all vertices in S. A closely related problem is computing a minimum base S for a permutation group G on [n] given by generators, i.e., a minimum cardinality subset S of [n] such that no nontrivial permutation in G fixes all elements of S. Our focus is mainly on the parameterized complexity of these problems. We show that when k=|S| is treated as parameter, then both problems are MINI[1]-hard. For the dual problems, where k=n-|S| is the parameter, we give FPT algorithms. A notion closely related to fixing is called individualization. Individualization combined with the Weisfeiler-Leman procedure is a fundamental technique in algorithms for Graph Isomorphism. Motivated by the power of individualization, in the present paper we explore the complexity of individualization: what is the minimum number of vertices we need to individualize in a given graph such that color refinement "succeeds" on it. Here "succeeds" could have different interpretations, and we consider the following: It could mean the individualized graph becomes: (a) discrete, (b) amenable, (c) compact, or (d) refinable. In particular, we study the parameterized versions of these problems where the parameter is the number of vertices individualized. We show a dichotomy: For graphs with color classes of size at most 3 these problems can be solved in polynomial time (even in logspace), while starting from color class size 4 they become W[P]-hard.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Frank Fuhlbrück

Research overview

Is this your work?

5 publications

Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm

Local WL Invariance and Hidden Shades of Regularity

On the Weisfeiler-Leman Dimension of Fractional Packing

The Weisfeiler-Leman Algorithm and Recognition of Graph Properties

The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs

See the researcher in context

Building this map preview