Revision #1 Authors: Noga Alon, Shai Gutner

Accepted on: 14th February 2009 00:00

Downloads: 1302

Keywords:

The domination number of a graph $G=(V,E)$ is the minimum size of

a dominating set $U \subseteq V$, which satisfies that every

vertex in $V \setminus U$ is adjacent to at least one vertex in

$U$. The notion of a problem kernel refers to a polynomial time

algorithm that achieves some provable reduction of the input size.

Given a graph $G$ whose domination number is $k$, the objective is

to design a polynomial time algorithm that produces a graph $G'$

whose size depends only on $k$, and also has domination number

equal to $k$.

Note that the graph $G'$ is constructed without knowing the value

of $k$.

Problem kernels can be used to obtain efficient approximation and

exact algorithms for the domination number, and are also useful in

practical settings.

In this paper, we present the first nontrivial result for the

general case of graphs with an excluded minor, as follows. For every

fixed $h$, given a graph $G$ with $n$ vertices that does not contain

$K_h$ as a topological minor, our $O(n^{3.5}+k^{O(1)})$ time

algorithm constructs a subgraph $G'$ of $G$, such that if the

domination number of $G$ is $k$, then the domination number of $G'$

is also $k$ and $G'$ has at most $k^c$ vertices, where $c$ is a

constant that depends only on $h$. This result is improved for

graphs that do not contain $K_{3,h}$ as a topological minor, using a

simpler algorithm that constructs a subgraph with at most $ck$

vertices, where $c$ is a constant that depends only on $h$.

Our results imply that there is a problem kernel of polynomial size

for graphs with an excluded minor and a linear kernel for graphs

that are $K_{3,h}$-minor-free. The only previous kernel results

known for the dominating set problem are the existence of a linear

kernel for the planar case as well as for graphs of bounded genus.

Using the polynomial kernel construction, we give an $O(n^{3.5} +

2^{O(\sqrt{k})})$ time algorithm for finding a dominating set of

size at most $k$ in an $H$-minor-free graph with $n$ vertices. This

improves the running time of the previously best known algorithm.

TR08-066 Authors: Noga Alon, Shai Gutner

Publication: 20th July 2008 16:09

Downloads: 2151

Keywords:

The domination number of a graph $G=(V,E)$ is the minimum size of

a dominating set $U \subseteq V$, which satisfies that every

vertex in $V \setminus U$ is adjacent to at least one vertex in

$U$. The notion of a problem kernel refers to a polynomial time

algorithm that achieves some provable reduction of the input size.

Given a graph $G$ whose domination number is $k$, the objective is

to design a polynomial time algorithm that produces a graph $G'$

whose size depends only on $k$, and also has domination number

equal to $k$.

Note that the graph $G'$ is constructed without knowing the value

of $k$.

Problem kernels can be used to obtain efficient approximation and

exact algorithms for the domination number, and are also useful in

practical settings.

In this paper, we present the first nontrivial result for the

general case of graphs with an excluded minor, as follows. For

every fixed $h$, given a graph $G$ that does not contain $K_h$ as

a topological minor, our polynomial time algorithm constructs a

subgraph $G'$ of $G$, such that if the domination number of $G$ is

$k$, then the domination number of $G'$ is also $k$ and $G'$ has

at most $k^c$ vertices, where $c$ is a constant that depends only

on $h$. This result is improved for graphs that do not contain

$K_{3,h}$ as a topological minor, using a simpler algorithm that

constructs a subgraph with at most $ck$ vertices, where $c$ is a

constant that depends only on $h$.

Our results imply that there is a problem kernel of polynomial

size for graphs with an excluded minor and a linear kernel for

graphs that are $K_{3,h}$-minor-free. The only previous kernel

results known for the dominating set problem are the existence of

a linear kernel for the planar case as well as for graphs of

bounded genus.