Fixed parameter tractable problems, transversals in hypergraphs and their connection to total domination in graphs

Anders Yeo

If a problem is NP-hard then there is no fast (ie polynomial) algorithm to solve the problem, unless P=NP (most researchers believe P=NP is false). Therefore not much effort has been put into finding good algorithms for NP-hard problems. However in real life situations we quite often need solutions for NP-hard problems, which was one of the main motivations for studying fixed parameter tractable (FPT) problems.

A problem is FPT if given a parameter k (often related to the solution) there is an algorithm of complexity O(f(k) n^c) for some function f(k) and some constant c. This means that for constant k the problem is polynomial. For example the problem "vertex cover" is solvable in time O(1.28^k n^c) for some constant c, where k is an upper bound on the size of the vertex cover. So if we want to find a vertex cover of size 30 it can be done in polynomial time (where the exponent does not depend on k=30).

We have FPT results for the linear arrangement problem, which will be explained in more detail at the talk.

A hypergraph, H, has a vertex set V(H) and an edge set E(H), where each edge is a subset of the vertices in V(H). Note that a graph is a special case of a hypergraph where all sets have size two. If all edges in a hypergraph have size exactly r, then it is a r-uniform hypergraph. A transversal, T, in a hypergraph is a set of vertices such that every edge in H contains a vertex from T. We are currently working on a FPT algorithm for finding a minimum transversal in a 3-uniform hypergraph. Such an algorithm could also be used to a find minimum feedback vertex sets in tournaments and to find total dominating sets in graphs with minimum degree three.

The second half of the talk will be spent on theoretical results on total dominating sets in graphs and transversals in hypergraphs. A total dominating set in a graph G is a set, S, such that every vertex in G has a neighbour in S. If G is a graph, then consider the hypergraph H with the same vertex set as G and where every hyperedge in H is an open neighbourhood in G (ie if x is a vertex in G, then the hyperedge containing all the neighbours of x will belong to H). It is not difficult to see that a transversal in H is also a total dominating set in G. We will give upper bounds on the size of a total dominating set in graphs with minimum degree d, for d=2,3,4. We will also give upper bounds under other conditions as well. Most of these results were obtained by using transversals in hypergraphs.

Finally, if time permits, I will mention the minimum cost homomorphisms problem, even though this is not related to the above.