There are several frameworks to compute approximate Pareto sets for multiobjective optimization (MOO) problems. An approximate Pareto set that is even precise in one specific objective is called one-exact. In such frameworks, some auxiliary single-objective problem is considered, for which a problem-specific oracle is required. However, often these oracles are required to be a PTAS or even FPTAS. As such, these frameworks are only applicable to "simple" MOO problems that allow for such strong oracles to exist. They are inapplicable whenever the auxiliary problem is APX-hard. We propose a general framework that, for a (possibly even non-constant) accuracy vector β = (β_2, … , β_d) and any ε > 0, computes polynomially sized, one-exact (1,(1 + ε)β_2,… ,(1 + ε)β_d)-Pareto sets for d-objective minimization problems. The framework is analogously applicable to maximization and mixed MOO problems. The running time is polynomial in the time required to solve our auxiliary problem β-RelaxedDualRestrict. Notably, these guarantees hold even if β-RelaxedDualRestrict is APX-hard. We further show that if β-RelaxedDualRestrict cannot be solved in polynomial time, then no (1,β_2, … ,β_d)-Pareto set can be computed in polynomial time. For biobjective problems, our framework even yields a (1,(1 + ε)β_2)-Pareto set of at most 𝒪(log β₂) times the size of the minimum-size one-exact (1,(1 + ε)β_2)-Pareto set. We show that this relative size guarantee is asymptotically tight. Further, we present techniques to obtain suitable oracles for β-RelaxedDualRestrict from existing (single-objective) approximation algorithms, including a general "re-randomization" method that may be of independent interest. Using these, we obtain new best approximation guarantees for several established MOO problems, including Spanner, Clique, TSP, Facility Location, and Set Cover problems.

Given an undirected graph G with edge weights and lengths, a minimum α-spanner is a least-weight subgraph H ⊆ G that preserves distances w.r.t. the lengths between all node pairs up to a factor of α. Literature often takes the simplifying assumption of a single (coupled) edge function for weights and lengths. For such instances, several exact and non-exact algorithms are known and have been thoroughly evaluated in practice. However, many practical instances have decoupled form, as their weights and lengths are generally independent. Due to the increased complexity, only few (and even fewer practical) algorithms are able to guarantee low-weight solutions. This prompts practitioners to force their naturally decoupled instances into a coupled format, forsaking any quality guarantee. We implement several exact, approximative and heuristic algorithms for decoupled α-spanners, and use algorithm engineering to speed them up in practice. Our hypothesis-driven experiments evaluate their performance w.r.t. solution quality and speed. Generally, many practical instances can indeed be solved exactly within reasonable time, while LP-based approximation algorithms are not worthwhile. We find that standard greedy algorithms often yield acceptable results, but there are also practical instances for which they yield arbitrarily poor solutions. Here, augmented greedy variations offer a good compromise between solution quality and speed.

Determining the crossing numbers of Cartesian products of small graphs with arbitrarily large paths has been an ongoing topic of research since the 1970s. Doing so requires the establishment of coincident upper and lower bounds; the former is usually demonstrated by providing a suitable drawing procedure, while the latter often requires substantial theoretical arguments. Many such papers have been published, which typically focus on just one or two small graphs at a time, and use ad hoc arguments specific to those graphs. We propose a general approach which, when successful, establishes the required lower bound. This approach can be applied to the Cartesian product of any graph with arbitrarily large paths, and in each case involves solving a modified version of the crossing number problem on a finite number (typically only two or three) of small graphs. We demonstrate the potency of this approach by applying it to Cartesian products involving all 133 graphs of orders five or six, and show that it is successful in 128 cases. This includes 60 cases which a recent survey listed as either undetermined, or determined only in journals without adequate peer review.

In this paper, we study the problem of pathfinding on traversal-dependent graphs, i.e., graphs whose edges change depending on the previously visited vertices. In particular, we study self-deleting graphs, introduced by Carmesin et al. [Sarah Carmesin et al., 2023], which consist of a graph G = (V, E) and a function f: V → 2^E, where f(v) is the set of edges that will be deleted after visiting the vertex v. In the (Shortest) Self-Deleting s-t-path problem we are given a self-deleting graph and its vertices s and t, and we are asked to find a (shortest) path from s to t, such that it does not traverse an edge in f(v) after visiting v for any vertex v. We prove that Self-Deleting s-t-path is NP-hard even if the given graph is outerplanar, bipartite, has maximum degree 3, bandwidth 2 and |f(v)| ≤ 1 for each vertex v. We show that Shortest Self-Deleting s-t-path is W[1]-complete parameterized by the length of the sought path and that Self-Deleting s-t-path is W[1]-complete parameterized by the vertex cover number, feedback vertex set number and treedepth. We also show that the problem becomes FPT when we parameterize by the maximum size of f(v) and several structural parameters. Lastly, we show that the problem does not admit a polynomial kernel even for parameterization by the vertex cover number and the maximum size of f(v) combined already on 2-outerplanar graphs.

Abstract We introduce and discuss the problem: given a directed graph with edge capacities $$\textit{cap} $$ cap and a retention ratio $$\alpha \in (0,1)$$ α ∈ ( 0 , 1 ) , find the smallest subgraph that, for each pair of vertices ( u , v ), preserves at least a fraction $$\alpha $$ α of a maximum u - v -flow’s value. This problem originates from the practical setting of reducing the power consumption in a computer network: it models turning off as many links as possible, while retaining the ability to transmit at least $$\alpha $$ α times the traffic compared to the original network. First we prove that is NP-hard already on a restricted set of directed acyclic graphs (DAGs) with unit edge capacities. Our reduction also shows that a closely related problem (which only considers the arguably most complicated core of the problem in the objective function) is NP-hard to approximate within a sublogarithmic factor already on DAGs. In terms of positive results, we present two algorithms that solve optimally on directed series-parallel graphs (DSPs): a simple linear-time algorithm for the special case of unit edge capacities and a cubic-time dynamic programming algorithm for the general case of non-uniform edge capacities. Further, we introduce the family of laminar series-parallel graphs (LSPs), a generalization of DSPs that also includes cyclic and very dense graphs. Their properties allow us to solve on LSPs by employing our DSP-algorithms as subroutines. In addition, we give a separate quadratic-time algorithm for on LSPs with unit edge capacities that also yields straightforward quadratic time algorithms for several related problems such as and on LSPs.

Abstract In this paper, we study the connected blocks polytope, which, apart from its own merits, can be seen as the generalization of certain connectivity based or Eulerian subgraph polytopes. We provide a complete facet description of this polytope, characterize its edges and show that it is Hirsch. We also show that connected blocks polytopes admit a regular unimodular triangulation by constructing a squarefree Gröbner basis. In addition, we prove that the polytope is Gorenstein of index 2 and that its $$h^*$$ h ∗ -vector is unimodal.

Given a weighted graph $G$, a minimum weight $α$-spanner is a least-weight subgraph $H\subseteq G$ that preserves minimum distances between all node pairs up to a factor of $α$. There are many results on heuristics and approximation algorithms, including a recent investigation of their practical performance [20]. Exact approaches, in contrast, have long been denounced as impractical: The first exact ILP (integer linear program) method [48] from 2004 is based on a model with exponentially many path variables, solved via column generation. A second approach [2], modeling via arc-based multicommodity flow, was presented in 2019. In both cases, only graphs with 40-100 nodes were reported to be solvable. In this paper, we briefly report on a theoretical comparison between these two models from a polyhedral point of view, and then concentrate on improvements and engineering aspects. We evaluate their performance in a large-scale empirical study. We report that our tuned column generation approach, based on multicriteria shortest path computations, is able to solve instances with over 16000 nodes within 13 minutes. Furthermore, now knowing optimal solutions for larger graphs, we are able to investigate the quality of the strongest known heuristic on reasonably sized instances for the first time.

Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward $k$-planar drawings of DAGs in which the edges are monotonically increasing in a common direction and every edge is crossed at most $k$ times for some integer $k \ge 1$. We show that the number of crossings per edge in a monotone drawing is in general unbounded for the class of bipartite outerplanar, cubic, or bounded pathwidth DAGs. However, it is at most two for outerpaths and it is at most quadratic in the bandwidth in general. From the computational point of view, we prove that testing upward-$k$-planarity is NP-complete already for $k=1$ and even for restricted instances for which upward planarity testing is polynomial. On the positive side, we can decide in linear time whether a single-source DAG admits an upward 1-planar drawing in which all vertices are incident to the outer face.

Beyond planarity concepts (prominent examples include k-planarity or fan-planarity) apply certain restrictions on the allowed patterns of crossings in drawings. It is natural to ask, how much the number of crossings may increase over the traditional (unrestricted) crossing number. Previous approaches to bound such ratios, e.g. [arXiv:1908.03153, arXiv:2105.12452], require very specialized constructions and arguments for each considered beyond planarity concept, and mostly only yield asymptotically non-tight bounds. We propose a very general proof framework that allows us to obtain asymptotically tight bounds, and where the concept-specific parts of the proof typically boil down to a couple of lines. We show the strength of our approach by giving improved or first bounds for several beyond planarity concepts.

Abstract Given a graph $$G=(V,E)$$ G = ( V , E ) and a set $$S \subseteq \left( {\begin{array}{c}V\\ 2\end{array}}\right) $$ S ⊆ V 2 of terminal pairs, the minimum multicut problem asks for a minimum edge set $$\delta \subseteq E$$ δ ⊆ E such that there is no s-t-path in $$G -\delta $$ G - δ for any $$\{s,t\}\in S$$ { s , t } ∈ S . For $$|S|=1$$ | S | = 1 this is the well known s-t-cut problem, but in general the minimum multicut problem is NP-complete, even if the input graph is a tree. The multicut polytope $$\textsc {MultC}^\square (G,S)$$ M U L T C □ ( G , S ) is the convex hull of all multicuts in G; the multicut dominant is given by $$\textsc {MultC}(G,S)=\textsc {MultC}^\square (G,S)+\mathbb {R}^E_{{\ge 0}}$$ M U L T C ( G , S ) = M U L T C □ ( G , S ) + R ≥ 0 E . The latter is the relevant object for the minimization problem. While polyhedra associated to several cut problems have been studied intensively there is only little knowledge for multicut. We investigate properties of the multicut dominant and in particular derive results on liftings of facet-defining inequalities. This yields a classification of all facet-defining path- and edge inequalities. Moreover, we investigate the effect of graph operations such as node splitting, edge subdivisions, and edge contractions on the multicut-dominant and its facet-defining inequalities. In addition, we introduce facet-defining inequalities supported on stars, trees, and cycles and show that the former two can be separated in polynomial time when the input graph is a tree.

Subgraph Problems are optimization problems on graphs where a solution is a subgraph that satisfies some property and optimizes some measure. Examples include shortest path, minimum cut, maximum matching, or vertex cover. In reality, however, one often deals with time-dependent data, i.e., the input graph may change over time and we need to adapt our solution accordingly. We are interested in guaranteeing optimal solutions after each graph change while retaining as much of the previous solution as possible. Even if the subgraph problem itself is polynomial-time computable, this multistage variant turns out to be NP-hard in most cases. We present an algorithmic framework that—for any subgraph problem of a certain type—guarantees an optimal solution for each point in time and provides an approximation guarantee for the similarity between subsequent solutions. We show that the class of applicable multistage subgraph problems is very rich and that proving membership to this class is mostly straightforward. As examples, we explicitly state these proofs and obtain corresponding approximation algorithms for the natural multistage versions of Shortest s-t-Path, Perfect Matching, Minimum s-t-Cut—and further classical problems on bipartite or planar graphs, namely Maximum Cut, Vertex Cover, and Independent Set. We also report that all these problems are already NP-hard on only two stages.

Green Traffic Engineering encompasses network design and traffic routing strategies that aim at reducing the power consumption of a backbone network. We argue that turning off linecards is the most effective practically feasible approach to reach this goal. Thus, we investigate the problem of minimizing the number of active line cards in a network while simultaneously allowing a multi-commodity flow being routed and keeping the maximum link utilization below a certain threshold. In addition to proving this problem to be NP-hard, we present an optimal ILP-based algorithm as well as a heuristic based on 2-Segment Routing. Lastly, we evaluate both approaches on real-world networks obtained from the Repetita Framework and a globally operating Internet Service Provider. The results of this evaluation indicate that our heuristic is not only close to optimal but significantly faster than the optimal algorithm, making it viable in practice.

A multiplicative $α$-spanner $H$ is a subgraph of $G=(V,E)$ with the same vertices and fewer edges that preserves distances up to the factor $α$, i.e., $d_H(u,v)\leqα\cdot d_G(u,v)$ for all vertices $u$, $v$. While many algorithms have been developed to find good spanners in terms of approximation guarantees, no experimental studies comparing different approaches exist. We implemented a rich selection of those algorithms and evaluate them on a variety of instances regarding, e.g., their running time, sparseness, lightness, and effective stretch.

Abstract In multistage perfect matching problems, we are given a sequence of graphs on the same vertex set and are asked to find a sequence of perfect matchings, corresponding to the sequence of graphs, such that consecutive matchings are as similar as possible. More precisely, we aim to maximize the intersections, or minimize the unions between consecutive matchings. We show that these problems are NP-hard even in very restricted scenarios. As our main contribution, we present the first non-trivial approximation algorithms for these problems: On the one hand, we devise a tight approximation on graph sequences of length two (2-stage graphs). On the other hand, we propose several general methods to deduce multistage approximations from blackbox approximations on 2-stage graphs.

Traffic engineering is an important concept that allows Internet Service Providers (ISPs) to utilize their existing routing hardware more efficiently. One technology that can be used is Segment Routing (SR). In this paper, we address the use of SR to increase the resilience against failure scenarios. In addition, we develop solutions that are manageable and, thus, deployable in a tier 1 ISP network. We propose a post-convergence aware SR based optimization model. With it, we can proactively find a single SR configuration that is beneficial in all predefined failure scenarios, including single link failures, shared risk link group failures, and node failures. In addition to this use-case, we also extend the optimization model to include other important practical requirements such as keeping the number of SR tunnels to a minimum, avoiding arbitrary traffic splitting, or meeting latency bounds. We evaluate our approaches with recently measured data from a tier 1 ISP and show that we can improve over state of the art routing approaches.

We consider the multiobjective shortest path (MOSP) problem. While known approximation algorithms allow a polynomial running time, the degrees of these polynomials are dependent on the number of objective functions. Unfortunately, this also holds true for their best-case. Exact algorithms, while attaining an exponential worst-case running time even in the number of nodes, allow for far better best-case performance and are thus preferred in practice. We introduce a new general approximation framework for MOSP. It aims at combining strong worst-case guarantees with practically useful performance. It allows for various labeling strategies as employed by exact algorithms; thus, decades of research can be utilized. We conduct a comprehensive computational study to compare our framework to known approximations and exact algorithms. For many, this is their first practical investigation. Furthermore, this is the first time that graphs of practically relevant sizes as well as real-world instances are considered in the context of MOSP approximation. The results show that our framework is superior to the known approximation methods in running time and quality. They also demonstrate the usefulness and limits of approximations compared to exact methods.

The crossing number is the smallest number of pairwise edge crossings when drawing a graph into the plane. There are only very few graph classes for which the exact crossing number is known or for which there at least exist constant approximation ratios. Furthermore, up to now, general crossing number computations have never been successfully tackled using bounded width of graph decompositions, like treewidth or pathwidth. In this paper, we show that the crossing number is tractable (even in linear time) for maximal graphs of bounded pathwidth 3. The technique also shows that the crossing number and the rectilinear (a.k.a. straight-line) crossing number are identical for this graph class, and that we require only an $$O(n)\times O(n)$$ O(n)×O(n)-grid to achieve such a drawing. Our techniques can further be extended to devise a 2-approximation for general graphs with pathwidth 3. One crucial ingredient here is that the crossing number of a graph with a separation pair can be lower-bounded using the crossing numbers of its cut-components, a result that may be interesting in its own right. Finally, we give a $$4{\mathbf{w}}^3$$ 4w3-approximation of the crossing number for maximal graphs of pathwidth $${\mathbf{w}}$$ w. This is a constant approximation for bounded pathwidth. We complement this with an NP-hardness proof of the weighted crossing number already for pathwidth 3 graphs and bicliques $$K_{3,n}$$ K3,n.

The minimum genus of a graph is an important question in graph theory and a key ingredient in several graph algorithms. However, its computation is NP-hard and turns out to be hard even in practice. Only recently, the first non-trivial approach - based on SAT and ILP (integer linear programming) models - has been presented, but it is unable to successfully tackle graphs of genus larger than 1 in practice. Herein, we show how to improve the ILP formulation. The crucial ingredients are two-fold. First, we show that instead of modeling rotation schemes explicitly, it suffices to optimize over partitions of the (bidirected) arc set A of the graph. Second, we exploit the cycle structure of the graph, explicitly mapping short closed walks on A to faces in the embedding. Besides the theoretical advantages of our models, we show their practical strength by a thorough experimental evaluation. Contrary to the previous approach, we are able to quickly solve many instances of genus > 1.

Traffic engineering is an important concept that allows Internet Service Providers (ISPs) to utilize their existing routing hardware more efficiently. One technology that can be used in this field is Segment Routing (SR). While transferring SR approaches from theory towards an actual deployment, it quickly becomes apparent that there are many requirements and constraints that have to be satisfied. One of the most important requirement for a traffic engineering approach is the resilience against failure scenarios. In this paper, we propose a post-convergence aware 2-SR based optimization model. With it, we are able to proactively find a single SR configuration that is beneficial in all predefined failure scenarios, including single link failures, shared risk link group failures, and node failures. We evaluate our model with recently measured data from a tier 1 ISP and show that we can improve over state of the art routing approaches.

The NP-hard Maximum Planar Subgraph problem asks for a planar subgraph $H$ of a given graph $G$ such that $H$ has maximum edge cardinality. For more than two decades, the only known non-trivial exact algorithm was based on integer linear programming and Kuratowski's famous planarity criterion. We build upon this approach and present new constraint classes, together with a lifting of the polyhedron, to obtain provably stronger LP-relaxations, and in turn faster algorithms in practice. The new constraints take Euler's polyhedron formula as a starting point and combine it with considering cycles in $G$. This paper discusses both the theoretical as well as the practical sides of this strengthening.

Segment Routing (SR) based traffic engineering can be used to avoid network congestion effectively. Most research about SR considers the routing metric as a given constant. The metric defines shortest paths. As shortest paths are essential building blocks of SR paths, the metrics heavily influence SR. In this paper, we evaluate this influence thoroughly using data from a tier one Internet Service Provider (ISP) backbone, as well as other, publicly available topologies. We conclude that metrics do in fact play a role in SR optimization. Simple metrics, however, already push SR close to the optimum with respect to the most common traffic engineering objective of minimizing maximum utilization.

Given a graph G, the NP-hard Maximum Planar Subgraph problem asks for a planar subgraph of G with the maximum number of edges. The only known non-trivial exact algorithm utilizes Kuratowski's famous planarity criterion and can be formulated as an integer linear program (ILP) or a pseudo-boolean satisfiability problem (PBS). We examine three alternative characterizations of planarity regarding their applicability to model maximum planar subgraphs. For each, we consider both ILP and PBS variants, investigate diverse formulation aspects, and evaluate their practical performance.

Segment Routing (SR) can be used as a traffic engineering strategy to counteract increasing loads on networks like Internet Service Provider (ISP) backbones. Many SR approaches, however, optimize traffic flows that were measured in the past. This paper introduces a new tunnel training architecture. It aims to show that the results of these strategies can still be beneficial for routing new traffic flows using the tunnel training architecture. We evaluate the selection of different matrices for training, as well as the choice of different tunnel selection heuristics. The results show that optimization results tend to be beneficial even for traffic matrices that were not known during the optimization. Classifying the quality of SR tunnels, though, proves to be difficult and trace dependent.

Let G be a connected planar (but not yet embedded) graph and F a set of additional edges not in G. The multiple edge insertion problem (MEI) asks for a drawing of G+F with the minimum number of pairwise edge crossings, such that the subdrawing of G is plane. An optimal solution to this problem is known to approximate the crossing number of the graph G+F. Finding an exact solution to MEI is NP-hard for general F, but linear time solvable for the special case of |F|=1 [Gutwenger et al, SODA 2001/Algorithmica] and polynomial time solvable when all of F are incident to a new vertex [Chimani et al, SODA 2009]. The complexity for general F but with constant k=|F| was open, but algorithms both with relative and absolute approximation guarantees have been presented [Chuzhoy et al, SODA 2011], [Chimani-Hlineny, ICALP 2011]. We show that the problem is fixed parameter tractable (FPT) in k for biconnected G, or if the cut vertices of G have bounded degrees. We give the first exact algorithm for this problem; it requires only O(|V(G)|) time for any constant k.

Formally, approaches based on mathematical programming are able to find provably optimal solutions. However, the demands on a verifiable formal proof are typically much higher than the guarantees we can sensibly attribute to implementations of mathematical programs. We consider this in the context of the crossing number problem, one of the most prominent problems in topological graph theory. The problem asks for the minimum number of edge crossings in any drawing of a given graph. Graph-theoretic proofs for this problem are known to be notoriously hard to obtain. At the same time, proofs even for very specific graphs are often of interest in crossing number research, as they can, e.g., form the basis for inductive proofs. We propose a system to automatically generate a formal proof based on an ILP computation. Such a proof is (relatively) easily verifiable, and does not require the understanding of any complex ILP codes. As such, we hope our proof system may serve as a showcase for the necessary steps and central design goals of how to establish formal proof systems based on mathematical programming formulations.

In a directed graph G with non-correlated edge lengths and costs, the network design problem with bounded distances asks for a cost-minimal spanning subgraph subject to a length bound for all node pairs. We give a bi-criteria (2+\varepsilon,O(n^{0.5+\varepsilon}))-approximation for this problem. This improves on the currently best known linear approximation bound, at the cost of violating the distance bound by a factor of at most 2+\varepsilon. In the course of proving this result, the related problem of directed shallow-light Steiner trees arises as a subproblem. In the context of directed graphs, approximations to this problem have been elusive. We present the first non-trivial result by proposing a (1+\varepsilon,O(|R|^{\varepsilon}))-ap\-proximation, where R is the set of terminals. Finally, we show how to apply our results to obtain an (\alpha+\varepsilon,O(n^{0.5+\varepsilon}))-approximation for light-weight directed \alpha-spanners. For this, no non-trivial approximation algorithm has been known before. All running times depends on n and \varepsilon and are polynomial in n for any fixed \varepsilon>0.

The upward crossing number problem asks for a drawing of the graph into the plane with the minimum number of edge crossings where the edges are drawn as monotonously increasing curves w.r.t. the y-axis. While there is a large body of work on solving this central graph drawing problem heuristically, we present the first approach to solve the problem to proven optimality. Our approach is based on a reformulation of the problem as a boolean formula that can be iteratively tightened and resolved. In our experiments, we show the practical applicability and limits of our approach. Furthermore, we can now for the first time evaluate the state-of-the-art heuristics w.r.t. true optimum solutions. This leads to the finding that these algorithms are in general surprisingly far away from the optimum. Finally, we show that we can use our approach as a strong heuristic: even after only one minute of running time, our approach typically gives better solutions than the known heuristics for medium sized instances.

In a connected weighted graph, consider deleting the edges one at a time, in some order, such that after every deletion the remaining edges are still connected. We study the problem of finding such a deletion sequence that maximizes the sum of the weights of the edges in all the distinct graphs generated: the weight of an edge is counted in every graph that it is in. This effectively asks for the high-weight edges to remain in the graph as long as possible, subject to connectivity. We apply this to road network generalization in order to generate a sequence of successively more generalized maps of a road network so that these maps go well together, instead of considering each level of generalization independently. In particular, we look at the problem of making a road segment selection that is consistent across zoom levels.

Let $G$ be a graph embedded in an orientable surface $\Sigma$, possibly with edge weights, and denote by ${\rm len}(\gamma)$ the length (the number of edges or the sum of the edge weights) of a cycle $\gamma$ in $G$. The stretch of a graph embedded on a surface is the minimum of ${\rm len}(\alpha)\cdot {\rm len}(\beta)$ over all pairs of cycles $\alpha$ and $\beta$ that cross exactly once. We provide two algorithms to compute the stretch of an embedded graph, each based on a different principle. The first algorithm is based on surgery and computes the stretch in time $O(g^4 n \log n)$ with high probability, or in time $O(g^4 n \log^2 n)$ in the worst case, where $g$ is the genus of the surface $\Sigma$ and $n$ is the number of vertices in $G$. The second algorithm is based on using a short homology basis and computes the stretch in time $O(n^2\log n + n^2g + ng^3)$.

We present a semidefinite programming (SDP) approach for the problem of ordering vertices of a layered graph such that the edges of the graph are drawn as vertical as possible. This multilevel vertical ordering (MLVO) problem is a quadratic ordering problem and conceptually related to the well-studied problem of multilevel crossing minimization (MLCM). In contrast to the latter, it can be formulated such that it does not merely consist of multiple sequentially linked bilevel quadratic ordering problems, but as a genuine multilevel problem with dense cost matrix. This allows us to describe the graphs' structures more compactly and therefore obtain solutions for graphs too large for MLCM in practice. In this paper we give motivation and mathematical models for MLVO. We formulate linear and quadratic programs, including some strengthening constraint classes, and an SDP relaxation for MLVO. We compare all approaches both theoretically and experimentally and show that MLVO's properties render linear and quadratic programming approaches inapplicable, even for small sparse graphs, while the SDP works surprisingly well in practice. This is in stark contrast to other ordering problems like MLCM, where such graphs are typically solved more efficiently with integer linear programs. Finally, we also compare our approach to related MLCM approaches.

MOTIVATION: Mass spectrometry allows sensitive, automated and high-throughput analysis of small molecules such as metabolites. One major bottleneck in metabolomics is the identification of 'unknown' small molecules not in any database. Recently, fragmentation tree alignments have been introduced for the automated comparison of the fragmentation patterns of small molecules. Fragmentation pattern similarities are strongly correlated with the chemical similarity of the molecules, and allow us to cluster compounds based solely on their fragmentation patterns. RESULTS: Aligning fragmentation trees is computationally hard. Nevertheless, we present three exact algorithms for the problem: a dynamic programming (DP) algorithm, a sparse variant of the DP, and an Integer Linear Program (ILP). Evaluation of our methods on three different datasets showed that thousands of alignments can be computed in a matter of minutes using DP, even for 'challenging' instances. Running times of the sparse DP were an order of magnitude better than for the classical DP. The ILP was clearly outperformed by both DP approaches. We also found that for both DP algorithms, computing the 1% slowest alignments required as much time as computing the 99% fastest.

We present an approach based on semidefinite programs (SDP) to tackle the multi-level crossing minimization problem. Thereby, we are given a layered graph (i.e., the graph's vertices are assigned to multiple parallel levels) and ask for an ordering of the nodes on their levels such that, when drawing the graph with straight lines, the resulting number of crossings is minimized. Solving this step is crucial in the probably most widely used graph drawing scheme, the so-called Sugiyama framework. The problem has received a lot of attention both in the field of heuristics and exact methods. For a long time, integer linear programming (ILP) approaches were the only exact algorithms applicable at least to small graphs. Recently, SDP formulations for the special case of two levels were proposed and dominated the ILP for dense instances. In this paper, we present a new SDP formulation for the general multi-level version that, for two-levels, is even stronger than the aforementioned specialized SDP. As a side-product, we also obtain an SDP-based heuristic which in practice always gives (near-)optimal solutions. We conduct a large set of experiments, both on randomized and on real-world instances, and compare our approach to a state-of-the-art ILP-based branch-and-cut implementation. The SDP clearly dominates for denser graphs, while the ILP approach is usually faster for sparse instances. However, even for such sparse graphs, the SDP solves more instances to optimality than the ILP. In fact, there is no single instance the ILP solved, which the SDP did not. Overall, our experiments reveal that for sparse graphs, one should usually try to find an optimal solution with the ILP first. If this approach does not solve the instance to optimality within reasonable time, the SDP still has a good chance to do so. Being able to solve larger real-world instances than reported before, we are also able to evaluate heuristics for this problem. In this paper we do so for the traditional barycenter-heuristic (showing that it leaves a large gap to the true optimum) and the state-of-the-art upward-planarization method (showing that it is usually close to the optimum).

Let S be a set of k strings over an alphabet Σ; each string has a length between ℓ and n. The Closest Substring Problem (CSSP) is to find a minimal integer d (and a corresponding string t of length ℓ) such that each string s ∊ S has a substring of length ℓ with Hamming distance at most d to t. We say t is the closest substring to S. For ℓ = n, this problem is known as the Closest String Problem (CSP). Particularly in computational biology, the CSP and CSSP have found numerous practical applications such as identifying regulatory motifs and approximate gene clusters, and in degenerate primer design. We study ILP formulations for both problems. Our experiments show that a position-based formulation for the CSP performs very well on real-world instances emerging from biology. Even on randomly generated instances that are hard to solve to optimality, solving the root relaxation leads to solutions very close to the optimum. For the CSSP we give a new formulation that is polytope-wise stronger than a straightforward extension of the CSP formulation. Furthermore we propose a strengthening constraint class that speeds up the running time.

In the last years, several integer linear programming (ILP) formulations for the crossing number problem arose. While they all contain a common conceptual core, the properties of the corresponding polytopes have never been investigated. In this paper, we formally establish the crossing number polytope and show several facet-defining constraint classes.

The crossing number of a graph is the least number of pairwise edge crossings in a drawing of the graph in the plane. We provide an O(n log n) time constant factor approximation algorithm for the crossing number of a graph of bounded maximum degree which is “densely enough” embeddable in an arbitrary fixed orientable surface. Our approach combines some known tools with a powerful new lower bound on the crossing number of an embedded graph. This result extends previous results that gave such approximations in particular cases of projective, toroidal or apex graphs; it is a qualitative improvement over previously published algorithms that constructed low-crossing-number drawings of embeddable graphs without giving any approximation guarantees. No constant factor approximation algorithms for the crossing number problem over comparably rich classes of graphs are known to date.

We consider the problem of computing a crossing minimum drawing of a given planar graph G = (V, E) augmented by a star, i.e., an additional vertex v together with its incident edges Ev = {(v, u) | u ∊ V}, in which all crossings involve Ev. Alternatively, the problem can be stated as finding a planar embedding of G, in which the given star can be inserted requiring the minimum number of crossings. This is a generalization of the crossing minimum edge insertion problem [15], and can help to find improved approximations for the crossing minimization problem. Indeed, in practice, the algorithm for the crossing minimum edge insertion problem turned out to be the key for obtaining the currently strongest approximate solutions for the crossing number of general graphs. The generalization considered here can lead to even better solutions for the crossing minimization problem. Furthermore, it offers new insight into the crossing number problem for almost-planar and apex graphs. It has been an open problem whether the star insertion problem is polynomially solvable. We give an affirmative answer by describing the first efficient algorithm for this problem. This algorithm uses the SPQR-tree data structure to handle the exponential number of possible embeddings, in conjunction with dynamic programming schemes for which we introduce partitioning cost subproblems.

Given an undirected graph G = (V, E) with edge weights and a positive integer number k, the k-Cardinality Tree problem consists of finding a subtree T of G with exactly k edges and the minimum possible weight. Many algorithms have been proposed to solve this NP-hard problem, resulting in mainly heuristic and metaheuristic approaches. In this paper we present an exact ILP-based algorithm using directed cuts. We mathematically compare the strength of our formulation to the previously known ILP formulations of this problem, and give an extensive study on the algorithm's practical performance compared to the state-of-the-art metaheuristics. In contrast to the widespread assumption that such a problem cannot be efficiently tackled by exact algorithms for medium and large graphs (between 200 and 5000 nodes), our results show that our algorithm not only has the advantage of proving the optimality of the computed solution, but also often outperforms the metaheuristic approaches in terms of running time.

We define the concept of crossing numbers for simultaneous graphs by extending the crossing number problem of traditional graphs. We discuss differences to the traditional crossing number problem, and give an NP-completeness proof and lower and upper bounds for the new problem. Furthermore, we show how existing heuristic and exact algorithms for the traditional problem can be adapted to the new task of simultaneous crossing minimization, and report on a brief experimental study of their implementations.