Given a connected undirected graph $\overline{G}$ on $n$ vertices and nonnegative edge costs $c$, the $\ensuremath{{2ECM}}$ problem is that of finding a 2-edge connected spanning multisubgraph of $\overline{G}$ of minimum cost. The natural linear program (LP) for $\ensuremath{{2ECM}}$, which coincides with the subtour LP for the traveling salesman problem on the metric closure of $\overline{G}$, gives a lower bound on the optimal cost. For instances where this LP is optimized by a half-integral solution $x$, Carr and Ravi (1998) showed that the integrality gap is at most $\frac43$: they show that the vector $\frac43 x$ dominates a convex combination of incidence vectors of 2-edge connected spanning multisubgraphs of $\overline{G}$. We present a simpler proof of the result due to Carr and Ravi by applying an extension of Lovász's splitting-off theorem. Our proof naturally leads to a $\frac43$-approximation algorithm for half-integral instances. Given a half-integral solution $x$ to the LP for $\ensuremath{{2ECM}}$, we give an $O(n^2)$-time algorithm to obtain a 2-edge connected spanning multisubgraph of $\overline{G}$ with cost at most $\frac43 c^T x$. We also consider a related problem of finding a cheap 2-edge connected spanning subgraph of a 3-regular, 3-edge connected graph $G = (V,E)$ with arbitrary edge costs $c$. We give a polynomial-time Las Vegas algorithm that finds a random 2-edge connected spanning subgraph $H$ of $G$ whose expected cost, $\mathbb{E}\left[{c(H)}\right]$, is at most $\frac45 c(E)$.

We present approximation algorithms for several network design problems in the model of Flexible Graph Connectivity (Adjiashvili, Hommelsheim and Mühlenthaler, "Flexible Graph Connectivity", Math. Program. pp. 1-33 (2021), IPCO 2020: pp. 13-26). In an instance of the Flexible Graph Connectivity (FGC) problem, we have an undirected connected graph G = (V,E), a partition of E into a set of safe edges S and a set of unsafe edges U, and nonnegative costs {c_e}_{e ∈ E} on the edges. A subset F ⊆ E of edges is feasible for FGC if for any unsafe edge e ∈ F ∩ U, the subgraph (V,F⧵{e}) is connected. The algorithmic goal is to find a (feasible) solution F that minimizes c(F) = ∑_{e ∈ F} c_e. We present a simple 2-approximation algorithm for FGC via a reduction to the minimum-cost r-out 2-arborescence problem. This improves upon the 2.527-approximation algorithm of Adjiashvili et al. For integers p ≥ 1 and q ≥ 0, the (p,q)-FGC problem is a generalization of FGC where we seek a minimum-cost subgraph H = (V,F) that remains p-edge connected against the failure of any set of at most q unsafe edges; that is, for any set F' ⊆ U with |F'| ≤ q, H-F' = (V, F ⧵ F') should be p-edge connected. Note that FGC corresponds to the (1,1)-FGC problem. We give approximation algorithms for two important special cases of (p,q)-FGC: (a) Our 2-approximation algorithm for FGC extends to a (k+1)-approximation algorithm for the (1,k)-FGC problem. (b) We present a 4-approximation algorithm for the (k,1)-FGC problem. For the unweighted FGC problem, where each edge has unit cost, we give a 16/11-approximation algorithm. This improves on the result of Adjiashvili et al. for this problem. The (p,q)-FGC model with p = 1 or q ≤ 1 can be cast as the Capacitated k-Connected Subgraph problem which is a special case of the well-known Capacitated Network Design problem. We denote the former problem by Cap-k-ECSS. An instance of this problem consists of an undirected graph G = (V,E), nonnegative integer edge-capacities {u_e}_{e ∈ E}, nonnegative edge-costs {c_e}_{e ∈ E}, and a positive integer k. The goal is to find a minimum-cost edge-set F ⊆ E such that every (non-trivial) cut of the capacitated subgraph H(V,F,u) has capacity at least k. We give a min(k, 2max_{e ∈ E} u_e)-approximation algorithm for this problem.

Given a connected undirected graph $\bar{G}$ on $n$ vertices, and non-negative edge costs $c$, the 2ECM problem is that of finding a $2$-edge~connected spanning multisubgraph of $\bar{G}$ of minimum cost. The natural linear program (LP) for 2ECM, which coincides with the subtour LP for the Traveling Salesman Problem on the metric closure of $\bar{G}$, gives a lower bound on the optimal cost. For instances where this LP is optimized by a half-integral solution $x$, Carr and Ravi (1998) showed that the integrality gap is at most $\frac43$: they show that the vector $\frac43 x$ dominates a convex combination of incidence vectors of $2$-edge connected spanning multisubgraphs of $\bar{G}$. We present a simpler proof of the result due to Carr and Ravi by applying an extension of Lov\'{a}sz's splitting-off theorem. Our proof naturally leads to a $\frac43$-approximation algorithm for half-integral instances. Given a half-integral solution $x$ to the LP for 2ECM, we give an $O(n^2)$-time algorithm to obtain a $2$-edge connected spanning multisubgraph of $\bar{G}$ whose cost is at most $\frac43 c^T x$.

Given a complete graph $K_{n}=(V, E)$ with nonnegative edge costs $c\in {\mathbb R}^{E}$, the problem 2EC is that of finding a 2-edge connected spanning multisubgraph of $K_{n}$ of minimum cost. The integrality gap $\alpha\text{2{\it EC}}$ of the linear programming relaxation $\text{2{\it EC}}^{\text{LP}}$ for 2EC has been conjectured to be $\frac{6}{5}$, although currently we only know that $\frac{6}{5}\leq\alpha\text{2{\it EC}}\leq\frac{3}{2}$. In this paper, we explore the idea of using the structure of solutions for $\text{2{\it EC}}^{\text{LP}}$ and the concept of convex combination to obtain improved bounds for $\alpha\text{2{\it EC}}$. We focus our efforts on a family $J$ of half-integer solutions that appear to give the largest integrality gap for $\text{2{\it EC}}^{\text{LP}}$. We successfully show that the conjecture $\alpha\text{2{\it EC}} = \frac{6}{5}$ is true for any cost functions optimized by some $x^{*}\in J$.

We study the problem of finding the breakpoint median for multichromosomal unsigned genomes that contain circular or mixed (circular and linear) chromosomes. It has been shown by Tannier, Zheng, and Sankoff that for signed multichromosomal circular or mixed genomes the breakpoint median can be found in polynomial time; however, the complexity of the unsigned versions of the problems were unknown. In this paper, we show that these problems can all be solved in polynomial time. We also study restricted versions of the multichromosomal breakpoint median problem where the number of chromosomes of the median must be a certain number. We show that as soon as we impose a fixed number of chromosomes the problem becomes NP-hard. Moreover, we introduce the notion of partially signed circular or mixed genomes, where both signed and unsigned genes may exist in the same genome. We provide the first study of this form of these breakpoint median problems and show that these problem can also be solved in polynomial time by providing a novel transformation to b-matchings.

In this paper we are interested in algorithms for finding $2$-factors that cover certain prescribed edge-cuts in bridgeless cubic graphs. Since a Hamilton cycle is a 2-factor covering all edge-cuts, imposing the constraint of covering those edge-cuts makes the obtained $2$-factor closer to a Hamilton cycle. We present an algorithm for finding a minimum-weight $2$-factor covering all the $3$-edge cuts in weighted bridgeless cubic graphs, together with a polyhedral description of such 2-factors and that of perfect matchings intersecting all the 3-edge cuts in exactly one edge. We further give an algorithm for finding a 2-factor covering all the $3$- and $4$-edge cuts in bridgeless cubic graphs. Both of these algorithms run in ${\rm O}(n\sp{3})$ time, where $n$ is the number of vertices. As an application of the latter algorithm, we design a 6/5-approximation algorithm for finding a minimum 2-edge-connected spanning subgraph in 3-edge-connected cubic graphs, which improves upon the previous best ratio of 5/4. The algorithm begins with finding a 2-factor covering all 3- and 4-edge cuts, which is the bottleneck in terms of complexity, and thus it has running time ${\rm O}(n\sp{3})$. We then improve this time complexity to ${\rm O}(n\sp{2} \log\sp{4}n)$ by relaxing the condition of the initial $2$-factor and elaborating on the subsequent processes.

The problem of designing communication networks that can survive the loss of any single link is studied. Such problems can be formulated as minimum cost 2-edge connected subgraph problems in a complete graph. The linear programming cutting plane approach has been used effectively for related problems in [Schwerpunktprogramm der Deutschen Forschungsgemeinschaft, Anwendungsbezogene Optimierung and Steuerung, Report No. 188, 1989], where problem-specific cutting planes that define facets of the underlying integer polyhedra are used. This paper introduces a new class of valid inequalities for the polytope associated with the minimum cost 2-edge connected subgraph problem, and necessary and sufficient conditions for these inequalities to be facet-inducing for this polytope are given.

The authors investigate whether maximal overlapping of protocol test subsequences can be achieved in polynomial time. They review the concepts related to FSM (finite state machine)-based test sequence generation and then define the optimal test sequence generation (OTSG) problem. It is proved that the OTSG problem is NP-complete. Therefore an efficient solution to the problem should not be expected in the general case.>