Graph width parameters: from structure to algorithm

Most discrete optimization problems are computationally hard. To overcome this, we may restrict the input and ask: Which input restrictions lead to "fast" algorithms?

The input is often described by a graph and knowing that a graph is "easily decomposable" can be highly useful for designing efficient algorithms for many well-known optimization problems.<br><br>A graph width parameter p is a function that assigns a number to each graph G, where a small value of p(G) usually means that the graph G is "easily decomposable" with respect to the parameter p. We use graph width parameters to show that certain graphs are "easily decomposable" with respect to specific graph width parameters and design "fast" algorithms for otherwise "hard" problems.<br><br>In Chapter 2 and Chapter 3 we give basic definitions and background for the graph width parameters that are studied in this thesis, which are mim-width, sim-width, layered tree-independence number and the related notion of fractional tree-independence-number-fragility.