Mitarbeiterseminar

Baumweite ist ein Beispiel für ein Komplexitätsmaß von Graphen. In diesem Vortrag wird das Komplexitätsmaß der Rangweite vorgestellt. Viele NP-vollständige Graphenprobleme sind FPT, wenn als Parameter k die Rangweite des Eingabegraphen gewählt wird. Anders als bei der Baumweite ist i.A. die Rangweite eines Subgraphen nicht kleiner gleich der Rangweite des Ausgangsgraphen. Es wird gezeigt, dass die Rangweite eines Graphen (bis auf eine Differenz von maximal 1) mit der Rangweite ihres Komplementgraphen übereinstimmt.

Es sei $C$ eine Graphklasse. Dann enthält die $MSO$-Theorie von $C$ alle $MSO$-Sätze, die für sämtliche Graphen aus $C$ gelten. Seese vermutete: Wenn die $MSO$-Theorie von $C$ entscheidbar ist, sind die Rangweiten der Graphen in $C$ beschränkt. Courcelle und Oum konnten davon folgende Abschwächung zeigen: Wenn die $C_2MSO$-Theorie von $C$ entscheidbar ist, dann haben ihre Graphen beschränkte Rangweite. Die Logik $C_2MSO$ besitzt zu den sprachlichen Möglichkeiten von $MSO$ ein einstelliges Relationssymbol Even, welches für jede Menge ausdrückt, ob diese geradzahlig viele Elemente besitzt.

The existential $k$-pebble game characterizes the expressive power of the existential-positive $k$-variable fragment of the infinitary logic L_{infty omega}. The winner of the existential k-pebble game on two given finite structures can easily be determined in time $O(n^{2k})$. We show that there is no $O(n^{(k-3)/12})$ time algorithm that decides which player can win the existential k-pebble game on two given structures. This lower bound is unconditional and does not rely on any unproven complexity theoretic assumptions.

Establishing strong $k$-consistency is a well-known heuristic for solving the constraint satisfaction problem (CSP). By the game characterization of Kolaitis and Vardi our result implies that there is no $O(n^{(k-3)/12})$ time algorithm that decides if strong $k$-consistency can be established for a given CSP-instance.

The question of whether there is a polynomial time algorithm deciding whether two graphs are isomorphic has been a one of the best known open problems in theoretical computer science for more than forty years. Indeed, the graph isomorphism problem is one of the very few natural problems in NP that is neither known to be in P nor known to be NP-complete. The question is still wide open, but a number of deep partial results giving polynomial time algorithms for specific classes of graphs are known. Many of them have been obtained through a group theoretic approach that dominated the research on the graph isomorphism problem since the early 1980s.

After an introductory survey on the graph isomorphism problem, in my talk I will focus on approaches to the graph isomorphism problem based on structural graph theory and connections between logical definability and certain combinatorial algorithms for the isomorphism problem. In particular, I will speak about two recent results: The first says that the Weisfeiler-Lehman algorithm (a simple combinatorial algorithm) can be used to decide isomorphism on graph classes with excluded minors in polynomial time. The second says that isomorphism can be decided in polynomial time on graph classes with excluded topological subgraphs.

*** This is the talk I'll give at SODA. No need to attend for those who'll be there. ***

The computational problem graph isomorphism asks whether there is an adjacency and non-adjacency preserving bijection between the vertices of two input graphs. The problem lies in the complexity class NP, but neither is the problem known to be NP-complete nor has a polynomial-time algorithm been developed. Its complexity status thus remains open.

I will talk about various aspects of the graph isomorphism problem: To this end I will describe the concepts underlying isomorphism algorithms that run fast in practice and explain how some of these concepts can be applied to obtain scalable graph kernels in the area of machine learning. I will also discuss the results that are known concerning the parameterized complexity of the isomorphism problem.

We study a family of graph clustering problems where each cluster has to satisfy a certain local requirement.

Formally, let $mu$ be a function on the subsets of vertices of a graph $G$. In the $(mu,p,q)$-PARTITION problem, the task is to find a partition of the vertices into clusters where each cluster $C$ satisfies the requirements that (1) at most $q$ edges leave $C$ and (2) $mu(C)≤ p$.

Our first result shows that if $mu$ is an arbitrary polynomial-time computable monotone function, then $(mu,p,q)$-PARTITION can be solved in time $n^{O(q)}$, i.e., it is polynomial-time solvable for every fixed $q$.

We study in detail three concrete functions $mu$ (number of nonedges in the cluster, maximum number of non-neighbours a vertex has in the cluster, the number of vertices in the cluster), which correspond to natural clustering problems. For these functions, we show that $(mu,p,q)$-PARTITION can be solved in time $2^{O(p)} n^{O(1)}$ and in time $2^{O(q)} n^{O(1)}$, i.e., the problem is fixed-parameter tractable parameterized by $p$ or by $q$.