Plane spanners of bounded degree are efficient communication backbones for networks. However, while existing spanners provide attractive guarantees in the worst-case, they are demand-oblivious and may hence be suboptimal under specific traffic demands. This paper thus initiates the study of demand-aware plane spanners of bounded degree, geometric spanners whose topology accounts for the actual communication traffic. We show that demand-awareness can significantly reduce the distance travelled per bit, and present a spanner which exploits topological flexibilities to account for the demand, without losing desirable guarantees of demand-oblivious spanners, namely constant stretch and degree. We complement our analytical results with heuristic improvements and a simulation study exploring the benefits of demand-awareness under realistic traffic traces.

To achieve fast recovery from link failures, most modern communication networks feature fully decentralized fast re-routing mechanisms. These re-routing mechanisms rely on pre-installed static re-routing rules at the nodes (the routers), which depend only on local failure information, namely on the failed links incident to the node. Ideally, a network is perfectly resilient: the re-routing rules ensure that packets are always successfully routed to their destinations as long as the source and the destination are still physically connected in the underlying network after the failures. Unfortunately, there are examples where achieving perfect resilience is not possible. Surprisingly, only very little is known about the algorithmic aspect of when and how perfect resilience can be achieved. We investigate the computational complexity of analyzing such local fast re-routing mechanisms. Our main result is a negative one: we show that even checking whether a given set of static re-routing rules ensures perfect resilience is coNP-complete. Additionally, we investigate other fundamental variations of the problem. In particular, we show that our coNP-completeness proof also applies to scenarios where the re-routing rules have specific patterns (known as skipping in the literature). On the positive side, for scenarios where nodes do not have information about the link from which a packet arrived (the so-called in-port), we present a linear-time algorithm to realize perfect resilience whenever possible (which we show can also be determined in linear time).

Payment channel networks (PCNs) are among the most promising solutions to the scalability issues in permissionless blockchains , allowing parties to pay each other off-chain through a path of payment channels (PCs). However, the cost of routing transactions is proportional to the number of intermediaries since each charges a fee. Analogous to other networks, malicious intermediaries on the path can lead to security/privacy threats. Virtual channels (VCs), i.e., bridges over PC paths, mitigate the above PCN issues: Intermediaries participate only in the VC setup but in no future VC payments. However, creating a VC has a cost that must be paid out of the bridged PCs’ balance. Currently, we are missing guidelines on how/where to set up VCs. Ideally, VCs should minimize transaction costs while mitigating security and privacy threats from on-path adversaries. In this work, we address for the first time the VC setup problem, formalizing it as an optimization problem . We present an integer linear program (ILP) computing the globally optimal VC setup strategy in terms of cost, security, and privacy. We accompany this expensive ILP with a fast, greedy algorithm . Our model and algorithms can be used with any on-path adversary whose strategy can be expressed as a set of corrupted nodes. We evaluate the greedy algorithm over a snapshot of the Lightning Network (LN), the largest Bitcoin-based PCN. Our results confirm that the greedy strategy minimizes costs while protecting against security and privacy threats and may serve the LN community as guidelines for VC deployment.

Given the increasingly stringent requirements on the performance and efficiency of communication networks, over the last years, great efforts have been made to render networks more flexible and programmable. In particular, modern networks support a flexible rerouting of flows, e.g., depending on the dynamically changing traffic or network conditions. However, the underlying algorithmic problems are still not well-understood today.In this paper, we revisit the k-Network Flow Update problem that asks for a schedule to reroute k unsplittable flows from their current paths to the given new paths, in a congestion-free manner in a capacitated network. We show that the problem is already NP-hard for three acyclic flows on simple directed graphs. Our main contribution is an efficient algorithm for sparse networks; specifically the algorithm is fixed parameter tractable in the number of flows and the treewidth of a graph that is the union of all flows. Our results also settle the open complexity question in the literature.

We study four NP-hard optimal seat arrangement problems which each have as input a set of n agents, where each agent has cardinal preferences over other agents, and an n-vertex undirected graph (called the seat graph). The task is to assign each agent to a distinct vertex in the seat graph such that either the sum of utilities or the minimum utility is maximized, or it is envy-free or exchange-stable. Aiming at identifying hard and easy cases, we extensively study the algorithmic complexity of the four problems by looking into natural graph classes for the seat graph (e.g., paths, cycles, stars, or matchings), problem-specific parameters (e.g., the number of non-isolated vertices in the seat graph or the maximum number of agents towards whom an agent has non-zero preferences), and preference structures (e.g., non-negative or symmetric preferences). For strict preferences and seat graphs with disjoint edges and isolated vertices, we correct an error in the literature and show that finding an envy-free arrangement remains NP-hard in this case.

The under-representation of women in IT has multiple possible causes, ranging from sociocultural aspects to individual dispositions and social attribution. This full research to practice paper explores secondary school students' (age 12–15) stereotypical perspectives of computer scientists and possible ways to challenge them. The major goal is to let young students form a more accurate concept of a computer science professionals by alleviating distorted images, often transmitted through media and the environment. Students who might not think of themselves as fitting in the prevalent stereotype of a computer scientist and may even lose interest in the field. Consequently, our approach challenges stereotypes in order to make any effort to raise young students' interest in computer science and in pursuing careers in this field. As part of this endeavor, we analyzed the drawings and descriptions of IT professionals made by 87 students aged 12–15 to determine what sets of preconceived perspectives and misconceptions are present in the learners' minds regarding persons in the IT profession. Our results have shown that that stereotypical views on IT actually exist in students' mindsets, but are subject to change when systematically challenged in a friendly and safe atmosphere. Aside of the scientific contribution, the paper aims to inspire and support educators in their efforts to help women and underrepresented groups in computing outgrow inaccurate stereotypes and to uncover young students' potential interest in the field. With this we aim to contribute to overcoming the gender imbalance and foster more equality in the occupational field of information technologies. Strategically, by creating a more sensitive, diverse and harmonious future that computer scientists knowingly and unknowingly co-shape.