The anti-Ramsey numbers are a fundamental notion in graph theory, introduced in 1978, by Erdős, Simonovits and Sós. For given graphs G and H the anti-Ramsey number ar ( G , H ) is defined to be the maximum number k such that there exists an assignment of k colors to the edges of G in which every copy of H in G has at least two edges with the same color. Usually, combinatorists study extremal values of anti-Ramsey numbers for various classes of graphs. There are works on the computational complexity of the problem when H is a star. Along this line of research, we study the complexity of computing the anti-Ramsey number ar ( G , P k ) , where P k is a path of length k . First, we observe that when k is close to n (the number of vertices in G ), the problem is hard; hence, the challenging part is the computational complexity of the problem when k is a fixed constant. We provide a characterization of the problem for paths of constant length. Our first main contribution is to prove that computing ar ( G , P k ) for every integer k ≥ 3 is NP-hard. We obtain this by providing several structural properties of such coloring in graphs. We also study the exact complexity of the precolored version and show that there is no subexponential algorithm for the problem unless ETH fails for any fixed constant k .

We prove that the distance-r dominating set, distance-r connected dominating set, distance-r vertex cover, and distance-r connected vertex cover problems admit constant factor approximations in the CONGEST model of distributed computing in a constant number of rounds on classes of sparse high-girth graphs. In this paper, sparse means bounded expansion, and high-girth means girth at least 4r+2. Our algorithm is quite simple; however, the proof of its approximation guarantee is non-trivial. To complement the algorithmic results, we show tightness of our approximation by providing a loosely matching lower bound on rings. Our result is the first to show the existence of constant-factor approximations in a constant number of rounds in non-trivial classes of graphs for distance-r covering problems.

Airline companies are currently investigating means to improve in-flight services for passengers. Given emerging Air-to-Ground (A2G) communication technologies and the high desire of passengers for in-flight services, the servers providing in-flight services can be moved from the airplane to Data Centers (DCs) on the ground. In this scenario, network nodes (airplanes) demanding network services move over a ground core network. Therefore, the selection of DCs to connect to, as well as the underlying routing decisions are challenging. In particular, to keep a low-delay in-flight connection during the flight, airplanes connections can be reconfigured from a DC to another one, which comes at a delay cost. This paper presents a formal model for the in-flight service provisioning problem, also as an Integer Linear Program (ILP). We show that the problem is NP-hard and hence propose an efficient online heuristic, HOMA, which addresses the above challenges in polynomial time. HOMA models the problem as a dynamic matching with special properties, and then efficiently solves it by a transformation into the shortest-path routing problem. Our simulation results indicate that HOMA can achieve near-optimal performance and outperform the baseline and state-of-the-art algorithms by up to 15% while reducing the runtime from hours to seconds.

The anti-Ramsey numbers are a fundamental notion in graph theory, introduced in 1978, by Erdös, Simonovits and Sós. For given graphs G and H the anti-Ramsey number ar(G,H) is defined to be the maximum number k such that there exists an assignment of k colors to the edges of G in which every copy of H in G has at least two edges with the same color. Usually, combinatorists study extremal values of anti-Ramsey numbers for various classes of graphs. There are works on the computational complexity of the problem when H is a star. Along this line of research, we study the complexity of computing the anti-Ramsey number ar(G,P_k), where P_k is a path of length k. First, we observe that when k is close to n, the problem is hard; hence, the challenging part is the computational complexity of the problem when k is a fixed constant. We provide a characterization of the problem for paths of constant length. Our first main contribution is to prove that computing ar(G,P_k) for every integer k > 2 is NP-hard. We obtain this by providing several structural properties of such coloring in graphs. We investigate further and show that approximating ar(G,P₃) to a factor of n^{-1/2 - ε} is hard already in 3-partite graphs, unless P = NP. We also study the exact complexity of the precolored version and show that there is no subexponential algorithm for the problem unless ETH fails for any fixed constant k. Given the hardness of approximation and parametrization of the problem, it is natural to study the problem on restricted graph families. Along this line, we first introduce the notion of color connected coloring, and, employing this structural property, we obtain a linear time algorithm to compute ar(G,P_k), for every integer k, when the host graph, G, is a tree.

Abstract We initiate the study of a fundamental combinatorial problem: Given a capacitated graph $$G=(V,E)$$ G=(V,E) , find a shortest walk (“route”) from a source $${s\in V}$$ s∈V to a destination $$t\in V$$ t∈V that includes all vertices specified by a set $$WP \subseteq V$$ WP⊆V : the waypoints. This Waypoint Routing Problem finds immediate applications in the context of modern networked systems. Our main contribution is an exact polynomial-time algorithm for graphs of bounded treewidth. We also show that if the number of waypoints is logarithmically bounded, exact polynomial-time algorithms exist even for general graphs. Our two algorithms provide an almost complete characterization of what can be solved exactly in polynomial time: we show that more general problems (e.g., on grid graphs of maximum degree 3, with slightly more waypoints) are computationally intractable.

We consider the SDN network update problem in which a controller wants to update the routes of k (unsplittable) flows from their old paths to the new paths, consistently, i.e., without temporary congestion. As updates communicated by the controller take effect asynchronously, the challenge is to perform these updates fast, i.e., using a minimal number of rounds (controller interactions). We present the first fast, i.e., polynomial-time solution for scheduling such congestion-free network updates, for two flows and in the node ordering model. We also show that the problem is already NP-hard for six flows. We complement our formal results with simulations.

We study the version of the k -disjoint paths problem where k demand pairs ( s 1 , t 1 ) , …, ( s k , t k ) are specified in the input and the paths in the solution are allowed to intersect, but such that no vertex is on more than c paths. We show that on directed acyclic graphs the problem is solvable in time n O ( d ) if we allow congestion k − d for k paths. Furthermore, we show that, under a suitable complexity theoretic assumption, the problem cannot be solved in time f ( k ) n o ( d / log ⁡ d ) for any computable function f .

The Minimum Dominating Set (MDS) problem is a fundamental and challenging problem in distributed computing. While it is well known that minimum dominating sets cannot be well approximated locally on general graphs, in recent years there has been much progress on computing good local approximations on sparse graphs and in particular on planar graphs. In this article, we study distributed and deterministic MDS approximation algorithms for graph classes beyond planar graphs. In particular, we show that existing approximation bounds for planar graphs can be lifted to bounded genus graphs and more general graphs, which we call locally embeddable graphs, and present (1) a local constant-time, constant-factor MDS approximation algorithm on locally embeddable graphs, and (2) a local O (log * n )-time (1+ϵ)-approximation scheme for any ϵ > 0 on graphs of bounded genus. Our main technical contribution is a new analysis of a slightly modified variant of an existing algorithm by Lenzen et al. [21]. Interestingly, unlike existing proofs for planar graphs, our analysis does not rely on direct topological arguments but on combinatorial density arguments only.

Changing a given configuration in a graph into another one is known as a reconfiguration problem. Such problems have recently received much interest in the context of algorithmic graph theory. We initiate the theoretical study of the following reconfiguration problem: How to reroute k unsplittable flows of a certain demand in a capacitated network from their current paths to their respective new paths, in a congestion-free manner? This problem finds immediate applications, e.g., in traffic engineering in computer networks. We show that the problem is generally NP-hard already for k=2 flows, which motivates us to study rerouting on a most basic class of flow graphs, namely DAGs. Interestingly, we find that for general k, deciding whether an unsplittable multi-commodity flow rerouting schedule exists, is NP-hard even on DAGs. Our main contribution is a polynomial-time (fixed parameter tractable) algorithm to solve the route update problem for a bounded number of flows on DAGs. At the heart of our algorithm lies a novel decomposition of the flow network that allows us to express and resolve reconfiguration dependencies among flows.

\noindent We provide a new constant factor approximation algorithm for the (connected) \mboxdistance- r dominating set problem on graph classes of bounded expansion. Classes of bounded expansion include many familiar classes of sparse graphs such as planar graphs and graphs with excluded (topological) minors, and notably, these classes form the most general subgraph closed classes of graphs for which a sequential constant factor approximation algorithm for the distance- r dominating set problem is currently known. Our algorithm can be implemented in the \congestbc model of distributed computing and uses $Øof(r^2 łog n)$ communication rounds. % Our techniques, which may be of independent interest, are based on a distributed computation of sparse neighborhood covers of small radius on bounded expansion classes. We show how to compute an r -neighborhood cover of radius~$2r$ and overlap $f(r)$ on every class of bounded expansion in $Øof(r^2łog n)$ communication rounds for some function~ f .% in the \congestbc model. % Finally, we show how to use the greater power of the łocal model to turn any distance- r dominating set into a constantly larger connected distance- r dominating set in $3r+1$ rounds on any class of bounded expansion. Combining this algorithm, e.g., with the constant factor approximation algorithm for dominating sets on planar graphs of Lenzen et al.\ gives a constant factor approximation algorithm for connected dominating sets on planar graphs in a constant number of rounds in the łocal model, where the approximation ratio is only $6$ times larger than that of Lenzen et al.'s algorithm.

The Minimum Dominating Set (MDS) problem is not only one of the most fundamental problems in distributed computing, it is also one of the most challenging ones. While it is well-known that minimum dominating sets cannot be approximated locally on general graphs, over the last years, several breakthroughs have been made on computing local approximations on sparse graphs.

In cops and robber games a number of cops tries to capture a robber in a graph. A variant of these games on undirected graphs characterises tree width by the least number of cops needed to win. We consider cops and robber games on digraphs and width measures (such as DAG-width, directed tree width or D-width) corresponding to them. All of them generalise tree width and the game characterising it. For the DAG-width game we prove that the problem to decide the minimal number of cops required to capture the robber (which is the same as deciding DAG-width), is PSPACE-complete, in contrast to most other similar games. We also show that the cop-monotonicity cost for directed tree width games cannot be bounded by any function. As a consequence, D-width is not bounded in directed tree width, refuting a conjecture by Safari. A large number of directed width measures generalising tree width has been proposed in the literature. However, only very little was known about the relation between them, in particular about whether classes of digraphs of bounded width in one measure have bounded width in another. In this paper we establish an almost complete order among the most prominent width measures with respect to mutual boundedness.