tr-announce April 2009

tr-announce@lists.rwth-aachen.de

1 participants
3 discussions

2009-11: The Longest Path Problem is Polynomial on Interval Graphs

by Carsten Fuhs

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.

15 years, 5 months

2009-06: The Recognition of Tolerance and Bounded Tolerance Graphs is NP-complete

by Carsten Fuhs

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.

15 years, 6 months

2009-08: Satellites and Mirrors for Solving Independent Set on Sparse Graphs

by Carsten Fuhs

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.

15 years, 6 months

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

tr-announce April 2009