
Structural properties of graphs and eficient algorithms: Problems Between Parameters
Knop, Dušan ; Fiala, Jiří (advisor) ; Niedermeier, Rolf (referee) ; Feldmann, Andreas Emil (referee)
Structural Properties of Graphs and Eficient Algorithms: Problems Between Parameters Dušan Knop Parameterized complexity became over last two decades one of the most impor tant subfield of computational complexity. Structural graph parameters (widths) play important role both in graph theory and (parameterized) algoritmh design. By studying some concrete problems we exhibit the connection between struc tural graph parameters and parameterized tractability. We do this by examining tractability and hardness results for the Target Set Selection, Minimum Length Bounded Cut, and other problems. In the Minimum Length Bounded Cut problem we are given a graph, source, sink, and a positive integer L and the task is to remove edges from the graph such that the distance between the source and the sink exceeds L in the resulting graph. We show that an optimal solution to the Minimum Length Bounded Cut problem can be computed in time f(k)n, where f is a computable function and k denotes the treedepth of the input graph. On the other hand we prove that (under assumption that FPT ̸= W[1]) no such algorithm can exist if the parameter k is the treewidth of the input graph. Currently only few such problems are known. The Target Set Selection problem exibits the same phenomenon for the vertex cover number and...


EberhardLike Theorems
Šimečková, Zuzana ; Šámal, Robert (advisor) ; Fiala, Jiří (referee)
Define sequence (pk) = (p3,p4, . . . ) as numbers of ksized faces  kgons  of an embedding of a planar graph. A corollary to Euler's formula for planar graphs states that for cubic graphs ∑ k>=3 (6 − k)pk = 12 holds. Naturally, this leads us to explore the nature of p for which a corresponding cubic planar graph exists. Eberhard proved that if p satisfies the equality above then a cubic planar graph that corresponds to p except for the number of hexagons, exists. DeVos et al. show similar theorem, but instead of hexagon, both pentagons and heptagons can be added. In this thesis, we extend their result by using their proof strategy and designing a program to find graphs needed in such proof. We were able to prove that for every pair r,s ∈ N where s < 6 < r < 14 and r,s are coprime the following theorem holds: for each sequence of nonnegative integers satisfying ∑ k>=3 (6 − k)pk = 12 there are infinitely many cubic planar graphs corresponding to p except for the number of both rgons and sgons. 1


Computational complexity in graph theory
Melka, Jakub ; Kratochvíl, Jan (advisor) ; Fiala, Jiří (referee)
In the present work we study the problem of reconstructing a graph from its closed neighbourhood list. We will explore this problem, formulated by V. Sós, from the point of view of the fixed parameter complexity. We study the graph reconstruction problem in a more general setting, when the reconstructed graph is required to belong to some special graph class. In the present work we prove that this general problem lies in the complexity class FPT, when parametrized by the treewidth and maximum degree of the reconstructed graph, or by the number of certain special induced subgraphs if the reconstructed graph is 2degenerate. Also, we prove that the graph reconstruction problem lies in the complexity class XP when parametrized by the vertex cover number. Finally, we prove mutual independence of the results


Structural properties of graphs and eficient algorithms: Problems Between Parameters
Knop, Dušan ; Fiala, Jiří (advisor)
Structural Properties of Graphs and Eficient Algorithms: Problems Between Parameters Dušan Knop Parameterized complexity became over last two decades one of the most impor tant subfield of computational complexity. Structural graph parameters (widths) play important role both in graph theory and (parameterized) algoritmh design. By studying some concrete problems we exhibit the connection between struc tural graph parameters and parameterized tractability. We do this by examining tractability and hardness results for the Target Set Selection, Minimum Length Bounded Cut, and other problems. In the Minimum Length Bounded Cut problem we are given a graph, source, sink, and a positive integer L and the task is to remove edges from the graph such that the distance between the source and the sink exceeds L in the resulting graph. We show that an optimal solution to the Minimum Length Bounded Cut problem can be computed in time f(k)n, where f is a computable function and k denotes the treedepth of the input graph. On the other hand we prove that (under assumption that FPT ̸= W[1]) no such algorithm can exist if the parameter k is the treewidth of the input graph. Currently only few such problems are known. The Target Set Selection problem exibits the same phenomenon for the vertex cover number and...


Steiner coloring of cubic graphs
Tlustá, Stanislava ; Fiala, Jiří (advisor) ; Šámal, Robert (referee)
This thesis is dedicated to the coloring of cubic graphs. It summarizes the knowledge we have about so called Steiner coloring, which is an edgecoloring such that the colors incident with one vertex form a triple of some partial Steiner system. The main objects of interest are the projective and affine systems. Afterwards the sufficient condition for universality of the system is stated and it is observed, that all other transitive Steiner triple systems satisfy it. This thesis also contains methods of construction of the coloring for the Fano plane, for the affine system Z3 3 and for the universal system created as a product of the Fano plane and the trivial system (F7 S⊠ 3). Finally an algorithm usable for the rest of the systems and graphs with bounded treewidth is presented.


Game variants of graph labeling
Jedličková, Nikola ; Šámal, Robert (advisor) ; Fiala, Jiří (referee)
A graph labeling on a graph G is a mapping from the vertex set or the edge set to a set of labels L ⊆ N ∪ {0}. We will survey the existing results on graph labeling games. We also introduce a new type of labeling  ESD labeling and its game variant which was inspired by Tuza. An ESD labeling on a graph G is an injective mapping φ : V (G) → {1, . . . , n} such that for every two edges, the sum of the the labels on their endpoints is different. Apart from the question of existence of such labeling, we will examine game variant in which two players gradually build an ESD labeling. 1


Approximation of independence number of planar graphs
Berg, Michal ; Dvořák, Zdeněk (advisor) ; Fiala, Jiří (referee)
The independent set problem is a wellknown NPcomplete problem, which is NP complete even for planar graphs. But unlike general graphs, there exists an polynomial time approximation scheme for planar graphs. We are going to describe an exact algorithm for maximum independent set problem in planar graphs based on dynamic programming. This algorithm can be easily modified to an polynomialtime approximation scheme. We implemented both versions of this algorithm and tested them. We used a few random planar graph generators for that. We compared the exact algorithm with another two algorithms. We compared the approximation algorithm with its exact version and measured its real approximation ratio and also its time complexity in comparison with the exact version. We discovered that the exact algorithm usually finishes the computation faster than the other two algorithms. We also discovered that the approximation version has a better approximation ratio compared to the theoretical minimum with good time complexity. 1


Application of Music Therapy in Special Education for iCT Framework
Bártů, Tomáš ; Šátek, Václav (referee) ; Fiala, Jiří (advisor)
This bachelor thesis describes development of virtual guitar application for the purposes of music therapy in environment of special education for mentally challenged. Hence this thesis deals with issues of development of similarly focused applications, an analysis of some already existing applications of this kind and a design, implementation of a new application. The resulting application follows on design principles of " Computer as Therapy " project and it is based on iCT Framework simplifying design and development of applications in indicated environment. The development is focused on multiplatform development with support for operating system Android and iOS. The verification of the application has been done in environment of mentally challenged people.


Application of AAC in Special Education for iCT Framework
Čajánek, Martin ; Šátek, Václav (referee) ; Fiala, Jiří (advisor)
This bachelor thesis focuses on analysis of communication needs in special education during sessions with mental disabled people and also focuses on application, which addresses this problematic. Developed application enables users to create sentences by choosing picture symbols representing words or their own creating and subsequent voice synthesizing of constructed sentence. This application is designed for mobile devices with Android and iOS operating systems and was develop in accordance with " Computer as Therapy " design principles and serves as extension (addon) for iCT Framework, which encapsulates and simplifies interaction and management among applications designed for special education.


iCT Framework and Application for Sign Language Translation
Meca, Vojtěch ; Šátek, Václav (referee) ; Fiala, Jiří (advisor)
The aim of this thesis was to create two applications for people with learning difficulties. The first, iCT Framwork, is also an executable application to be used with the target group mentioned above. As an executable application, iCT Framework operates as a central tool for managing users, applications, and user restrictions. Development of Gesture Translator application presented another aim of the thesis: this application can translate sign language gestures for people with learning difficulties. Both applications are functioning on Android as well as iOS operating systems.
