Theses

doc. RNDr. Dušan Knop, Ph.D.

Mgr. Michal Opler, Ph.D.

Department of Theoretical Computer Science

This thesis focuses on winner selection in committee election. We provide an overview of voting systems for single-winner and multi-winner election. Winner selection is often computationally hard, therefore we introduce election with structured preferences. In election with structured preferences, the votes are in some way restricted which may help to create more efficient winner selection algorithms. We describe some of the known structured preferences. We provide an overview of the current literature on the topic of structured and nearly structured preferences. We also review current work on committee election with structured preferences and usage of ordered weighted average (OWA) in committee election. We propose polynomial-time algorithms for finding a winning committee for approval election with OWA vector (0, ..., 0, 1) and interval preference restrictions. In such election, a voter approves a committee only if she approves all of its members. We use this property and show two approaches for finding a winning committee.

Thesis on DSpace

doc. RNDr. Dušan Knop, Ph.D.

Ing. Daniel Vašata, Ph.D.

Department of Applied Mathematics

The maps of elections framework is a methodology for visualizing and analyzing election datasets. So far, this framework was restricted to collections of election datasets that have equal numbers of candidates. In this thesis, we extend this framework to be able to deal with datasets containing different numbers of candidates. We do this in two ways: we extend an already existing positionwise distance, and we also develop the idea and implementation of a feature distance. We test the new distances on synthetic data generated using the Mapel package.

Thesis on DSpace

doc. RNDr. Dušan Knop, Ph.D.

RNDr. Jiřina Scholtzová, Ph.D.

Department of Theoretical Computer Science

In this work, we deal with the problem of minimising the total power consumption of a wireless network, which is formally known as Min-Power Symmetric Connectivity. The wireless network is represented by an edge-weighted undirected graph. The goal is to find a connected spanning subgraph with the minimum sum of the costs across all vertices. The cost of a vertex is given by the largest weight of the edge incident to the given vertex. It is known that the problem is NP-hard. We extend this result and show that the problem is NP-hard for a particular class of complete graphs. Next, we present two routines for solving Min-Power Symmetric Connectivity more efficiently. One of the methods focuses on finding the so-called obligatory subgraph. We are able to find it efficiently using lower bounds on the vertex cost. We introduce a method for incrementing these vertex lower bounds. Subsequently, we focus on the possible reduction in the number of edges. We present a method for identifying redundant edges in a graph, thereby reducing the computational complexity of the task.

Thesis on DSpace

doc. RNDr. Dušan Knop, Ph.D.

Ing. Václav Blažej, Ph.D.

Department of Theoretical Computer Science

In the Roommate diversity problem, agents that belong to one of the two types have to be allocated to fixed size rooms based on their preferences, which depend solely on the fraction of agents of their own type among their potential roommates. In this work we study the stability of outcomes with respect to the room size and structured preferences. We provide a new randomized algorithm for finding core stable outcomes and show the results which we have obtained with the algorithm. We have found a small single-peaked instance with empty core and have verified, that every instance of the Roommate diversity problem with room size = 3, all preferences single peaked and number of agents <= 30, room size = 3 and number of agents <= 15, room size = 4, all preferences single peaked and number of agents = 30, admits an outcome that is core stable. We present arguments why we believe that every instance of this problem with room size = 3, room size = 4 and all preferences single peaked, admits an outcome that is core stable.

Thesis on DSpace

RNDr. Tomáš Valla, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Department of Theoretical Computer Science

In this thesis, we study the m-eternal domination problem. Given graph G, guards are placed on vertices of G. Then vertices are subject to sequential attacks. After each attack, a guard must move into the attacked vertex. At most one guard is allowed to occupy any vertex. We denote the minimum number of guards, that can defend G indefinitely as g[?]m(G). We consider cactus graphs G, such that every edge in G is on a cycle of size 3k + 1 for some k [?] N. We show that for every such G on n vertices, g[?]m(G) = 1 + (n [?] 1)/3. We introduce the m-eternal guard configuration problem, being the same as the m-eternal domination problem, except it allows multiple guards on single vertex. We denote the minimum number of required guards in G as G[?]m(G). We present a linear algorithm for computing G[?]m(G) in cactus graphs, where every articulation is in two blocks. Moreover, we design a linear-time algorithm for computing g[?]m in clique trees. We include a C++ implementation of these algorithms, together with an exponential algorithm for both problems in general graphs.

Thesis on DSpace

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

doc. Ing. Ivan Šimeček, Ph.D.

Department of Theoretical Computer Science

RNDr. Tomáš Valla, Ph.D.

Department of Theoretical Computer Science

In this thesis, we examine several open problems in taking and breaking games under the impartial and partizan setting. We prove the existence of an impartial subtraction game with aperiodic nim-sequence and periodic outcome sequence. We also analyze the equivalence classes of subtraction games and provide a solution to one of these classes. We introduce a new taking and breaking game and partially solve it. Then we solve several partizan subtraction games and partizan pure breaking games and describe a general technique for testing arithmetic periodicity of these games. Moreover, we design some game solving algorithms for impartial taking and breaking games. We prove PSPACE-hardness for a generalized subtraction game under the impartial setting and EXPTIME-hardness under the partizan setting.

Thesis on DSpace

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

doc. Ing. Ivan Šimeček, Ph.D.

Department of Theoretical Computer Science

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.

Thesis on DSpace

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

RNDr. Tomáš Valla, Ph.D.

Department of Theoretical Computer Science

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.

Thesis on DSpace

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

RNDr. Tomáš Valla, Ph.D.

Department of Theoretical Computer Science

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.

Thesis on DSpace

RNDr. Tomáš Valla, Ph.D.

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

Department of Theoretical Computer Science

This thesis studies so-called network motifs. Network motifs are connected subgraphs of a given network that occur in significantly higher frequencies than would be expected in random networks. Different approaches to finding network motifs are described and based on their analysis a new improved parallel algorithm for finding network motifs called Efise was introduced. Practical results show, that Efise offers significantly better performance than other tools and thanks to efficient parallelization method, it also achieves linear speedups, which makes it an order of magnitude faster than previous state-of-the-art tools for finding network motifs.

Thesis on DSpace