Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Sebastian Kuhnert:

TR16-157 | 13th October 2016
Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Toran

Parameterized Complexity of Small Weight Automorphisms

We consider the PermCode problem to decide, given a representation of a permutation group G and a parameter k, whether there is a non-trivial element of G with support at most k. This problem generalizes several problems in the literature. We introduce a new method that allows to reduce the ... more >>>

TR14-096 | 29th July 2014
Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Toran

Solving Linear Equations Parameterized by Hamming Weight

Given a system of linear equations $Ax=b$ over the binary field $\mathbb{F}_2$ and an integer $t\ge 1$, we study the following three algorithmic problems:
1. Does $Ax=b$ have a solution of weight at most $t$?
2. Does $Ax=b$ have a solution of weight exactly $t$?
3. Does $Ax=b$ have a ... more >>>

TR13-074 | 9th May 2013
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky

Helly Circular-Arc Graph Isomorphism is in Logspace

We present logspace algorithms for the canonical labeling problem and the representation problem of Helly circular-arc (HCA) graphs. The first step is a reduction to canonical labeling and representation of interval intersection matrices. In a second step, the Delta trees employed in McConnell's linear time representation algorithm for interval matrices ... more >>>

TR12-078 | 14th June 2012
Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev

Approximate Graph Isomorphism

We study optimization versions of Graph Isomorphism. Given two graphs $G_1,G_2$, we are interested in finding a bijection $\pi$ from $V(G_1)$ to $V(G_2)$ that maximizes the number of matches (edges mapped to edges or non-edges mapped to non-edges). We give an $n^{O(\log n)}$ time approximation scheme that for any constant ... more >>>

TR12-032 | 4th April 2012
Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe

Interval graph representation with given interval and intersection lengths

We consider the problem of finding interval representations of graphs that additionally respect given interval lengths and/or pairwise intersection lengths, which are represented as weight functions on the vertices and edges, respectively. Pe'er and Shamir proved that the problem is NP-complete if only the former are given [SIAM J. Discr. ... more >>>

TR10-043 | 5th March 2010
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky

Interval Graphs: Canonical Representation in Logspace

Revisions: 1

We present a logspace algorithm for computing a canonical interval representation and a canonical labeling of interval graphs. As a consequence, the isomorphism and automorphism problems for interval graphs are solvable in logspace.

more >>>

TR09-053 | 20th May 2009
Johannes Köbler, Sebastian Kuhnert

The Isomorphism Problem for k-Trees is Complete for Logspace

Revisions: 1

We show that k-tree isomorphism can be decided in logarithmic
space by giving a logspace canonical labeling algorithm. This improves
over the previous StUL upper bound and matches the lower bound. As a
consequence, the isomorphism, the automorphism, as well as the
canonization problem for k-trees ... more >>>

ISSN 1433-8092 | Imprint