The game of chess has inspired mathematicians for a long time. A well-known example for a chess problem is the so-called "Eight Queens Puzzle". In 1848 the german mathematician M. Bezzel asked for the number of possibilities to place eight queens on a chessboard, without two queens threatening each other. A related problem was covered in G. Berge’s famous book "The Theory of graphs" and is known as the "Five Queens Puzzle". This problem deals with the question of f inding the minimum number of queens needed to attack or occupy every square on a chess board. The general case of this problem is known as the DOMINATING SET Problem or DS Problem and belongs to the fundamental problems in graph theory. In 1990 S. T. Hedetniemi and R. C. Laskar (see [17]) noted that essential research on Domination in graphs started with the graph theory texts of D. König (1950), G. Berge (1958) and O. Ore (1962). From the mid-1970s onwards the number of domination papers grew quickly. The authors attribute this to mainly three factors. Two of them are the diversity of applications and the interest in finding polynomial time solutions to domination problems in special classes of graphs, which have motivated the approach worked out in this thesis . Adominating set for an undirected graph G = (VE) is a subset D of V, such that every vertex in V is connected to at least one member of D. Now we are looking for the domination number (G) which is the number of vertices in a smallest dominating set of G.

To classify the hardness of DOMINATING SET we consider the so-called decision version of DOMINATING SET, which means, given an integer k, to decide whether a dominating set of size k exists in a given graph. Due to the fact that V itself is always a dominating set in a graph G = (VE), we can reduce the decision problem to integers k V . It has been shown by M. Garey and D. Johnson in 1979 ([10]), that this decision version of DOMINATING SET is NP-complete. Under the hypothesis that P= NP, there is no efficient algorithm to solve this problem. The approach to the DS Problem worked out in this thesis is to formulate DOMINATING SET as a so-called copositive program, which is a certain optimization problem. The field of Mathematical Optimization is a very active area of research in modern mathematics. Generally speaking it is about finding a point in a set of feasible points which maximizes or minimizes an objective function. For the purpose of this thesis we mostly stick to conic programs, where the set of feasible points can be expressed with the help of convex cones and linear constraints. Examples for convex cones are the non-negative orthant or the cone of positive semidefinite matrices, common constraints are linear (in)equalities or integrality constraints. Copositive programs are certain conic programs, where the considered cone is the cone of copositive matrices. In Chapter 3 we develope two specific copositive formulations for DOMINATING SET.

Because solving copositive programs in general remains NP-hard, we approximate the resulting program with a series of simpler programs developed by P. Parrilo in [21]. This allows us to develope algorithms to approximate any copositive program, such as the formulations given in Chapter 3 within polynomial time. This means we provide two new approximation algorithms for DOMINATING SET. Furthermore, a simplification for semidefinite programs, developed by C. Bachoc, D. C. Gijswijt, A. Schrijver and F. Vallentin [1], can be applied to Parrilo’s hierarchy in certain instances of DOMINATING SET. This increases the performance of the algorithms significantly for large instances, providing a useful tool to find lower bounds for the domination number (G).