For a graph G, a set of vertices S is an efficient total k-dominating set (ETkD set) if every vertex of G is adjacent to exactly k vertices in S. A torus graph is the Cartesian product Cm□Cn of two cycles.In this work, we characterize all torus graphs with an ETkD set for k = 1, 2, 3. In particular, we prove following conjecture of Kuziak, Peterin, and Yero (2014): Cm□Cn has an ET1D set if and only if m ≡ n ≡ 0 (mod 4). This allows us to determine the total domatic number and the injective chromatic number of all torus graphs. Additionally, we characterize the signed total Roman domatic number of 4-regular graphs in terms of ET1D and ET2D sets, and consequently obtain exact values for all torus graphs.

k -slow burning is a model for contagion in social networks. In this model, given an undirected graph G in every time step , first every burning vertex spreads the fire to up to k of its neighbours, before second one additional source of fire is ignited. The k -slow burning number, denoted by b s ( k , G ) , is the minimum number of time steps needed until the whole graph is burning. This model can be seen as a combination of the classic graph burning problem and the much older ( k -)broadcasting problem. We prove NP -hardness of the k -slow burning problem for every fixed k on path forests, spider graphs and most notably the class of graphs of radius 1, where normal graph burning is solvable in polynomial time. Furthermore, we show that among all connected graphs on n vertices, the k -slow burning number of the star graph, b s ( k , S n − 1 ) , is maximal for k ∈ { 1 , 2 } and asymptotically maximal for fixed k ≥ 3 . This observation motivates a generalisation of the burning number conjecture for k -slow burning. Finally, we give a 3 / 2 -approximation for the k -slow burning problem on path forests and a 2-approximation on trees .

ABSTRACT The ‐matching problem is a well‐known generalization of the classical matching problem with various applications in operations research and computer science. Given an undirected graph, each vertex has a capacity , indicating the maximum number of times it can be matched, while edges can also be used multiple times. The problem is solvable in polynomial time and has many real‐world applications. In some of them, a feasible matching must exactly satisfy the capacities , leading to the so‐called perfect ‐matching problem. Typically, the capacities are assumed to be fixed and known. However, in practice, these capacities often face uncertainties, such as worker availability or customer demand fluctuations. This article analyses a robust variant of both the ‐matching and perfect ‐matching problems, accounting for such capacity uncertainties, termed the Directed Robust ‐Matching Problem (DRU). We study the computational complexity of this problem across different classes of graphs, providing insights into its tractability for potential applications.

In light of the recent pandemic and the shortage of vaccinations during their roll-out, questions arose regarding the best strategy to achieve immunity throughout the population by adjusting the time gap between the two necessary vaccination doses. This strategy has already been studied from different angles by various researches. However, the deliveries of vaccination doses also proved to be highly uncertain, with manufacturers not being able to deliver the promised amount of vaccines on time. In this paper, we study the robust version of this problem and its generalization to matchings on arbitrary graphs. By exploring the problem, we show that it is weakly NP-hard for a constant number of scenarios and strongly NP-hard else. Further, we propose a pseudo-polynomial algorithm for the weakly NP-hard subproblem with a constant number of scenarios and time between both doses. Finally, we perform computational experiments to better understand the behavior of the problem.

Abstract In this article, we study robust transshipment under consistent flow constraints. We consider demand uncertainty represented by a finite set of scenarios and characterize a subset of arcs as so‐called fixed arcs. In each scenario, we require an integral flow that satisfies the respective flow balance constraints. In addition, on each fixed arc, we require equal flow for all scenarios. The objective is to minimize the maximum cost occurring among all scenarios. We show that the problem is strongly ‐complete on acyclic digraphs by a reduction from the ‐Sat problem. Furthermore, we prove that the problem is weakly ‐complete on series‐parallel digraphs by a reduction from a special case of the Partition problem. If in addition the number of scenarios is constant, we observe the pseudo‐polynomial‐time solvability of the problem. We provide poly‐nomial‐time algorithms for three special cases on series‐parallel digraphs. Finally, we present a polynomial‐time algorithm for pearl digraphs.

We present an iterative algorithm to compute feasible solutions in reasonable running time to quadratically constrained quadratic programs (QCQPs), which form a challenging class of nonconvex continuous optimization. This algorithm is based on a mixed-integer linear program (MILP) which is a restriction of the original QCQP obtained by discretizing all quadratic terms. In each iteration, this MILP restriction is solved to get a feasible QCQP solution. Since the quality of this solution heavily depends on the chosen discretization of the MILP, we iteratively adapt the discretization values based on the MILP solution of the previous iteration. To maintain a reasonable problem size in each iteration of the algorithm, the discretization sizes are fixed at predefined values. Although our algorithm did not always yield good feasible solutions on arbitrary QCQP instances, an extensive computational study on almost 1300 test instances of two different problem classes - box-constrained quadratic programs with complementarity constraints and disjoint bilinear programs, demonstrates the effectiveness of our approach. We compare the quality of our solutions against those from heuristics and local optimization algorithms in two state-of-the-art commercial solvers and observe that on one instance class we clearly outperform the other methods whereas on the other class we obtain competitive results.

Techniques like Network Functions Virtualisation and Software Defined Networking provide a new dimension of flexibility in the deployment, operation and maintenance of telecommunication networks. They also enable the realisation of multiple virtual networks (multi-tenancy) on a common substrate network infrastructure. Provisioning such virtual networks requires efficient resource allocation mechanisms so that the utility of the substrate infrastructure provider can be maximised. In this work, we first outline a mathematical model for the general network slice design problem and extend it to cope with traffic uncertainties. We employ the Γ-robust uncertainty set [1], [2] to model the uncertainties in the traffic demands. Furthermore, we add survivability aspects to our model by protecting the network slice against single substrate network element (node/link) failures. Finally, both survivability and traffic robustness approaches are considered simultaneously and we present two different optimisation models. A performance evaluation is carried out comparing the different robust and survivable models with their non-robust non-survivable counterpart using network topology examples from SNDlib.

Flexgrid optical networking technology allows for a more flexible consumption of bandwidth. The spectrum allocation problem consists of the conflict‐free assignment of consecutive spectrum space of different sizes to lightpaths. In this article, we study the computational complexity of spectrum allocation with and without demand uncertainty. First, it is shown that the problem becomes already NP‐hard for cases where wavelength assignment is still polynomial time solvable. Next, five different ways to define the robust counterpart are compared. It is shown (amongst others) that on a single network edge, the two least efficient models are less computationally demanding than the other variants. A computational study using comparable integer linear programming formulations reveals that the additional slots required by these models directly depend on the restrictions of the employed technology. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(4), 342–359 2017

The budgeted minimum cost flow problem (BMCF(K)) with unit upgrading costs extends the classical minimum cost flow problem by allowing one to reduce the cost of at most K arcs. In this article, we consider complexity and algorithms for the special case of an uncapacitated network with just one source. By a reduction from 3‐SAT we prove strong ‐completeness and inapproximability, even on directed acyclic graphs. On the positive side, we identify three polynomially solvable cases: on arborescences, on so‐called tree‐like graphs, and on instances with a constant number of sinks. Furthermore, we develop dynamic programs with pseudo‐polynomial running time for the BMCF(K) problem on (directed) series‐parallel graphs and (directed) graphs of bounded treewidth. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 67–82 2017

In this paper, we extend our former investigation on conceiving reliable fixed point-to-point wireless networks under outage probability constraints. We consider the problem of determining the minimum cost bandwidth assignment of a network, while guaranteeing a reliability level of the solution. If the optimal bandwidth assignment and routing of traffic demands are accomplished, the reliability criterion requires that network flows remain feasible with high probability, regarding that the performance of microwave links is prone to variations due to external factors, e.g., weather. We introduce a chance-constrained programming approach to tackle this problem and we present reformulations to standard integer linear programming models, including a budget-constrained formulation. To improve the solving performance, we propose new valid inequalities and a primal heuristic. Computational results present a performance analysis of the valid inequalities and the heuristic. Further, the outperformance of the novel model compared to more traditional approaches is documented.

Abstract Traffic in communication networks fluctuates heavily over time. Thus, to avoid capacity bottlenecks, operators highly overestimate the traffic volume during network planning. In this article we consider telecommunication network design under traffic uncertainty, adapting the robust optimization approach of Bertsimas and Sim [Oper Res 52 (2004), 35–53]. We present two different mathematical formulations for this problem, provide valid inequalities, study the computational implications, and evaluate the realized robustness. To enhance the performance of the mixed‐integer programming solver, we derive robust cutset inequalities generalizing their deterministic counterparts. Instead of a single cutset inequality for every network cut, we derive multiple valid inequalities by exploiting the extra variables available in the robust formulations. We show that these inequalities define facets under certain conditions and that they completely describe a projection of the robust cutset polyhedron if the cutset consists of a single edge. For realistic networks and live traffic measurements, we compare the formulations and report on the speed‐up achieved by the valid inequalities. We study the “price of robustness” and evaluate the approach by analyzing the real network load. The results show that the robust optimization approach has the potential to support network planners better than present methods. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013

In this note, we give a proof that several vertex ordering problems can be solved in O ∗(2 n ) time and O ∗(2 n ) space, or in O ∗(4 n ) time and polynomial space. The algorithms generalize algorithms for the Travelling Salesman Problem by Held and Karp (J. Soc. Ind. Appl. Math. 10:196–210, 1962) and Gurevich and Shelah (SIAM J. Comput. 16:486–502, 1987). We survey a number of vertex ordering problems to which the results apply.

We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential-time algorithms using exponential space or using only polynomial space. We first report on an implementation of a dynamic programming algorithm for computing the treewidth of a graph with running time O *(2 n ). This algorithm is based on the old dynamic programming method introduced by Held and Karp for the Traveling Salesman problem. We use some optimizations that do not affect the worst case running time but improve on the running time on actual instances and can be seen to be practical for small instances. We also consider the problem of computing Treewidth under the restriction that the space used is only polynomial and give a simple O *(4 n ) algorithm that requires polynomial space. We also show that with a more complicated algorithm using balanced separators, Treewidth can be computed in O *(2.9512 n ) time and polynomial space.

Robust optimization is an emerging field in telecommunication network design which takes future traffic uncertainty into account. This yields optimal robust network designs which are optimal for all traffic realizations within a pre-defined set of uncertainty. In 2003, Bertsimas and Sim have introduced an adjustable uncertainty set for general optimization problems which preserves the computational complexity of the original non-robust problem. Recently, Koster et al. have applied this approach to network design problems. In this paper, we consider this so-called Γ-robust network design problem. We investigate the importance of statistical input data analysis to determine reasonable parameter settings for robust network planning. Using detailed real-life traffic measurements of two backbone networks (Abilene and GEANT), we determine optimal robust network designs for 495 different parameter settings per network. Afterwards, we evaluate the realized robustness (i.e., the percentage of supported traffic matrices) w.r.t. the planning data and a larger set of historical data to simulate uncertain future traffic.

In this paper, we investigate on conceiving reliable fixed broadband wireless networks under outage probability constraints. We introduce a joint model of data routing and bandwidth assignment that minimizes the total renewal fees of licenses. This problem differs from classical capacity planning since the capacity of microwave links is prone to variations and, hence, we must deal with random parameters to guarantee a desirable reliability level of the solution. We introduce a chance-constrained programming approach to tackle this problem and derive integer linear programming (ILP) counterparts. We further propose cutset-based valid inequalities to enhance the performance of ILP solvers. Computational results illustrate the price of reliability and present a comparative study on the performance of the different formulations.

In this article, we study capacitated network design problems. We unify and extend polyhedral results for directed, bidirected, and undirected link capacity models. Valid inequalities based on a network cut are known to be strong in several special cases. We show that regardless of the link model, facets of the polyhedra associated with such a cut translate to facets of the original network design polyhedra if the two subgraphs defined by the network cut are (strongly) connected. Our investigation of the facial structure of the cutset polyhedra allows to complement existing polyhedral results for the three variants by presenting facet-defining flow-cutset inequalities in a unifying way. In addition, we present a new class of facet-defining inequalities, showing as well that flow-cutset inequalities alone do not suffice to give a complete description for single-commodity, single-module cutset polyhedra in the bidirected and undirected case – in contrast to a known result for the directed case. The practical importance of the theoretical investigations is highlighted in an extensive computational study on 27 instances from the Survivable Network Design Library (SNDlib). © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(2), 141–156 2011

In this paper we present a new technique for computing lower bounds for graph treewidth. Our technique is based on the fact that the treewidth of a graph G is the maximum order of a bramble of G minus one. We give two algorithms: one for general graphs, and one for planar graphs. The algorithm for planar graphs is shown to give a lower bound for both the treewidth and branchwidth that is at most a constant factor away from the optimum. For both algorithms, we report on extensive computational experiments that show that the algorithms often give excellent lower bounds, in particular when applied to (close to) planar graphs.

There are many graph problems that can be solved in linear or polynomial time with a dynamic programming algorithm when the input graph has bounded treewidth. For combinatorial optimization problems, this is a useful approach for obtaining fixed-parameter tractable algorithms. Starting from trees and series-parallel graphs, we introduce the concepts of treewidth and tree decompositions, and illustrate the technique with the Weighted Independent Set problem as an example. The paper surveys some of the latest developments, putting an emphasis on applicability, on algorithms that exploit tree decompositions, and on algorithms that determine or approximate treewidth and find tree decompositions with optimal or close to optimal treewidth. Directions for further research and suggestions for further reading are also given.

Several sets of reductions rules are known for preprocessing a graph when computing its treewidth. In this paper we give reduction rules for a weighted variant of treewidth, motivated by the analysis of algorithms for probabilistic networks. We present two general reduction rules that are safe for weighted treewidth. They generalise many of the existing reduction rules for treewidth. Experimental results show that these reduction rules can significantly reduce the problem size for several instances of real-life probabilistic networks.

Currently, the most efficient algorithm for inference with a probabilistic network builds upon a triangulation of a network's graph. In this paper, we show that pre-processing can help in finding good triangulations for probabilistic networks, that is, triangulations with a maximum clique size as small as possible. We provide a set of rules for stepwise reducing a graph, without losing optimality. This reduction allows us to solve the triangulation problem on a smaller graph. From the smaller graph's triangulation, a triangulation of the original graph is obtained by reversing the reduction steps. Our experimental results show that the graphs of some well-known real-life probabilistic networks can be triangulated optimally just by preprocessing; for other networks, huge reductions in their graph's size are obtained.

Abstract In this paper, we describe a computational study to solve hard partial constraint satisfaction problems (PCSPs) to optimality. The PCSP is a general class of problems that contains a diversity of problems, such as generalized subgraph problems, MAX‐SAT, Boolean quadratic programs, and assignment problems like coloring and frequency planning. We present a dynamic programming algorithm that solves PCSPs based on the structure (tree decomposition) of the underlying constraint graph. With the use of dominance and bounding techniques, we are able to solve small and medium‐size instances of the problem to optimality and to obtain good lower bounds for large‐size instances within reasonable time and memory limits. © 2002 Wiley Periodicals, Inc.