A graph is said to be 2-edge-connected if it remains connected after the deletion of any single edge. Given an unweighted bridgeless graph G with n vertices, the minimum size 2-edge-connected spanning subgraph problem (2EC) is that of finding a 2-edge-connected spanning subgraph of G with the minimum number of edges. This problem has important applications in the design of survivable networks. However, because the problem is NP-hard, it is unlikely that efficient methods exist for solving it. Thus efficient methods that find solutions that are provably close to optimal are sought. In this thesis, an approximation algorithm is presented for 2EC on bridgeless cubic graphs which guarantees to be within 5/4 of the optimal solution value, improving on the previous best proven approximation guarantee of 5/4+ε for this problem. We also focus on the linear programming (LP) relaxation of 2EC, which provides important lower bounds for 2EC in useful solution techniques like branch and bound. The “goodness” of this lower bound is measured by the integrality gap of the LP relaxation for 2EC, denoted by α2EC. Through a computational study, we find the exact value of α2EC for graphs with small n. Moreover, a significant improvement is found for the lower bound on the value of α2EC for bridgeless subcubic graphs, which improves the known best lower bound on α2EC from 9/8 to 8/7.

A graph is said to be 2-edge-connected if it remains connected after the deletion of any single edge. Given an unweighted bridgeless graph G with n vertices, the minimum size 2-edge-connected spanning subgraph problem (2EC) is that of finding a 2-edge-connected spanning subgraph of G with the minimum number of edges. This problem has important applications in the design of survivable networks. However, because the problem is NP-hard, it is unlikely that efficient methods exist for solving it. Thus efficient methods that find solutions that are provably close to optimal are sought. In this thesis, an approximation algorithm is presented for 2EC on bridgeless cubic graphs which guarantees to be within 5/4 of the optimal solution value, improving on the previous best proven approximation guarantee of 5/4+ε for this problem. We also focus on the linear programming (LP) relaxation of 2EC, which provides important lower bounds for 2EC in useful solution techniques like branch and bound. The “goodness” of this lower bound is measured by the integrality gap of the LP relaxation for 2EC, denoted by α2EC. Through a computational study, we find the exact value of α2EC for graphs with small n. Moreover, a significant improvement is found for the lower bound on the value of α2EC for bridgeless subcubic graphs, which improves the known best lower bound on α2EC from 9/8 to 8/7.

Given a complete graph K_n = (V,E) with non-negative edge costs c ∈ R^E, the problem multi-2EC_cost is that of finding a 2-edge connected spanning multi-subgraph of K_n with minimum cost. It is believed that there are no efficient ways to solve the problem exactly, as it is NP-hard. Methods such as approximation algorithms, which rely on lower bounds like the linear programming relaxation multi-2EC^LP of multi-2EC , thus become vital cost cost to obtain solutions guaranteed to be close to the optimal in a fast manner. In this thesis, we focus on the integrality gap αmulti-2EC of multi-2EC^LP , which is a measure of the quality of multi-2EC^LP as a lower bound. Although we currently only know cost that 6/5 ≤ αmulti-2EC_cost ≤ 3 , the integrality gap for multi-2EC_cost has been conjectured to be 6/5. We explore the idea of using the structure of solutions for αmulti-2EC_cost and the concept of convex combination to obtain improved bounds for αmulti-2EC_cost. We focus our efforts on a family J of half-integer solutions that appear to give the largest integrality gap for multi-2EC_cost. We successfully show that the conjecture αmulti-2EC_cost = 6/5 is true for any cost functions optimized by some x∗ ∈ J. We also study the related problem 2EC_size, which consists of finding the minimum size 2-edge connected spanning subgraph of a 2-edge connected graph. The problem is NP-hard even at its simplest, when restricted to cubic 3-edge connected graphs. We study that case in the hope of finding a more general method, and we show that every 3-edge connected cubic graph G = (V ′, E′), with n = |V ′| allows a 2EC_size solution for G of size at most 7n/6 This improves upon Boyd, Iwata and Takazawa’s guarantee of 6n/5 and extend Takazawa’s 7n/6 guarantee for bipartite cubic 3-edge connected graphs to all cubic 3-edge connected graphs.

In this thesis we focus on two NP-hard and intensively studied problems: The travelling salesman problem (TSP), which aims to find a minimum cost tour that visits every node exactly once in a complete weighted graph, and the 2-edge-connected spanning subgraph problem (2ECSS), which aims to find a minimum size 2-edge-connected spanning subgraph in a given graph. TSP and 2ECSS have many real world applications. However, both problems are NP-hard which means it is unlikely that polynomial time algorithms exist to solve them, so methods that return close to optimal solutions are sought. In this thesis we mainly focus on k-approximation algorithms for the two problems, which efficiently return a solution within k times of the optimal solution. For a special case of TSP called graph TSP, using ideas from Momke and Svensson, we present a 25/18-approximation algorithm for a special class of graphs using circulations and T-joins, which improves the previous known best bound of 7/5 for such graphs. Moreover, if the graph does not contain special nodes, our algorithm ensures the ratio of 4/3. For 2ECSS, given any k-edge-connected graph G=(V,E), |V|=n, |E|=m, we present an approximation algorithm that gives a 2-edge-connected spanning subgraph with the number of edges at most n+(m-n)/(k-1)-(k-2)/(k-1) with a novel use of circulations, which improves both the approximation ratio and the simplicity of the proof compared to a result by Huh in 2004.

In this thesis we focus on two NP-hard and intensively studied problems: The travelling salesman problem (TSP), which aims to find a minimum cost tour that visits every node exactly once in a complete weighted graph, and the 2-edge-connected spanning subgraph problem (2ECSS), which aims to find a minimum size 2-edge-connected spanning subgraph in a given graph. TSP and 2ECSS have many real world applications. However, both problems are NP-hard which means it is unlikely that polynomial time algorithms exist to solve them, so methods that return close to optimal solutions are sought. In this thesis we mainly focus on k-approximation algorithms for the two problems, which efficiently return a solution within k times of the optimal solution. For a special case of TSP called graph TSP, using ideas from Momke and Svensson, we present a 25/18-approximation algorithm for a special class of graphs using circulations and T-joins, which improves the previous known best bound of 7/5 for such graphs. Moreover, if the graph does not contain special nodes, our algorithm ensures the ratio of 4/3. For 2ECSS, given any k-edge-connected graph G=(V,E), |V|=n, |E|=m, we present an approximation algorithm that gives a 2-edge-connected spanning subgraph with the number of edges at most n+(m-n)/(k-1)-(k-2)/(k-1) with a novel use of circulations, which improves both the approximation ratio and the simplicity of the proof compared to a result by Huh in 2004.

Uma decomposição de um grafo G é um conjunto D = {H_1,... , H_k } de subgrafos de G dois-a-dois aresta-disjuntos que cobre o conjunto das arestas de G. Se H_i é isomorfo a um grafo fixo H, para 1<=i<=k, então dizemos que D é uma H-decomposição de G. Neste trabalho, estudamos o caso em que H é um caminho de comprimento fixo. Para isso, primeiramente decompomos o grafo dado em trilhas, e depois fazemos uso de um lema de desemaranhamento, que nos permite transformar essa decomposição em trilhas numa decomposição somente em caminhos. Com isso, obtemos resultados para três conjecturas sobre H-decomposição de grafos no caso em que H=P_\\ell é o caminho de comprimento \\ell. Dois desses resultados resolvem versões fracas das Conjecturas de Kouider e Lonc (1999) e de Favaron, Genest e Kouider (2010), ambas para grafos regulares. Provamos que, para todo inteiro positivo \\ell, (i) existe um inteiro positivo m_0 tal que se G é um grafo 2m\\ell-regular com m>=m_0, então G admite uma P_\\ell-decomposição; (ii) se \\ell é ímpar, existe um inteiro positivo m_0 tal que se G é um grafo m\\ell-regular com m>=m_0, e G contém um m-fator, então G admite uma P_\\ell-decomposição. O terceiro resultado diz respeito a grafos altamente aresta- conexos: existe um inteiro positivo k_\\ell tal que se G é um grafo k_\\ell-aresta-conexo cujo número de arestas é divisível por \\ell, então G admite uma P_\\ell-decomposição. Esse resultado prova que a Decomposition Conjecture de Barát e Thomassen (2006), formulada para árvores, é verdadeira para caminhos. / A decomposition of a graph G is a set D = {H_1,...,H_k} of pairwise edge-disjoint subgraphs of G that cover the set of edges of G. If H_i is isomorphic to a fixed graph H, for 1<=i<=k, then we say that D is an H-decomposition of G. In this work, we study the case where H is a path of fixed length. For that, we first decompose the given graph into trails, and then we use a disentangling lemma, that allows us to transform this decomposition into one consisting only of paths. With this approach, we tackle three conjectures on H-decomposition of graphs and obtain results for the case H=P_\\ell is the path of length \\ell. Two of these results solve weakenings of a conjecture of Kouider and Lonc (1999) and a conjecture of Favaron, Genest and Kouider (2010), both for regular graphs. We prove that, for every positive integer \\ell, (i) there is a positive integer m_0 such that, if G is a 2m\\ell-regular graph with m>=m_0, then G admits a P_\\ell-decomposition; (ii) if \\ell is odd, there is a positive integer m_0 such that, if G is an m\\ell-regular graph with m>=m_0 containing an m-factor, then G admits a P_\\ell-decomposition. The third result concerns highly edge-connected graphs: there is a positive integer k_\\ell such that if G is a k_\\ell-edge-connected graph whose number of edges is divisible by \\ell, then G admits a P_\\ell-decomposition. This result verifies for paths the Decomposition Conjecture of Barát and Thomassen (2006), on trees.

In this dissertation, we examine specific network connectivity problems, and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite its many practical uses, this problem has not been previously studied. We present the first constant factor approximation algorithm for VCC, and provide an upper bound on the integrality gap of its linear programming relaxation. We also introduce a new, useful, extension of the minimum spanning tree problem, called the Extended Minimum Spanning Tree Problem (EMST), that is based on a special case of VCC; and provide both a polynomial-time algorithm and a complete linear description for it. Furthermore, we show how to generalize this new problem to handle numerous disjoint vital cores, providing the first complete linear description of, and polynomial-time algorithm for, the generalized problem. We examine the Survivable Network Design Problem (SNDP) with multiple copies of edges allowed in the solution (multi-SNDP), and present a new approximation algorithm for which the approximation guarantee is better than that of the current best known for certain cases of multi-SNDP. With our method, we also obtain improved bounds on the integrality gap of the linear programming relaxation of the problem. Furthermore, we show the application of these results to variations of SNDP. We investigate cases where the optimal values of multi-SNDP and SNDP are equal; and we present an improvement on the previously best known integrality gap bound and approximation guarantee for the special case of SNDP with metric costs and low vertex connectivity requirements, as well as for the similar special case of the Vertex Connected Survivable Network Design Problem (VC-SNDP). The quality of the results that one can obtain for a given network design problem often depends on its integer linear programming formulation, and, in particular, on its linear programming relaxation. In this connection, we investigate formulations for the Steiner Tree Problem (ST). We propose two new formulations for ST, and investigate their strength in terms of their associated integrality gaps.

In this dissertation, we examine specific network connectivity problems, and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite its many practical uses, this problem has not been previously studied. We present the first constant factor approximation algorithm for VCC, and provide an upper bound on the integrality gap of its linear programming relaxation. We also introduce a new, useful, extension of the minimum spanning tree problem, called the Extended Minimum Spanning Tree Problem (EMST), that is based on a special case of VCC; and provide both a polynomial-time algorithm and a complete linear description for it. Furthermore, we show how to generalize this new problem to handle numerous disjoint vital cores, providing the first complete linear description of, and polynomial-time algorithm for, the generalized problem. We examine the Survivable Network Design Problem (SNDP) with multiple copies of edges allowed in the solution (multi-SNDP), and present a new approximation algorithm for which the approximation guarantee is better than that of the current best known for certain cases of multi-SNDP. With our method, we also obtain improved bounds on the integrality gap of the linear programming relaxation of the problem. Furthermore, we show the application of these results to variations of SNDP. We investigate cases where the optimal values of multi-SNDP and SNDP are equal; and we present an improvement on the previously best known integrality gap bound and approximation guarantee for the special case of SNDP with metric costs and low vertex connectivity requirements, as well as for the similar special case of the Vertex Connected Survivable Network Design Problem (VC-SNDP). The quality of the results that one can obtain for a given network design problem often depends on its integer linear programming formulation, and, in particular, on its linear programming relaxation. In this connection, we investigate formulations for the Steiner Tree Problem (ST). We propose two new formulations for ST, and investigate their strength in terms of their associated integrality gaps.

In this dissertation, we examine specific network connectivity problems, and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite its many practical uses, this problem has not been previously studied. We present the first constant factor approximation algorithm for VCC, and provide an upper bound on the integrality gap of its linear programming relaxation. We also introduce a new, useful, extension of the minimum spanning tree problem, called the Extended Minimum Spanning Tree Problem (EMST), that is based on a special case of VCC; and provide both a polynomial-time algorithm and a complete linear description for it. Furthermore, we show how to generalize this new problem to handle numerous disjoint vital cores, providing the first complete linear description of, and polynomial-time algorithm for, the generalized problem. We examine the Survivable Network Design Problem (SNDP) with multiple copies of edges allowed in the solution (multi-SNDP), and present a new approximation algorithm for which the approximation guarantee is better than that of the current best known for certain cases of multi-SNDP. With our method, we also obtain improved bounds on the integrality gap of the linear programming relaxation of the problem. Furthermore, we show the application of these results to variations of SNDP. We investigate cases where the optimal values of multi-SNDP and SNDP are equal; and we present an improvement on the previously best known integrality gap bound and approximation guarantee for the special case of SNDP with metric costs and low vertex connectivity requirements, as well as for the similar special case of the Vertex Connected Survivable Network Design Problem (VC-SNDP). The quality of the results that one can obtain for a given network design problem often depends on its integer linear programming formulation, and, in particular, on its linear programming relaxation. In this connection, we investigate formulations for the Steiner Tree Problem (ST). We propose two new formulations for ST, and investigate their strength in terms of their associated integrality gaps.

Uma decomposição de um grafo G é um conjunto D = {H_1,... , H_k } de subgrafos de G dois-a-dois aresta-disjuntos que cobre o conjunto das arestas de G. Se H_i é isomorfo a um grafo fixo H, para 1<=i<=k, então dizemos que D é uma H-decomposição de G. Neste trabalho, estudamos o caso em que H é um caminho de comprimento fixo. Para isso, primeiramente decompomos o grafo dado em trilhas, e depois fazemos uso de um lema de desemaranhamento, que nos permite transformar essa decomposição em trilhas numa decomposição somente em caminhos. Com isso, obtemos resultados para três conjecturas sobre H-decomposição de grafos no caso em que H=P_\\ell é o caminho de comprimento \\ell. Dois desses resultados resolvem versões fracas das Conjecturas de Kouider e Lonc (1999) e de Favaron, Genest e Kouider (2010), ambas para grafos regulares. Provamos que, para todo inteiro positivo \\ell, (i) existe um inteiro positivo m_0 tal que se G é um grafo 2m\\ell-regular com m>=m_0, então G admite uma P_\\ell-decomposição; (ii) se \\ell é ímpar, existe um inteiro positivo m_0 tal que se G é um grafo m\\ell-regular com m>=m_0, e G contém um m-fator, então G admite uma P_\\ell-decomposição. O terceiro resultado diz respeito a grafos altamente aresta- conexos: existe um inteiro positivo k_\\ell tal que se G é um grafo k_\\ell-aresta-conexo cujo número de arestas é divisível por \\ell, então G admite uma P_\\ell-decomposição. Esse resultado prova que a Decomposition Conjecture de Barát e Thomassen (2006), formulada para árvores, é verdadeira para caminhos. / A decomposition of a graph G is a set D = {H_1,...,H_k} of pairwise edge-disjoint subgraphs of G that cover the set of edges of G. If H_i is isomorphic to a fixed graph H, for 1<=i<=k, then we say that D is an H-decomposition of G. In this work, we study the case where H is a path of fixed length. For that, we first decompose the given graph into trails, and then we use a disentangling lemma, that allows us to transform this decomposition into one consisting only of paths. With this approach, we tackle three conjectures on H-decomposition of graphs and obtain results for the case H=P_\\ell is the path of length \\ell. Two of these results solve weakenings of a conjecture of Kouider and Lonc (1999) and a conjecture of Favaron, Genest and Kouider (2010), both for regular graphs. We prove that, for every positive integer \\ell, (i) there is a positive integer m_0 such that, if G is a 2m\\ell-regular graph with m>=m_0, then G admits a P_\\ell-decomposition; (ii) if \\ell is odd, there is a positive integer m_0 such that, if G is an m\\ell-regular graph with m>=m_0 containing an m-factor, then G admits a P_\\ell-decomposition. The third result concerns highly edge-connected graphs: there is a positive integer k_\\ell such that if G is a k_\\ell-edge-connected graph whose number of edges is divisible by \\ell, then G admits a P_\\ell-decomposition. This result verifies for paths the Decomposition Conjecture of Barát and Thomassen (2006), on trees.