A Diametral Path through Streams and Forbidden Patterns

Abstract

Networks are found in many scenarios: as a model for roads, social contacts, or the internet. Analysing a network is often challenging due to the size of the network. Computers can help using computation and fast algorithms. But which algorithms are suited to analyse which type of network? To this end, we study different properties of networks and several mathematical problems that arise from network analysis. We abstract networks to graphs, broadly used mathematical models of networks. For many problems it has been shown that no fast algorithms can exist on general graphs. But, this is an incomplete view of the algorithmic landscape: for a simple graph it can be possible to design an efficient algorithm. Which properties must the graph have so that we can find fast algorithms? An example of such a property that we study is that the graph does not contain a certain pattern H, a so-called forbidden pattern. This gives knowledge about the structure of the graph that can be used in an algorithm. For this property we work out in detail the landscape of the Diameter problem on H-subgraph-free graphs, where we obtain a dichotomy depending on the forbidden pattern(s) H. We further study the landscape of Diameter on H-free graphs, where the pattern H does not occur as an induced subgraph. Here, we come close to a dichotomy but leave a few open cases. We investigate these cases further by defining a more specific problem-variant that we call dmax-Diameter. We show for most open cases that dmax-Diameter can be solved in linear time. For H-free graphs we also study the landscape of the Subset Vertex Cover problem, a variant of the well-known Vertex Cover problem, and we show that Subset Vertex Cover is NP-complete for a class of graphs where Vertex Cover can be solved in polynomial time. Next to this, we provide several polynomial-time algorithms for the Subset Vertex Cover problem for some specific classes of H-free graphs. We also study the streaming paradigm, where the graph is presented to us in a stream, and memory-use is a limiting factor instead of computation time. The main challenge of this paradigm is that information in the stream is presented linearly and saving information quickly exceeds acceptable memory limits. For this paradigm we explore the landscape of the Diameter problem from a parameterized and structural perspective, showing that bounded vertex cover number is likely to be at the frontier of parameters useful for computing Diameter in this paradigm. We also study the Independent Set problem for streams of geometric objects like unit-height rectangles and line segments, and analyse in detail which form the objects in the stream should have to solve the problem using little memory. Here, we conclude that although interval streams admit efficient algorithms, several generalizations of intervals do not admit efficient algorithms for Independent Set. On the positive side, we show that a stream of unit-height rectangles admits an efficient approximation algorithm.