Algorithms and Complexity for Edge-Set Switching in Graphs

Abstract

A switch graph is a graph with a variable edge set controlled by a collection of switches. Each switch has several positions, each corresponding to a subset of edges. A configuration selects one position per switch, which results in a simple graph where the edges are the union of the selected edge sets. This framework gives rise to a variety of switching problems, where the objective is to find a configuration such that the resulting graph satisfies a specified property. Several variants of these problems with different structural constraints on the switch graph have been studied in the literature. This thesis focuses on connectivity-related switching problems, such as finding a configuration that yields a connected graph (global connectivity) or one that connects a specific pair of vertices (s-t-connectivity). We combine existing results with new complexity-theoretic insights and investigate how structural restrictions on switches affect computational hardness. Our results include a strong complexity dichotomy for s-t-connectivity and a polynomial-time algorithm for global connectivity based on matroid theory. Additionally, we introduce a weighted variant of the problem and analyze its complexity, particularly from a parameterized complexity perspective. For several restricted classes of switches, we establish W[1]-hardness parameterized by the maximum allowed weight of the solution. On the other hand, we present a fixed-parameter tractable algorithm using dynamic programming over tree decompositions.