Source author record

Johannes Köbler

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 Discrete Mathematics Logic in Computer Science

Catalog footprint

Research overview

8works

4topics

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.

preprint2015arXiv

Graph Isomorphism, Color Refinement, and Compactness

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 graph G amenable to color refinement if it succeeds in distinguishing G from any non-isomorphic graph H. Tinhofer (1991) explored a linear programming approach to Graph Isomorphism and defined compact graphs: A graph is compact if its fractional automorphisms polytope is integral. Tinhofer noted that isomorphism testing for compact graphs can be done quite efficiently by linear programming. However, the problem of characterizing and recognizing compact graphs in polynomial time remains an open question. Our results are summarized below: - We show that amenable graphs are recognizable in time O((n + m)logn), where n and m denote the number of vertices and the number of edges in the input graph. - We show that all amenable graphs are compact. - We study related combinatorial and algebraic graph properties introduced by Tinhofer and Godsil. The corresponding classes of graphs form a hierarchy and we prove that recognizing each of these graph classes is P-hard. In particular, this gives a first complexity lower bound for recognizing compact graphs.

preprint2013arXiv

Circular-arc hypergraphs: Rigidity via Connectedness

A circular-arc hypergraph $H$ is a hypergraph admitting an arc ordering, that is, a circular ordering of the vertex set $V(H)$ such that every hyperedge is an arc of consecutive vertices. An arc ordering is tight if, for any two hyperedges $A$ and $B$ such that $A$ is a nonempty subset of $B$ and $B$ is not equal to $V(H)$ , the corresponding arcs share a common endpoint. We give sufficient conditions for $H$ to have, up to reversing, a unique arc ordering and a unique tight arc ordering. These conditions are stated in terms of connectedness properties of $H$ . It is known that $G$ is a proper circular-arc graph exactly when its closed neighborhood hypergraph $N[G]$ admits a tight arc ordering. We explore connectedness properties of $N[G]$ and prove that, if $G$ is a connected, twin-free, proper circular-arc graph with non-bipartite complement, then $N[G]$ has, up to reversing, a unique arc ordering. If the complement of $G$ is bipartite and connected, then $N[G]$ has, up to reversing, two tight arc orderings. As a corollary, we notice that in both of the two cases $G$ has an essentially unique intersection representation. The last result also follows from the work by Deng, Hell, and Huang based on a theory of local tournaments.

preprint2013arXiv

Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space

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 equal. This implies that the recognition and the isomorphism problems for this class of graphs are solvable in logspace. For a broader class of concave-round graphs, that still possess (not necessarily proper) circular-arc models, we show that those can also be constructed canonically in logspace. As a building block for these results, we show how to compute canonical models of circular-arc hypergraphs in logspace, which are also known as matrices with the circular-ones property. Finally, we consider the search version of the Star System Problem that consists in reconstructing a graph from its closed neighborhood hypergraph. We solve it in logspace for the classes of proper circular-arc, concave-round, and co-convex graphs.

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.

Johannes Köbler

Research overview

Is this your work?

8 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

Graph Isomorphism, Color Refinement, and Compactness

Circular-arc hypergraphs: Rigidity via Connectedness

Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space

See the researcher in context

Building this map preview