RNDr. Ondřej Suchý, Ph.D.

Second Vice-Chair of the Academic Senate

Theses

Bachelor theses

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.
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.

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.
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).

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.

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.
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.

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.
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.

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.

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.
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.

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.
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.

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.
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.

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.

Master theses

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.
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.
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.

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.
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.

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.
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.