April 2009 - tr-announce - lists.rwth-aachen.de

2009-11: The Longest Path Problem is Polynomial on Interval Graphs
by Carsten Fuhs 16 Apr '09

16 Apr '09

The following technical report is available from http://aib.informatik.rwth-aachen.de: The Longest Path Problem is Polynomial on Interval Graphs Kyriaki Ioannidou, George B. Mertzios, Stavros D. Nikolopoulos AIB 2009-11 The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem are known only for small classes of graphs, while it is NP-hard on general graphs, as it is a generalization of the Hamiltonian path problem. Motivated by the work of Uehara and Uno in~\cite{Ueh04}, where they left the longest path problem open for the class of interval graphs, in this paper we show that the problem can be solved in polynomial time on interval graphs. The proposed algorithm runs in $O(n^4)$ time, where $n$ is the number of vertices of the input graph, and bases on a dynamic programming approach.

1 0

2009-06: The Recognition of Tolerance and Bounded Tolerance Graphs is NP-complete
by Carsten Fuhs 07 Apr '09

07 Apr '09

The following technical report is available from http://aib.informatik.rwth-aachen.de: The Recognition of Tolerance and Bounded Tolerance Graphs is NP-complete George B. Mertzios, Ignasi Sau, Shmuel Zaks AIB 2009-06 Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This class of graphs has been extensively studied, due to both its interesting structure and its numerous applications (in bioinformatics, constrained-based temporal reasoning, resource allocation, and scheduling problems, among others). Several efficient algorithms for optimization problems that are NP-hard in general graphs have been designed for tolerance graphs. In spite of this, the recognition of tolerance graphs -namely, the problem of deciding whether a given graph is a tolerance graph- as well as the recognition of their main subclass of bounded tolerance graphs, are probably the most fundamental open problems in this context (cf.~the book on tolerance graphs~\cite{GolTol04}) since their introduction almost three decades ago~\cite{GoMo82}. In this article we resolve this problem, by proving that both recognition problems are NP-complete, even in the case where the input graph is a trapezoid graph. For our reduction we extend the notion of an acyclic orientation of permutation and trapezoid graphs. Our main tool is a new algorithm (which uses an approach similar to~\cite{Cheah96}) that transforms a given trapezoid graph into a permutation graph, while preserving this new acyclic orientation property.

1 0

2009-08: Satellites and Mirrors for Solving Independent Set on Sparse Graphs
by Carsten Fuhs 02 Apr '09

02 Apr '09

The following technical report is available from http://aib.informatik.rwth-aachen.de: Satellites and Mirrors for Solving Independent Set on Sparse Graphs Joachim Kneis, Alexander Langer AIB 2009-08 We study the well-known Maximum Independent Set (MIS) problem and introduce the notion of satellites of a node. Branching on nodes with satellites is extremely simple. Nevertheless, satellites can be used to overcome a couple of hard cases in previous algorithms. Together with the notion of mirrors, introduced by Fomin, Grandoni, and Kratsch, they can be used to solve MIS in time bounded by O^*(1.1928^{m-n}), which is O^*(1.0922^n) for cubic graphs. This improves over previous results for sparse graphs.

1 0