This thesis presents and develops a theory of self-reduction. This process is used to map instances of combinatorial optimisation problems onto smaller, more easily solvable instances in such a way that a solution of the former can be readily re-constructed, without loss of information or quality, from a solution of the latter. Self-reduction rules are surveyed for the Graph Colouring Problem, the Maximum Clique Problem, the Steiner Problem in Graphs, the Bin Packing Problem and the Set Covering Problem. This thesis introduces the problem of determining the maximum sequence of self-reductions on a given structure, and shows how the theory of confluence can be adapted from term re-writing to solve this problem by identifying rule sets for which all maximal reduction sequences are equivalent. Such confluence results are given for a number of reduction rules on problems on discrete systems. In contrast, NP-hardness results are also presented for some reduction rules. A probabilistic analysis of self-reductions on graphs is performed, showing that the expected number of self-reductions on a graph tends to zero as the order of the graph tends to infinity. An empirical study is performed comparing the performance of self-reduction, graph decomposition and direct methods of solving the Graph Colouring and Set Covering Problems. The results show that self-reduction is a potentially valuable, but sometimes erratic, method of finding exact solutions to combinatorial problems.

[pt] Nesta tese faz-se uma extensa revisão bibliográfica sobre o problema de Steiner na métrica retilínea, destacando-se a aplicação do mesmo no projeto de VLSI. São descritas em detalhes várias heurísticas existentes na literatura para as quais estudam-se a complexidade computacional e a qualidade das soluções obtidas. Além disso, são estabelecidos novos resultados relativos ao comportamento de pior caso destas heurísticas. Propõe-se, ainda, duas novas heurísticas para o problema de Steiner na métrica retilínea para as quais são estudadas a complexidade computacional e a qualidade da solução, inclusive com a análise do pior caso. Uma grande quantidade de testes computacionais permitiu a realização de uma comparação do desempenho das diversas heurísticas implementadas, concluindo-se que uma das novas heurísticas propostas fornece, em média, soluções melhores do que aquelas fornecidas pelas demais heurísticas conhecidas na literatura. / [en] In this dissertation we present a survey about the Steiner problem in the rectilinear metric, illustrating its applications to the VLSI desing. A large number of heurístics already described in literature is studied in details. Moreover, we study the complexity of these heuristics and the quality of their solutions. New results concerning their worst case behavior are stated. We also propose two new heuristics for thew Steiner problem in the rectilinear metric, for which we study the complexity and the quality of the solutions, including the worst case analysis. A large nember of computational experiments was conducted and allowed the comparison of the performances of the heuristics implemented. We conclude from these experiments that, in the average, the solutions obtained by one of the new heuristics are better than the solutions obtained by those alreafy available in the literature.

Title: Parameterized Complexity Author: Ondřej Suchý Department: Department of Applied Mathematics Advisor: Prof. RNDr. Jan Kratochvíl, CSc. Advisor's e-mail address: honza@kam.mff.cuni.cz Abstract: This thesis deals with the parameterized complexity of NP-hard graph problems. We explore the complexity of the problems in various scenarios, with respect to miscellaneous parameters and their combina- tions. Our aim is rather to classify in this multivariate manner whether the particular parameters make the problem fixed-parameter tractable or intractable than to present the algorithm achieving the best running time. In the questions we study typically the first-choice parameter is unsuccessful, in which case we propose to use less standard ones. The first family of problems investigated provides a common general- ization of many well known and studied domination and independence problems. Here we suggest using the dual parameterization and show that, in contrast to the standard solution-size, it can confine the in- evitable combinatorial explosion. Further studied problems are ana- logues of the Steiner problem in directed graphs. Here the parameter- ization by the number of terminals to be connected seems to be previ- ously unexplored in the directed setting. Unfortunately, the problems are shown to be...

The subject of this monograph can be described as the local properties of geometric Steiner minimal trees in finite-dimensional normed spaces. A Steiner minimal tree of a finite set of points is a shortest connected set interconnecting the points. For a quick introduction to this topic and an overview of all the results presented in this work, see Chapter 1. The relevant mathematical background knowledge needed to understand the results and their proofs are collected in Chapter 2. In Chapter 3 we introduce the Fermat-Torricelli problem, which is that of finding a point that minimizes the sum of distances to a finite set of given points. We only develop that part of the theory of Fermat-Torricelli points that is needed in later chapters. Steiner minimal trees in finite-dimensional normed spaces are introduced in Chapter 4, where the local Steiner problem is given an exact formulation. In Chapter 5 we solve the local Steiner problem for all two-dimensional spaces, and generalize this solution to a certain class of higher-dimensional spaces (CL spaces). The twodimensional solution is then applied to many specific norms in Chapter 6. Chapter 7 contains an abstract solution valid in any dimension, based on the subdifferential calculus. This solution is applied to two specific high-dimensional spaces in Chapter 8. In Chapter 9 we introduce an alternative approach to bounding the maximum degree of Steiner minimal trees from above, based on the illumination problem from combinatorial convexity. Finally, in Chapter 10 we consider the related k-Steiner minimal trees, which are shortest Steiner trees in which the number of Steiner points is restricted to be at most k. / Das Thema dieser Habilitationsschrift kann als die lokalen Eigenschaften der geometrischen minimalen Steiner-Bäume in endlich-dimensionalen normierten Räumen beschrieben werden. Ein minimaler Steiner-Baum einer endlichen Punktmenge ist eine kürzeste zusammenhängende Menge die die Punktmenge verbindet. Kapitel 1 enthält eine kurze Einführung zu diesem Thema und einen Überblick über alle Ergebnisse dieser Arbeit. Die entsprechenden mathematischen Vorkenntnisse mit ihren Beweisen, die erforderlich sind die Ergebnisse zu verstehen, erscheinen in Kapitel 2. In Kapitel 3 führen wir das Fermat-Torricelli-Problem ein, das heißt, die Suche nach einem Punkt, der die Summe der Entfernungen der Punkte einer endlichen Punktmenge minimiert. Wir entwickeln nur den Teil der Theorie der Fermat-Torricelli-Punkte, der in späteren Kapiteln benötigt wird. Minimale Steiner-Bäume in endlich-dimensionalen normierten Räumen werden in Kapitel 4 eingeführt, und eine exakte Formulierung wird für das lokale Steiner-Problem gegeben. In Kapitel 5 lösen wir das lokale Steiner-Problem für alle zwei-dimensionalen Räume, und diese Lösung wird für eine bestimmte Klasse von höher-dimensionalen Räumen (den sog. CL-Räumen) verallgemeinert. Die zweidimensionale Lösung wird dann auf mehrere bestimmte Normen in Kapitel 6 angewandt. Kapitel 7 enthält eine abstrakte Lösung die in jeder Dimension gilt, die auf der Analysis von Subdifferentialen basiert. Diese Lösung wird auf zwei bestimmte höher-dimensionale Räume in Kapitel 8 angewandt. In Kapitel 9 führen wir einen alternativen Ansatz zur oberen Schranke des maximalen Grads eines minimalen Steiner-Baums ein, der auf dem Beleuchtungsproblem der kombinatorischen Konvexität basiert ist. Schließlich betrachten wir in Kapitel 10 die verwandten minimalen k-Steiner-Bäume. Diese sind die kürzesten Steiner-Bäume, in denen die Anzahl der Steiner-Punkte auf höchstens k beschränkt wird.

Le travail que nous développons dans le cadre de cette thèse s'articule autour des problèmes de recherche de structure de recouvrement de graphes sous contrainte sur le degré des sommets. Comme l'arbre de recouvrement couvre les sommets d'un graphe connexe avec un minimum de liens, il est généralement proposé comme solution à ce type de problèmes. Cependant, pour certaines applications telles que le routage dans les réseaux optiques, les solutions ne sont pas nécessairement des sous-graphes. Nous supposons dans cette thèse que la contrainte sur le degré est due à une capacité limitée instantanée des sommets et que la seule exigence sur le recouvrement est sa connexité. Dans ce cas, la solution peut être différente d'un arbre. Nous reformulons ces problèmes de recouvrement en nous appuyant sur une extension du concept d'arbre appelée hiérarchie de recouvrement. Notre objectif principal est de démontrer son intérêt vis-à-vis de l'arbre en termes de faisabilité et de coût du recouvrement. Nous considérons deux types de contraintes sur le degré : des bornes sur le degré des sommets ou une borne sur le nombre de sommets de branchement et cherchons dans les deux cas un recouvrement de coût minimum. Nous illustrons aussi l'applicabilité des hiérarchies en étudiant un problème prenant davantage en compte la réalité du routage optique. Pour ces différents problèmes NP-difficiles, nous montrons, tant sur le coût des solutions optimales que sur la garantie de performance des solutions approchées, l'intérêt des hiérarchies de recouvrement. Ce constat se voit conforté par des expérimentations sur des graphes aléatoires. / The work conducted in this thesis is focused on the minimum spanning problems in graphs under constraints on the vertex degrees. As the spanning tree covers the vertices of a connected graph with a minimum number of links, it is generally proposed as a solution for this kind of problems. However, for some applications such as the routing in optical networks, the solution is not necessarily a sub-graph. In this thesis, we assume that the degree constraints are due to a limited instantaneous capacity of the vertices and that the only pertinent requirement on the spanning structure is its connectivity. In that case, the solution may be different from a tree. We propose the reformulation of this kind of spanning problems. To find the optimal coverage of the vertices, an extension of the tree concept called hierarchy is proposed. Our main purpose is to show its interest regarding the tree in term of feasibility and costs of the coverage. Thus, we take into account two types of degree constraints: either an upper bound on the degree of vertices and an upper bound on the number of branching vertices. We search a minimum cost spanning hierarchy in both cases. Besides, we also illustrate the applicability of hierarchies by studying a problem that takes more into account the reality of the optical routing. For all those NP-hard problems, we show the interest of the spanning hierarchy for both costs of optimal solutions and performance guarantee of approximate solutions. These results are confirmed by several experimentations on random graphs.