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

Second Vice-Chair of the Academic Senate

- +420224359877
- ondrej.suchy@fit.cvut.cz
- TH:A-1229

- Profile
- Publications
- Projects
- Teaching
- 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.

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.

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

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

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

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

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

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

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

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

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

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

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.

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

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