The complexity landscape of decompositional parameters for ILP: Programs with few global variables and constraints
Autoři
Dvorak, P.; Eiben, E.; Ganian, R.; Knop, D.; Ordyniak, S.
Rok
2021
Publikováno
Artificial Intelligence. 2021, 300 ISSN 0004-3702.
Typ
Článek
Pracoviště
Anotace
Integer Linear Programming (ILP) has a broad range of applications in various areas of artificial intelligence. Yet in spite of recent advances, we still lack a thorough understanding of which structural restrictions make ILP tractable. Here we study ILP instances consisting of a small number of "global" variables and/or constraints such that the remaining part of the instance consists of small and otherwise independent components; this is captured in terms of a structural measure we call fracture backdoors which generalizes, for instance, the well-studied class of N-fold ILP instances.
Local linear set on graphs with bounded twin cover number
Typ
Článek
Pracoviště
Anotace
Inspired by recent results for the so-called fair and local linear problems, we define two problems, LOCAL LINEAR SET and LOCAL LINEAR VERTEX COVER. Here the task is to find a set of vertices X subset of V (which is a vertex cover) of the input graph (V, E) such that the local linear constraints l(v) <= vertical bar X boolean AND N(v)vertical bar <= u(v) hold for all v is an element of V; here, l(v) and u( v) are on the input. We prove that both problems are in FPT for the parameter twin cover number (using integer linear programming).
Parameterized complexity of configuration integer programs
Autoři
Knop, D.; Koutecky, M.; Levin, A.; Mnich, M.; Onn, S.
Rok
2021
Publikováno
Operations Research Letters. 2021, 49(6), 908-913. ISSN 0167-6377.
Typ
Článek
Pracoviště
Anotace
Configuration integer programs (IP) have been key in the design of algorithms for NP-hard high-multiplicity problems. First, we develop fast exact (exponential-time) algorithms for Configuration IP and matching hardness results. Second, we showcase the implications of these results to bin-packing and facility-location-like problems.
Kernelization of graph hamiltonicity: Proper H-graphs
Autoři
Chaplick, S.; Fomin, F.V.; Golovach, P.A.; Knop, D.; Zeman, P.
Rok
2021
Publikováno
SIAM Journal on Discrete Mathematics. 2021, 35(2), 840-892. ISSN 0895-4801.
Typ
Článek
Pracoviště
Anotace
We obtain new polynomial kernels and compression algorithms for Path Cover and Cycle Cover, the well-known generalizations of the classical Hamiltonian Path and Hamiltonian Cycle problems. Our choice of parameterization is strongly influenced by the work of Biró, Hujter, and Tuza, who in 1992 introduced H-graphs, intersection graphs of connected subgraphs of a subdivision of a fixed (multi-)graph H. In this work, we turn to proper H-graphs, where the containment relationship between the representations of the vertices is forbidden. As the treewidth of a graph measures how similar the graph is to a tree, the size of graph H is the parameter measuring the closeness of the graph to a proper interval graph. We prove the following results. Path Cover admits a kernel of size O(||H||^8), where ||H|| is the size of graph H. In other words, we design an algorithm that for an n-vertex graph G and integer k >= 1, in time polynomial in n and ||H||, outputs a graph G' of size O(||H||^8) and k' <= |V(G')| such that the vertex set of G is coverable by k vertex-disjoint paths if and only if the vertex set of G' is coverable by k' vertex-disjoint paths. Hamiltonian Cycle admits a kernel of size O(||H||^8). Cycle Cover admits a polynomial kernel. We prove it by providing a compression of size O(||H||^10) into another NP-complete problem, namely, Prize Collecting Cycle Cover, that is, we design an algorithm that, in time polynomial in n and ||H||, outputs an equivalent instance of Prize Collecting Cycle Cover of size O(||H||^10). In all our algorithms we assume that a proper H-decomposition is given as a part of the input.
Graph isomorphism restricted by lists
Autoři
Klavík, P.; Knop, D.; Zeman, P.
Rok
2021
Publikováno
Theoretical Computer Science. 2021, 860 51-71. ISSN 0304-3975.
Typ
Článek
Pracoviště
Anotace
The complexity of graph isomorphism (GRAPHISO) is a famous problem in computer science. For graphs G and H, it asks whether they are the same up to a relabeling of vertices. In 1981, Lubiw proved that list restricted graph isomorphism (LISTISO ) is NP -complete: for each u∈V(G), we are given a list L(u)⊆V(H) of possible images of u. After 35 years, we revive the study of this problem and consider which results for GRAPHISO can be modified to solve LISTISO. We prove: 1) Under certain conditions, GI -completeness of a class of graphs implies NP -completeness of LISTISO. 2) Several combinatorial algorithms for GRAPHISO can be modified to solve LISTISO: for trees, planar graphs, interval graphs, circle graphs, permutation graphs, and bounded treewidth graphs. 3) LISTISO is NP -complete for cubic colored graphs with sizes of color classes bounded by 8 with all lists of size at most 3.
High-Multiplicity Fair Allocation Made More Practical
Autoři
Bredereck, R.; Figiel, A.; Kaczmarczyk, A.; Knop, D.; Niedermeier, R.
Rok
2021
Publikováno
AAMAS '21: 20th International Conference on Autonomous Agents and Multiagent Systems, Virtual Event, United Kingdom, May 3-7, 2021. New York: ACM, 2021. p. 260-268. ISSN 1548-8403. ISBN 978-1-7138-3262-1.
Typ
Stať ve sborníku
Pracoviště
Anotace
The envy-free, Pareto-efficient allocation of indivisible goods leads to computationally hard problems. There is a big variety of modeling issues, such as agent-specific utility functions or (high numbers of) different types of goods. In recent work, Bredereck et al. [ACM EC~2019] addressed this topic by showing (theoretical) fixed-parameter tractability results for "high-multiplicity fair allocation", exploiting parameters such as the number of agents or maximum absolute utility values. To this end, they used a number of tools from (theoretical) integer linear programming. We "engineer" their work towards practical usefulness, thereby being able to solve all real-world instances from the state-of-art online platform "spliddit.org for provably fair solutions". Besides providing the foundations for a fast tool for fair allocations, we also offer a flexible framework with the possibility to relax fairness or efficiency demands so to, e.g., allow tradeoffs between fairness and social welfare. Moreover, our framework provides ways to interpret and explain "solution paths" which makes it possible to perform further explorations in cases when no envy-free and efficient allocations exist.
Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set
Autoři
Rok
2021
Publikováno
Approximation and Online Algorithms - 19th International Workshop, WAOA 2021, Lisbon, Portugal, September 6-10, 2021, Revised Selected Papers. Springer, Cham, 2021. p. 23-38. Lecture Notes in Computer Science (LNCS). vol. 12982. ISSN 0302-9743. ISBN 978-3-030-92701-1.
Typ
Stať ve sborníku
Pracoviště
Anotace
Consider a vertex-weighted graph G with a source s and a target t. Tracking Paths requires finding a minimum weight set of vertices (trackers) such that the sequence of trackers in each path from s to t is unique. In this work, we derive a factor 66-approximation algorithm for Tracking Paths in weighted graphs and a factor 4-approximation algorithm if the input is unweighted. This is the first constant factor approximation for this problem. While doing so, we also study approximation of the closely related r -Fault Tolerant Feedback Vertex Set problem. There, for a fixed integer r and a given vertex-weighted graph G, the task is to find a minimum weight set of vertices intersecting every cycle of G in at least r+1 vertices. We give a factor O(r^2) approximation algorithm for r -Fault Tolerant Feedback Vertex Set if r is a constant.
Fine-Grained View on Bribery for Group Identification
Autoři
Boehmer, N.; Bredereck, R.; Knop, D.; Luo, J.
Rok
2020
Publikováno
Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2020. p. 67-73. ISBN 978-0-9992411-6-5.
Typ
Stať ve sborníku
Pracoviště
Anotace
Given a set of individuals qualifying or disqualifying each other, group identification is the task of identifying a socially qualified subgroup of individuals. Social qualification depends on the specific rule used to aggregate individual qualifications. The bribery problem in this context asks how many agents need to change their qualifications in order to change the outcome. Complementing previous results showing polynomial-time solvability or NP-hardness of bribery for various social rules in the constructive (aiming at making specific individuals socially qualified) or destructive (aiming at making specific individuals socially disqualified) setting, we provide a comprehensive picture of the parameterized computational complexity landscape. Conceptually, we also consider a more fine-grained concept of bribery cost, where we ask how many single qualifications need to be changed, and a more general bribery goal that combines the constructive and destructive setting.
Balancing the Spread of Two Opinions in Sparse Social Networks (Student Abstract)
Autoři
Rok
2022
Publikováno
Proceedings of the 36th AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2022. p. 12987-12988. ISSN 2159-5399. ISBN 978-1-57735-876-3.
Typ
Stať ve sborníku
Pracoviště
Anotace
We propose a new discrete model for simultaneously spreading two opinions within a social network inspired by the famous Target Set Selection problem. We are given a social network, a seed-set of agents for each opinion, and two thresholds per agent. The first threshold represents the willingness of an agent to adopt an opinion if she has no opinion at all, while the second threshold states the readiness to acquire a second opinion. The goal is to add as few agents as possible to the initial seed-sets such that, once the process started with these seed-set stabilises, each agent has either both opinions or none. We perform an initial study of its computational complexity. It is not surprising that the problem is NP-hard even in quite restricted settings. Therefore, we investigate the complexity of the problem from the parameterized point-of-view with special focus on sparse networks, which appears often in practice. Among other things, we show that the proposed problem is in the FPT complexity class if we parameterize by the vertex cover number of the underlying graph.
Automorphisms of the cube n^d
Autoři
Dvořák, P.; Valla, T.
Rok
2021
Publikováno
Discrete Mathematics. 2021, 2021(344(3)), ISSN 0012-365X.
Typ
Článek
Pracoviště
Anotace
Consider a hypergraph n^d where the vertices are points of the d-dimensional cube [n]^d and the edges are all sets of n points such that they are in one line. We study the structure of the group of automorphisms of n^d, i.e., permutations of points of [n]^d preserving the edges. In this paper we provide a complete characterization. Moreover, we consider the Colored Cube Isomorphism problem of deciding whether for two colorings of the vertices of n^d there exists an automorphism of n^d preserving the colors. We show that this problem is GI-complete.
A Parameterized Complexity View on Collapsing k-Cores
Autoři
Luo, J.; Molter, H.; Suchý, O.
Rok
2021
Publikováno
Theory of Computing Systems. 2021, 65(8), 1243-1282. ISSN 1432-4350.
Typ
Článek
Pracoviště
Anotace
We study the NP-hard graph problem Collapsed k-Core where, given an undirected graph G and integers b, x, and k, we are asked to remove b vertices such that the k-core of remaining graph, that is, the (uniquely determined) largest induced subgraph with minimum degree k, has size at most x. Collapsed k-Core was introduced by Zhang et al. (2017) and it is motivated by the study of engagement behavior of users in a social network and measuring the resilience of a network against user drop outs. Collapsed k-Core is a generalization of r-Degenerate Vertex Deletion (which is known to be NP-hard for all r >= 0) where, given an undirected graph G and integers b and r, we are asked to remove b vertices such that the remaining graph is r-degenerate, that is, every its subgraph has minimum degree at most r. We investigate the parameterized complexity of Collapsed k-Core with respect to the parameters b, x, and k, and several structural parameters of the input graph. We reveal a dichotomy in the computational complexity of Collapsed k-Core for k <= 2 and k >= 3. For the latter case it is known that for all x >= 0 Collapsed k-Core is W[P]-hard when parameterized by b. For k <= 2 we show that Collapsed k-Core is W[1]-hard when parameterized by b and in FPT when parameterized by (b + x). Furthermore, we outline that Collapsed k-Core is in FPT when parameterized by the treewidth of the input graph and presumably does not admit a polynomial kernel when parameterized by the vertex cover number of the input graph.
Minimum Eccentricity Shortest Path Problem with Respect to Structural Parameters
Autoři
Kučera, M.; Suchý, O.
Rok
2021
Publikováno
Combinatorial Algorithms. Cham: Springer International Publishing, 2021. p. 442-455. Lecture Notes in Computer Science. vol. 12757. ISSN 0302-9743. ISBN 978-3-030-79986-1.
Typ
Stať ve sborníku
Pracoviště
Anotace
The Minimum Eccentricity Shortest Path Problem consists in finding a shortest path with minimum eccentricity in a given undirected graph. The problem is known to be NP-complete and W[2]-hard with respect to the desired eccentricity. We present fpt algorithms for the problem parameterized by the modular width, distance to cluster graph, the combination of distance to disjoint paths with the desired eccentricity, and maximum leaf number.
On Kernels for d-Path Vertex Cover
Autoři
Červený, R.; Choudhary, P.; Suchý, O.
Rok
2022
Publikováno
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Wadern: Schloss Dagstuhl - Leibniz Center for Informatics, 2022. p. 29:1-29:14. Leibniz International Proceedings in Informatics (LIPIcs). vol. 241. ISSN 1868-8969. ISBN 978-3-95977-256-3.
Typ
Stať ve sborníku
Pracoviště
Anotace
In this paper we study the kernelization of the d-Path Vertex Cover (d-PVC) problem. Given a graph G, the problem requires finding whether there exists a set of at most k vertices whose removal from G results in a graph that does not contain a path (not necessarily induced) with d vertices. It is known that d-PVC is NP-complete for d≥ 2. Since the problem generalizes to d-Hitting Set, it is known to admit a kernel with O(dk^d) edges. We improve on this by giving better kernels. Specifically, we give kernels with O(k^2) vertices and edges for the cases when d = 4 and d = 5. Further, we give a kernel with O(k^4d^{2d+9}) vertices and edges for general d.
Automata Approach to Inexact Tree Pattern Matching Using 1-degree Edit Distance
Autoři
Rok
2021
Publikováno
Proceedings of the Prague Stringology Conference 2021. Praha: CESKE VYSOKE UCENI TECHNICKE V PRAZE, 2021. p. 1-15. ISBN 978-80-01-06869-4.
Typ
Stať ve sborníku
Pracoviště
Anotace
We compare labeled ordered trees based on unit cost 1-degree edit distance that uses operations vertex relabeling, leaf insertion, and leaf deletion. Given an input tree T and a tree pattern P, we find all subtrees in T that match P with up to k errors. We show that this problem can be solved by finite automaton when T and P are represented in linear, prefix bar, notation. First, we solve this problem by a pushdown automaton. Then, we show that it can be transformed into a nondeterministic finite automaton due to its restricted use of the pushdown store. We also show a simulation of the nondeterministic finite automaton by dynamic programming.
Hierarchical Bitmap Indexing for Range Queries on Multidimensional Arrays
Autoři
Krčál, L.; Ho, S.-S.; Holub, J.
Rok
2022
Publikováno
Database Systems for Advanced Applications. Springer, Cham, 2022. p. 509-525. Lecture Notes in Computer Science. vol. 13245. ISSN 0302-9743. ISBN 978-3-031-00122-2.
Typ
Stať ve sborníku
Pracoviště
Anotace
Bitmap indices are widely used in commercial databases for processing complex queries, due to their efficient use of bit-wise operations. Bitmap indices apply natively to relational and linear datasets, with distinct separation of the columns or attributes, but do not perform well on multidimensional array scientific data.
We propose a new method for multidimensional array indexing that considers the spatial component of multidimensional arrays. The hierarchical indexing method is based on sparse n-dimensional trees for dimension partitioning, and bitmap indexing with adaptive binning for attribute partitioning. This indexing performs well on range queries involving both dimension and attribute constraints, as it prunes the search space early. Moreover, the indexing is easily extensible to membership queries.
The indexing method was implemented on top of a state of the art bitmap indexing library Fastbit, using tables partitioned along any subset of the data dimensions. We show that the hierarchical bitmap index outperforms conventional bitmap indexing, where an auxiliary attribute is required for each dimension. Furthermore, the adaptive binning significantly reduces the amount of bins and therefore memory requirements.
Backward Pattern Matching on Elastic Degenerate Strings
Autoři
Procházka, P.; Cvacho, O.; Krčál, L.; Holub, J.
Rok
2021
Publikováno
Proceedings of 14th International Joint Conference on Biomedical Engineering Systems and Technologies (BIOSTEC 2021). Lisboa: SCITEPRESS – Science and Technology Publications, Lda, 2021. p. 50-59. vol. 3. ISSN 2184-4305. ISBN 978-989-758-490-9.
Typ
Stať ve sborníku
Pracoviště
Anotace
Recently, the concept of Elastic Degenerate Strings (EDS) was introduced as a way of representing a sequenced population of the same species. Several on-line Elastic Degenerate String Matching (EDSM) algorithms were presented so far. Some of them provide practical implementation. We propose a new on-line EDSM algorithm BNDM-EDS. Our algorithm combines two traditional algorithms BNDM and the Shift-And that were adapted to the specifics needed by Elastic Degenerate Strings. BNDM-EDS is running in O (Nmd m w e) worst-case time.
This implies O (Nm) time for small patterns, where m is the length of the searched pattern, N is the size of EDS, and w is the size of the computer word. The algorithm uses O (N + n) space, where n is the length of EDS. BNDM-EDS requires a simple preprocessing step with time and space O (m). Experimental results on real genomic data show superiority of BNDM-EDS over state-of-the-art algorithms.
Data Structures to Represent a Set of k-long DNA Sequences
Autoři
Chikhi, R.; Holub, J.; Medvedev, P.
Rok
2021
Publikováno
ACM Computing Surveys. 2021, 54(1), 17:1-17:22. ISSN 0360-0300.
Typ
Článek
DOI
Pracoviště
Anotace
The analysis of biological sequencing data has been one of the biggest applications of string algorithms. The approaches used in many such applications are based on the analysis of k-mers, which are short fixed-length strings present in a dataset. While these approaches are rather diverse, storing and querying a k-mer set has emerged as a shared underlying component. A set of k-mers has unique features and applications that, over the past 10 years, have resulted in many specialized approaches for its representation. In this survey, we give a unified presentation and comparison of the data structures that have been proposed to store and query a k-mer set. We hope this survey will serve as a resource for researchers in the field as well as make the area more accessible to researchers outside the field.
PFP Compressed Suffix Trees
Autoři
Boucher, C.; Cvacho, O.; Gagie, T.; Holub, J.; Manzini, G.; Navarro, G.; Rossi, M.
Rok
2021
Publikováno
Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX2021). Philadelphia: SIAM, 2021. p. 60-72. ISSN 2164-0300. ISBN 978-1-61197-647-2.
Typ
Stať ve sborníku
Pracoviště
Anotace
Prefix-free parsing (PFP) was introduced by Boucher et al. (2019) as a preprocessing step to ease the computation of Burrows-Wheeler Transforms (BWTs) of genomic databases. Given a string S, it produces a dictionary D and a parse P of overlapping phrases such that BWT(S) can be computed from D and P in time and workspace
bounded in terms of their combined size |PFP(S)|. In practice D and P are significantly smaller than S and computing BWT(S) from them is more efficient than computing
it from S directly, at least when S is the concatenation of many genomes. In this paper, we consider PFP(S) as a data structure and show how it can be augmented to sup-
port full suffix tree functionality, still built and fitting within O(|PFP(S)|) space. This entails the efficient computation of various primitives to simulate the suffix tree: computing a longest common extension (LCE) of two positions in S; reading any cell of its suffix array (SA), of its inverse (ISA), of its BWT, and of its longest common prefix array (LCP); and
computing minima over ranges and next/previous smaller value queries over the LCP. Our experimental results show that the PFP suffix tree can be efficiently constructed for
very large repetitive datasets and that its operations perform competitively with other compressed suffix trees that can only handle much smaller datasets.
Conversion of Finite Tree Automata to Regular Tree Expressions By State Elimination
Autoři
Rok
2020
Publikováno
Proceedings of the Prague Stringology Conference 2020. Praha: Czech Technical University in Prague, 2020. p. 11-22. ISBN 978-80-01-06749-9.
Typ
Stať ve sborníku
Pracoviště
Anotace
Regular tree languages can be accepted and described by finite tree automata and regular tree expressions, respectively.
We describe a new algorithm that converts a finite tree automaton to an equivalent regular tree expression.
Our algorithm is analogous to the well-known state elimination method of the conversion of a string finite automaton to an equivalent string regular expression.
We define a generalised finite tree automaton, the transitions of which read the sets of trees described by regular tree expressions.
Our algorithm eliminates states of the generalised finite tree automaton, which is analogous to the elimination of states in converting the string finite automaton.
Forward Linearised Tree Pattern Matching Using Tree Pattern Border Array
Autoři
Rok
2020
Publikováno
Proceedings of the Prague Stringology Conference 2020. Praha: Czech Technical University in Prague, 2020. p. 61-73. ISBN 978-80-01-06749-9.
Typ
Stať ve sborníku
Pracoviště
Anotace
We define a tree pattern border array as a property of linearised trees analogous to border arrays from the string domain. We use it to define a new forward tree pattern matching algorithm for ordered trees, which finds all occurrences of a single given linearised tree pattern in a linearised input tree. As with the classical Morris-Pratt algorithm, the tree pattern border array is used to determine shift lengths in the matching phase of the tree pattern matching algorithm.
We compare the new algorithm with the best performing previously existing algorithms based on backward linearised tree pattern matching algorithms, (non-)linearised tree pattern matching algorithms using finite tree automata or stringpath matchers. We show that the presented algorithm outperforms these for single tree pattern matching.
Adapting Stable Matchings to Evolving Preferences
Autoři
Bredereck, R.; Chen, J.; Knop, D.; Luo, J.; Niedermeier, R.
Rok
2020
Publikováno
Proceedings of the AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2020. p. 1830-1837. ISSN 2159-5399. ISBN 978-1-57735-835-0.
Typ
Stať ve sborníku
Pracoviště
Anotace
Adaptivity to changing environments and constraints is key to success in modern society. We address this by proposing “incrementalized versions” of Stable Marriage and Stable Roommates. That is, we try to answer the following question: for both problems, what is the computational cost of adapting an existing stable matching after some of the preferences of the agents have changed. While doing so, we also model the constraint that the new stable matching shall be not too different from the old one. After formalizing these incremental versions, we provide a fairly comprehensive picture of the computational complexity landscape of Incremental Stable Marriage and Incremental Stable Roommates. To this end, we exploit the parameters “degree of change” both in the input (difference between old and new preference profile) and in the output (difference between old and new stable matching). We obtain both hardness and tractability results, in particular showing a fixed-parameter tractability result with respect to the parameter “distance between old and new stable matching”.
Parameterized Algorithms for Finding a Collective Set of Items
Autoři
Bredereck, R.; Faliszewski, P.; Kaczmarczyk, A.; Knop, D.; Niedermeier, R.
Rok
2020
Publikováno
Proceedings of the AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2020. p. 1838-1845. ISSN 2159-5399. ISBN 978-1-57735-835-0.
Typ
Stať ve sborníku
Pracoviště
Anotace
We extend the work of Skowron et al. (AIJ, 2016) by considering the parameterized complexity of the following problem. We are given a set of items and a set of agents, where each agent assigns an integer utility value to each item. The goal is to find a set of k items that these agents would collectively use. For each such collective set of items, each agent provides a score that can be described using an OWA (ordered weighted average) operator and we seek a set with the highest total score. We focus on the parameterization by the number of agents and we find numerous fixed-parameter tractability results (however, we also find some W[1]-hardness results). It turns out that most of our algorithms even apply to the setting where each agent has an integer weight.
Multidimensional Stable Roommates with Master List
Autoři
Bredereck, R.; Heeger, K.; Knop, D.; Niedermeier, R.
Rok
2020
Publikováno
Web and Internet Economics - 16th International Conference, WINE 2020, Beijing, China, December 7-11, 2020, Proceedings. Cham: Springer, 2020. p. 59-73. ISBN 978-3-030-64945-6.
Typ
Stať ve sborníku
Pracoviště
Anotace
Since the early days of research in algorithms and complexity, the computation of stable matchings is a core topic. While in the classic setting the goal is to match up two agents (either from different “gender” (this is Stable Marriage) or “unrestricted” (this is Stable Roommates)), Knuth [1976] triggered the study of three- or multidimensional cases. Here, we focus on the study of Multidimensional Stable Roommates, known to be 𝖭𝖯 -hard since the early 1990’s. Many 𝖭𝖯 -hardness results, however, rely on very general input instances that do not occur in at least some of the specific application scenarios. With the quest for identifying islands of tractability, we look at the case of master lists. Here, as natural in applications where agents express their preferences based on “objective” scores, one roughly speaking assumes that all agent preferences are “derived from” a central master list, implying that the individual agent preferences shall be similar. Master lists have been frequently studied in the two-dimensional (classic) stable matching case, but seemingly almost never for the multidimensional case. This work, also relying on methods from parameterized algorithm design and complexity analysis, performs a first systematic study of Multidimensional Stable Roommates under the assumption of master lists.
Symbolická exekuce pro R
Autor
Petr Šťastný
Rok
2024
Typ
Bakalářská práce
Vedoucí
Pierre Donat-Bouillud, Ph.D.
Oponenti
Ing. Sebastián Krynski, MSc.
Katedra
Anotace
Symbolic execution je technika, která umožňuje testovat programy a dokazovat jejich netriviální vlastnosti.
Vytvoření nového systému pro symbolic execution je náročné. Místo toho je použita technika, kdy je symbolicky spouštěn samotný interpret cílového jazyka, díky čemuž je jednodušší symbolicky spustit i programy v daném jazyce.
V této práci aplikuji tuto techniku na jazyk R. Výsledný program je možné použít například na otestování korektnosti knihoven nebo na generování typových anotací.
Frontend překladače pro podmnožinu programovacího jazyka C++
Autor
Daniel Král
Rok
2024
Typ
Bakalářská práce
Vedoucí
Ing. Tomáš Pecka
Oponenti
Ing. Štěpán Plachý
Katedra
Anotace
Překladače pro programovací jazyky jsou nezbytnou součástí vývoje moderního software. Tato práce se zabývá návrhem přední části překladače pro (skoro) podmnožinu jazyka C++ nazvanou C+-. Nejprve je specifikován rozsah C+-. Poté je popsáno využití ANTLR4 pro lexikální a syntaktickou analýzu a vytvoření abstraktního syntaktického stromu. Následuje sémantická analýza a generování mezikódu LLVM IR pomocí LLVM C++ API. Implementace překladače je otestována sadou ukázkových kódů.
Možná vylepšení pro algoritmy řešící problém Min-Power Symmetric Connectivity
Autor
Richard Hartmann
Rok
2024
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Dušan Knop, Ph.D.
Oponenti
RNDr. Jiřina Scholtzová, Ph.D.
Katedra
Anotace
V teto praci se zabyvame problemem minimalizace celkove spotreby energie bezdratove site, ktery je formalne znamy jako Min-Power Symmetric Connectivity. Modelem bezdratove site je hranove ohodnoceny neorientovany graf. Cilem je najit souvisly podgraf, ktery pokryva vsechny vrcholy, s minimalnim souctem cen vsech vrcholu. Cena vrcholu je dana nejvetsi vahou hrany incidentni s danym vrcholem. Je znamo, ze se jedna o NP-tezky problem. Toto tvrzeni rozsirime a ukazeme, ze problem je NP-tezky pro konkretni tridu uplnych grafu. Dale predstavime dva postupy umoznujici efektivnejsi reseni Min-Power Symmetric Connectivity problemu. Jedna z metod se zameruje na hledani tzv. povinneho podgrafu. Ten jsme schopni efektivne nalezt za pomoci dolnich mezi cen vrcholu. Predstavime metodu, jak tyto dolni meze cen vrcholu zvysit. Dale se zabyvame moznou redukci poctu hran. Ukazeme metodu identifikujici nadbytecne hrany grafu, cimz snizime vypocetni slozitost ulohy.
Analýza velkých repozitářů kódu
Autor
Ing. Petr Máj
Rok
2023
Typ
Dizertační práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.
Oponenti
Prof. Tobias Wrigstad
Max Schaefer, MSc., DPhil.
Mgr. Tomáš Petříček, Ph.D.
Max Schaefer, MSc., DPhil.
Mgr. Tomáš Petříček, Ph.D.
Katedra
Vyhledávání vzorků ve stromech a indexování stromů za použití automatů zpracovávajících řetězce
Autor
Ing. Eliška Šestáková
Rok
2023
Typ
Dizertační práce
Vedoucí
doc. Ing. Jan Janoušek, Ph.D.
Oponenti
prof. RNDr. Alexandr Meduna, CSc.
prof. Philip Bille
prof. Giovanni Pighizzini
prof. Philip Bille
prof. Giovanni Pighizzini
Katedra
Aplikace zpětnovazebního učení na vytváření adversariálních vzorků škodlivého softwaru
Autor
Matouš Kozák
Rok
2023
Typ
Diplomová práce
Vedoucí
Mgr. Martin Jureček, Ph.D.
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.
Katedra
Anotace
Strojové učení se díky svým prvotřídním výsledkům v mnoha oblastech stává stále více populárnější pro řešení nejrůznějších problémů. Díky tomu vývojáři antivirů začínají začleňovat modely strojového učení i do svých produktů. I když tyto modely zlepšují schopnosti detekce antivirových programů, mají také své nevýhody v podobě citlivosti na adversariální útoky. Ačkoli tato citlivost byla prokázána u mnoha modelů při white-box útocích, pro oblast detekce malwaru je black-box útok využitelnější v praxi. Proto představujeme black-box útok, kde má útočník k dispozici pouze výsledek predikce a vzdává se jakýchkoli dalších informací o cílovém klasifikátoru. S využitím algoritmů zpětnovazebního učení jsme implementovali útok proti GBDT klasifikátoru natrénovaném na EMBER datasetu. Natrénovali jsme několik zpětnovazebních agentů na datové sadě malwaru pro operační systém Windows. Při modifikování jsme kladli velký důraz na zachování původní funkčnosti škodlivých vzorků. Dosáhli jsme úspěšnosti zmýlení cílového klasifikátoru v 58,92 % s využitím PPO algoritmu. Kromě toho, že jsme cílili na tento detektor, jsme studovali, jak se adversariální útok může přenést na jiné modely. Agent dříve natrénovaný proti GBDT klasifikátoru zaznamenal úspěšnost v 28,91 % případů proti MalConv, což je model založený čistě na strojovém učení. Vygenerované adversariální vzorky jsme také otestovali proti špičkovým AV programům a dosáhli jsme úspěšnosti zmýlení v rozmezí od 10,24 % do 25,7 %. Tyto výsledky dokazují, že nejen modely založené pouze na strojovém učení jsou náchylné k adversariálním útokům a že je třeba přijmout lepší opatření k ochraně našich systémů.
Strukturované volby komisí
Autor
Terezie Hrubanová
Rok
2023
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Dušan Knop, Ph.D.
Oponenti
Mgr. Michal Opler, Ph.D.
Katedra
Anotace
Tato práce se zabývá hledáním vítěze ve volbách komisí. Poskytujeme přehled volebních systémů pro single-winner a multi-winner volby. Hledání vítěze je často výpočetně náročné, proto zavádíme volby se strukturovanými preferencemi. Ve volbách se strukturovanými preferencemi jsou hlasy voličů nějakým způsobem omezené, což může usnadnit vytváření efektivnějších algoritmů pro hledání vítěze. Popisujeme některé ze známých strukturovaných preferencí.
Poskytujeme přehled současné literatury týkající se strukturovaných a téměř strukturovaných preferencí. Zkoumáme současné práce týkající se volby komisí se strukturovanými preferencemi a použití ordered weighted average (OWA) ve volbách komisí.
Představujeme polynomiální algoritmy pro hledání vítězných komisí v approval volbách s OWA vektorem (0, ..., 0, 1) a intervalově omezenými voličskými preferencemi. V takových volbách, volič schvaluje komisi pouze pokud schvaluje všechny její členy. Tuto vlastnost používáme a ukazujeme dva přístupy pro hledání výherní komise.
Implementace staticky typovaného, lazy, funkcionálního jazyka
Autor
Jan Liam Verter
Rok
2022
Typ
Diplomová práce
Vedoucí
Ryan Michael Culpepper
Oponenti
doc. Ing. Filip Křikava, Ph.D.
Katedra
Anotace
Tato práce se věnuje implementaci funkcionálního, staticky typovaného programovacího jazyka inspirovaného jazykem Haskell. Hlavním bodem zájmu práce je implementace typového systému pro tento jazyk. Implementace vychází z několika zdrojů zabývajících se implementací konkrétních aspektů typového systému. Tato práce se také zabývá dalšími aspekty implementace programovacího jazyka--lexikální a syntaktickou analýzou, překladem do menšího funkcionálního jazyka a tzv. non-strict evaluací.
Randomizované indexy pro přibližné vyhledávání v multidimenzionálních polích
Autor
Ing. Luboš Krčál
Rok
2022
Typ
Dizertační práce
Vedoucí
prof. Ing. Jan Holub, Ph.D.
Oponenti
prof. Ing. Michal Krátký, Ph.D.
Kwo-Sen Kuo, PhD.
Dimitar Mišev, PhD.
Kwo-Sen Kuo, PhD.
Dimitar Mišev, PhD.
Katedra
Složitost her na grafech
Autor
Ing. Václav Blažej
Rok
2022
Typ
Dizertační práce
Vedoucí
doc. RNDr. Tomáš Valla, Ph.D.
Oponenti
Prof., Dr. rer. nat. Robert Bredereck
RNDr. Martin Balko, Ph.D.
Paweł Rzążewski, PhD.
RNDr. Martin Balko, Ph.D.
Paweł Rzążewski, PhD.
Katedra
Dynamické tracovaní Haskellu
Autor
Ondřej Kvapil
Rok
2021
Typ
Bakalářská práce
Vedoucí
doc. Ing. Filip Křikava, Ph.D.
Oponenti
Vitaly Bragilevsky, MSc.
Katedra
Anotace
Haskell je jeden z nejznámějších jazyků s non-strict sémantikou. Na jednu stranu přináší tato sémantika pohodlí nekonečných datových struktur, řídících konstrukcí definovaných uživatelem a možnost vyhnout se nepotřebným výpočtům. Na stranu druhou jsou tyto výhody postiženy daní na výkonu za běhu programu a těžko předvídatelným chováním call-by-need. Nabízí se otázka: Vyplatí se líná evaluace? K zodpovězení této otázky musíme porozumět tomu, jak je lenost využívána v praxi. K tomuto účelu jsme vyvinuli nástroj pro dynamickou analýzu použitelný k trasování evaluace funkčních parametrů. Je implementován jako zásuvný modul kompilátoru Glasgow Haskell Compiler.
Stabilita Hedonických her se strukturovanými preferencemi
Autor
Jan Šmolík
Rok
2021
Typ
Bakalářská práce
Vedoucí
doc. RNDr. Dušan Knop, Ph.D.
Oponenti
Ing. Václav Blažej, Ph.D.
Katedra
Anotace
Problém stabilních spolubydlících s podmínkami různorodosti spočívá v rozdělení agentů dvou typů do koalic pevné velikosti na základě jejich preferencí, které závisí pouze na počtu agentů stejného typu. V této práci se zabýváme stabilitou takových rozdělení v závislosti na velikosti koalice a struktuře preferenčních profilů agentů. Snažíme se uchopit problém v celé jeho šíři a vytvořit nadhled nad celou problematikou představením Hedonických her a jejich zajímavých podtříd. Představujeme nový randomizovaný algoritmus na rychlé hledání core stabilních řešení instancí tohoto problému a ukazujeme, jakých výsledků jsme pomocí algoritmu dosáhli. Nalezli jsme malou single-peaked instanci s prázdným core a ověřili jsme, že každá instance tohoto problému, kde
velikost koalic = 3, preferenční relace všech agentů jsou single-peaked a počet agentů &lt;= 30,
velikost koalic = 3 a počet agentů &lt;= 15,
velikost koalic = 4, preferenční relace všech agentů jsou single-peaked a počet agentů = 8,
má core stabilní řešení. Předkládáme argumenty, proč se domníváme, že každá instance, kde
velikost koalic = 3,
velikost koalic = 4 a preferenční relace všech agentů jsou single-peaked,
má core stabilní řešení.
Algoritmy kombinatoriky na slovech
Autor
Martin Rejmon
Rok
2021
Typ
Diplomová práce
Vedoucí
doc. Ing. Štěpán Starosta, Ph.D.
Oponenti
doc. Ing. Jan Janoušek, Ph.D.
Katedra
Anotace
V této práci je podrobně popsáno několik algoritmů řešících problémy z matematického oboru kombinatorika na slovech. Součástí práce je i jejich implementace v svobodném a otevřeném počítačovém algebraickém systému SageMath za účelem jejich integrace do téhož systému. Mezi zkoumané algoritmy patří: klasifikace rostoucích písmenek morfismu, rozhodování se, zda morfismus je prostý, hledání zjednodušení morfismu, hledání všech nekonečných opakování v D0L systému a hledání všech podřetězců (kratší než zadaná délka) slov jazyka PD0L systému. Dále je v práci diskutován problém rozhodování se, zda morfimus D0L systému je prostý na množině podřetězců slov jazyka toho systému. Není obecně známo, zda tento problém jde rozhodnout, což v této práci není vyřešeno, ale je zde uvedeno, proč je to netriviální problém a kde některé z možných způsobů jeho řešení selžou.
Profilování haldy s nízkou latencí
Autor
Jan Tománek
Rok
2021
Typ
Diplomová práce
Vedoucí
doc. Ing. Daniel Langr, Ph.D.
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.
Katedra
Anotace
Četné dynamické alokace z haldy mohou mít zásadní dopad na celkovou dobu běhu programu. Problém se stává ještě více kritickým ve vícevláknových aplikacích, kde přílišná interakce s haldou může přerůst v hlavní zdroj neefektivity programu a negativně se podepsat na jeho škálovatelnosti. Existující profilery haldy přidávají k běhu programu tak velkou režii, že se profilování paměťově náročných vícevláknových aplikací stává téměř nemožné.
Tato práce popisuje obvyklé rozložení paměti Linuxového procesu, nastiňuje interní části paměťového manažeru GNU C, analyzuje existující nástroje pro profilování haldy a provádí čtenáře procesem konstrukce vlastního profileru haldy. Práce dále navrhuje koncept profilování haldy s nízkou latencí, na jehož základě byl vytvořen nový profiler s názvem Heaprof. Ten byl následně porovnán s existujícími profilery. Experimentální vyhodnocení odhalilo, že Heaprof jako jediný ze zkoumaných nástrojů dokázal provádět profilování bez dalšího dopadu na škálovatelnost programu. V osmivláknových benchmarcích došlo až k osminásobnému urychlení celého profilování.
Tiny x86 - Simulator procesorove architektury pro vyukove ucely
Autor
Ivo Strejc
Rok
2021
Typ
Diplomová práce
Vedoucí
Ing. Petr Máj, Ph.D.
Oponenti
Ing. Tomáš Pecka
Katedra
Anotace
Tato práce prezentuje tiny x86 architekturu a virtuální stroj, určené jako pomocný nástroj studentům k porozumění technikám kompilování a jejich dopad na výkon programu. V porovnání s již existujícími instrukčními sadami je tiny x86 jednodušší na použití, protože oproti binárnímu kódování nabízí aplikační rozhraní v jazyce C++ a nelimituje se na jeden návrh (jsou podporovány prvky CISC i RISC architektury). Prezentovaný virtuální stroj nabízí rozsáhle možnosti konfigurace, dovolující z(ne)výraznit různé návrhové prvky (počet registrů, odezvu paměti, trvání instrukcí atd.). Virtuální stroj je již nasazen v předmětu NI-GEN (generování kódu) na FIT ČVUT, kde jeho jednoduchost dovoluje studentům během semestru psát kompletní kompilátor.