Combinatorics Seminar
When: Sunday, June 15, 10am
Where: Schreiber 309
Speaker: Shai Gutner, Tel Aviv University,
Title: The Dominating Set Problem on Graphs with an Excluded Minor
(PhD defence talk)
Abstract:
There is substantial literature dealing with fixed parameter
algorithms for the dominating set problem on various families of
graphs. In this work, we give a k^{O(dk)} n time algorithm for
finding a dominating set of size at most k in a d-degenerated
graph with n vertices. This proves that the dominating set problem is
fixed-parameter tractable for degenerated graphs. For graphs that
do not contain K_h as a topological minor, we give an improved
algorithm for the problem with running time (O(h))^{hk} n. For
graphs which are K_h-minor-free, the running time is further
reduced to (O(\log h))^{hk/2} n. Fixed-parameter tractable
algorithms that are linear in the number of vertices of the graph
were previously known only for planar graphs.
It has been proved that a parameterized problem is kernelizable
if and only if it is fixed-parameter tractable. 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 dominating number is k, the objective is to
find a polynomial time algorithm that produces a graph G' whose size
depends only on k, and also has dominating number equal to k. We will
present new results concerning kernels for the case of graphs with
an excluded minor.
This work forms part of a Ph.D. thesis written under
the supervision of Prof. N. Alon and Prof. Y. Azar.