Computer Science – Data Structures and Algorithms
Scientific paper
2009-09-23
Computer Science
Data Structures and Algorithms
Scientific paper
The lower and the upper irredundance numbers of a graph $G$, denoted $ir(G)$ and $IR(G)$ respectively, are conceptually linked to domination and independence numbers and have numerous relations to other graph parameters. It is a long-standing open question whether determining these numbers for a graph $G$ on $n$ vertices admits exact algorithms running in time less than the trivial $\Omega(2^n)$ enumeration barrier. We solve these open problems by devising parameterized algorithms for the dual of the natural parameterizations of the problems with running times faster than $O^*(4^{k})$. For example, we present an algorithm running in time $O^*(3.069^{k})$ for determining whether $IR(G)$ is at least $n-k$. Although the corresponding problem has been known to be in FPT by kernelization techniques, this paper offers the first parameterized algorithms with an exponential dependency on the parameter in the running time. Additionally, our work also appears to be the first example of a parameterized approach leading to a solution to a problem in exponential time algorithmics where the natural interpretation as an exact exponential-time algorithm fails.
Brankovic Ljiljana
Fernau Henning
Kneis Joachim
Peter Rossmanith Dieter Kratsch Alexander Langer Mathieu Liedloff Daniel Raible
No associations
LandOfFree
Breaking the 2^n-Barrier for Irredundance: A Parameterized Route to Solving Exact Puzzles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Breaking the 2^n-Barrier for Irredundance: A Parameterized Route to Solving Exact Puzzles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Breaking the 2^n-Barrier for Irredundance: A Parameterized Route to Solving Exact Puzzles will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-182085