Dissertation theses
Parameterized complexity of problems of network design and analysis
Supervisor
Level
Topic of dissertation thesis
Topic description
Network analysis is a fundamental part of combinatorial optimization. The networks examined can represent, e.g., telecommunication networks, power grids, water pipelines, traffic networks, or relations between people.
The most important properties of the networks are, e.g., how efficiently can the network be traversed and how immune the network is to various kinds of disruptions. Naturally, the question how well is the network currently performing is connected with the question on how to improve its performance or how to propose a better performing network, i.e., with network design.
While most of the problems in the aread are NP-hard, they can be often effectively solved if the instance in question poses favorable structure.
The main toolbox to analyze the problems from such a perspective will be the parameterized (multivariate) complexity with a wide variate of approaches to design efficient scalable algorithms. An accent will be given to applicability of preprocessing methods such as (loosy) kernelization. The parameters considered will range from the standard budget related over problem specific to structural parameters.
Bachelor theses
Plugin for MediaWiki
Author
Petr Bárta
Year
2013
Type
Bachelor thesis
Supervisor
RNDr. Ondřej Suchý, Ph.D.
Reviewers
Ing. František Štampach, Ph.D.
Department
Extension of Game-portal Gamesites.cz
Author
Jiří Levý
Year
2013
Type
Bachelor thesis
Supervisor
RNDr. Ondřej Suchý, Ph.D.
Reviewers
Ing. František Štampach, Ph.D.
Department
FPT Algorithms for Multi-dimensional Matching
Author
Jakub Puchýř
Year
2014
Type
Bachelor thesis
Supervisor
RNDr. Ondřej Suchý, Ph.D.
Reviewers
doc. Ing. Ivan Šimeček, Ph.D.
Department
Algorithms for (NP-) Hard Problems
Author
Petr Urban
Year
2016
Type
Bachelor thesis
Supervisor
RNDr. Ondřej Suchý, Ph.D.
Reviewers
doc. Ing. Ivan Šimeček, Ph.D.
Department
Summary
This bachelor thesis deals with the Windy Postman Problem - a special case of a graph theory optimization problem - the Chinese Postman Problem. The postman's task is the same as in the traditional assignment - traverse all streets (edges of the graph) and return to the starting point (vertex). Unlike in the original task, in the WPP every undirected edge can have different value in each direction of traversal (hence the name - the streets are windy and it is easier to go with the wind than against it).
The goal of this thesis is implementation of an algorithm for this NP-hard problem. In the theoretical part the author explains the problem and its modifications, describes possibilities of practical application and means of solution. Subsequently in the practical part the author implements a C++ algorithm for a case of the problem (graph with only few undirected edges).
Exact algorithms for geodetic number and metric dimension of graphs
Author
Marek Jílek
Year
2016
Type
Bachelor thesis
Supervisor
RNDr. Ondřej Suchý, Ph.D.
Reviewers
RNDr. Tomáš Valla, Ph.D.
Department
Summary
This bachelor thesis deals with developing a parameterized algorithm searching for the minimal geodetic number of graphs with low vertex cover. A geodetic number is a cardinality of the smallest set, such that on the shortest paths between pairs of vertices contained in the set lies every vertex of the graph. At the beginning of the thesis, a few solutions of similar problems are analysed, such as a parameterized algorithm for searching a metric dimension of a graph. This paper demonstrates the use of some specific properties of bipartite graphs and graphs with low vertex cover to simplify the complexity of the algorithm. The described algorithm is implemented in C++. Using tests, the expected complexity reduction was confirmed. Therefore, this thesis proves that we can use this algorithm on the specific graphs previously mentioned with success.
Maximum Edge Coloring in Special Graph Classes
Author
Vojtěch Hruša
Year
2019
Type
Bachelor thesis
Supervisor
RNDr. Ondřej Suchý, Ph.D.
Reviewers
RNDr. Dušan Knop, Ph.D.
Department
Summary
In this thesis, maximum edge q-coloring problem is studied. The goal of the problem is to color the edges of a graph with as many colors as possible with one constraint. For each vertex v, the edges incident to v can be colored with at most q distinct colors. We first analyze known algorithms for the problem and present some of them in detail. We then show a new algorithm for trees working in linear time and a new algorithm for interval graphs working in O(n*(q+1)^p*k^(pq+1)*(q+p)^p) time, where n is the number of vertices, p is the size of a maximum clique and k is the number of colors used in an optimal solution. Finally, an implementation of the algorithm for interval graphs is also part of the thesis.
Adding a treewidth support to the Boost Graph Library
Author
Václav Král
Year
2020
Type
Bachelor thesis
Supervisor
RNDr. Ondřej Suchý, Ph.D.
Reviewers
Ing. Michal Valenta, Ph.D.
Department
Summary
The aim of this thesis is to extend the C++ Boost Graph Library (BGL) with algorithms for obtaining a tree decomposition of a graph and an example of an algorithm, that uses the tree decomposition. In this thesis the reader will get familiar with not only the algorithms and their usage, but also with the library itself. Further in this thesis the successful implementation of the algorithms is discussed, where the main focus is the compliance with conventions of BGL and rules of generic programming. The quality of implementation and possible enhancements are discussed at the end of the thesis. The result is a working extension of BGL.
Distance Edge Monitoring Set Problem with Respect to Structural Parameters
Author
Václav Lepič
Year
2022
Type
Bachelor thesis
Supervisor
RNDr. Ondřej Suchý, Ph.D.
Reviewers
doc. RNDr. Dušan Knop, Ph.D.
Department
Summary
This thesis is about the distance edge monitoring set problem. The problem is first described and then approached from a point of structural parameters.
Algorithm parameterized by vertex cover number was proposed and its correctness was proven. The algorithm was then implemented and tested.
Algorithm parameterized by the feedback edge set number was proposed, implemented, and tested.
Minimum Eccentricity Shortest Path Problem with Respect to Structural Parameters
Author
Martin Kučera
Year
2020
Type
Bachelor thesis
Supervisor
RNDr. Ondřej Suchý, Ph.D.
Reviewers
RNDr. Dušan Knop, Ph.D.
Department
Summary
The Minimum Eccentricity Shortest Path Problem consists in finding a shortest path with minimum eccentricity in a given graph. The problem is known to be NP-complete and W[2]-hard with respect to the minimum eccentricity. In this thesis, we present FPT algorithms for the problem parameterized by the maximum leaf number, neighborhood diversity, twin cover, distance to cluster, and the combination of distance to disjoint paths with the minimum eccentricity. In addition, we present an experimental evaluation of the last algorithm, which we have implemented.
Interval Graph Recognition Support for Boost Library
Author
Juraj Bielik
Year
2021
Type
Bachelor thesis
Supervisor
RNDr. Ondřej Suchý, Ph.D.
Reviewers
Ing. Jiří Novák, Ph.D.
Department
Summary
The purpose of this thesis is to extend the Boost Graph Library, which specializes in working with graph representation of data in programming language C++. Functionality for interval graph recognition and related functions is added. The reader will get familiar with libraries Boost Graph Library, Interval Container Library and algorithms Partition refinement, Lex-BFS, Chordality test, Clique Tree, Interval graph recognition and Construction of interval graph. Subsequently, the reader will be acquainted with implementation analysis of these algorithms and the structures, with heavy emphasis on generic functions’ interfaces provided to the user. A part of this work is devoted to testing of the created solution. Time complexities and possible enhancements of the implementation are discussed at the end. The result of this thesis is an usable extended functionality for Boost Graph Library which adheres to its standards.
Parameterized Algorithms for the Truncated Metric Dimension problem
Author
Jiří Jirásek
Year
2024
Type
Bachelor thesis
Supervisor
RNDr. Ondřej Suchý, Ph.D.
Reviewers
Mgr. Michal Opler, Ph.D.
Department
Summary
This thesis is directed at FPT algorithms that solve the Truncated Metric Dimension problem. Two already known algorithms solving the Metric Dimension problem are described. For the algorithm bounded by modular-width we present a simple modification for it to solve the Truncated Metric Dimension problem. As for the algorithm bounded by max leaf number, we describe the reason that prevented us from modifying the algorithm. Following that, we explain how we implemented the algorithms bounded by modular-width and show selected performance metrics.
Design and Analysis of Algorithms for Identifying Structures in Multi-Agent Systems with a Focus on Internal Minorities
Author
Šimon Brejcha
Year
2026
Type
Bachelor thesis
Supervisor
RNDr. Ondřej Suchý, Ph.D.
Reviewers
prof. RNDr. Pavel Surynek, Ph.D.
Department
Summary
An internal minority set of a graph is a subset of the vertex set of the graph, such that every vertex in it has less neighbors in it than outside of it. A maximal internal minority set is an internal minority set that is not a proper subset of any other internal minority set. In this thesis, we design and analyze two algorithms for finding the size of a smallest maximal internal minority set. The first algorithm is parametrized by max-leaf number and the other is for trees, which is a first step towards an algorithm parametrized by tree-width, a well-known and often used parameter. The algorithm for trees is implemented and experimentally tested on random trees.
Master theses
Subgraph Isomorphism Algorithm Based on Color Coding
Author
Josef Malík
Year
2016
Type
Master thesis
Supervisor
RNDr. Ondřej Suchý, Ph.D.
Reviewers
RNDr. Tomáš Valla, Ph.D.
Department
Summary
This thesis describes a solution to the subgraph isomorphism problem using the color coding technique. The subgraph isomorphism problem, its variants, and its applications are shown. The problem of constructing a nice tree decomposition of optimal width for a given graph is addressed, as such structure is required for the corresponding approach. As a main part of the thesis, several modifications and optimizations of the original color coding algorithm are proposed. Practical result of this work is a module implemented in C designated to solve large instances of the subgraph isomorphism problem along with the enumeration of the results.
Hitting paths in graphs
Author
Radovan Červený
Year
2018
Type
Master thesis
Supervisor
RNDr. Ondřej Suchý, Ph.D.
Reviewers
RNDr. Tomáš Valla, Ph.D.
Department
Summary
The problem of d-Path Vertex Cover, d-PVC lies in determining a subset F of vertices of a given graph G=(V,E) such that G \ F does not contain a path on d vertices. The paths we aim to cover need not to be induced. It is known that the d-PVC problem is NP-complete for any d >= 2. 5-PVC is known to be solvable in O(5^k*n^O(1)) time when parameterized by the size of the solution k. In this thesis we present an iterative compression algorithm that solves the 5-PVC problem in O(4^k*n^O(1)) time.
Parameterized Algorithms for Steiner Trees
Author
Peter Mitura
Year
2019
Type
Master thesis
Supervisor
RNDr. Ondřej Suchý, Ph.D.
Reviewers
doc. Ing. Ivan Šimeček, Ph.D.
Department
Summary
Given a weighted graph and a subset of its vertices called terminals, the Steiner Tree problem is to find
its connected subgraph of the minimum weight, that contains all of the given terminals. This problem is widely known
to be NP-hard, and has a wide range of applications in integrated circuit design, networking, transportation and more.
In our thesis, we analyze Dreyfus-Wagner, Erickson-Monma-Veinott, and Nederlof algorithms for this problem
parameterized by the number of vertices, and the rank-based dynamic programming algorithm for the problem
parameterized by treewidth. For all of these algorithms, we provide an optimized implementation, and compare it with
other solutions by submitting our results to the PACE 2018 challenge.
Induced star partition of graphs with respect to structural parameters
Author
Xuan Thang Nguyen
Year
2023
Type
Master thesis
Supervisor
RNDr. Ondřej Suchý, Ph.D.
Reviewers
Mgr. Michal Opler, Ph.D.
Department
Summary
An induced star partition of an undirected graph G = (V, E) is a partition S_1, ..., S_q of V(G) such that each set S_i induces a star (graph isomorphic to K_{1, r} for some r >= 0.
The Induced Star problem asks whether G admits an induced star partition of size q. This problem was proven to be NP-complete for each fixed q >=3 and has an exact 3^n n^{O(1)} time polynomial space algorithm. To the best of our knowledge, there are no known algorithms based on structural parameters for the problem. We present the following results:
(1) The problem is FPT when parameterized by the vertex cover number of the graph and there is an exact O(k^{2k+1} n^2) time algorithm, where k is the vertex cover number of the input graph.
(2) The problem is FPT when parameterized by the treewidth of the graph and there is an exact O(tw(G)^{2tw(G)} * n) time algorithm, where tw(G) is the treewidth of the input graph.
(3) For a fixed q, the problem can be solved linear time on graphs with bounded cliquewidth.
We also provide a simple implementation of our algorithm parameterized by the vertex cover number in C++ and evaluate its performance.