9 citations · 14 across the 11 of their papers we have counts for
15 papers
Bounds on Functionality and Symmetric Difference -- Two Intriguing Graph Parameters
Pavel Dvořák, Lukáš Folwarczný, Michal Opler +3
Functionality () is a graph parameter that generalizes graph degeneracy defined by Alecu et al. [JCTB, 2021]. They research the relation of functionality to many othe…
Improved Weighted Matching in the Sliding Window Model
Cezar-Mihail Alexandru, Pavel Dvořák, Christian Konrad +1
We consider the Maximum-weight Matching (MWM) problem in the streaming sliding window model of computation. In this model, the input consists of a sequence of weighted edges on a g…
List Locally Surjective Homomorphisms in Hereditary Graph Classes
Pavel Dvořák, Monika Krawczyk, Tomáš Masařík +3
A locally surjective homomorphism from a graph to a graph is an edge-preserving mapping from to that is surjective in the neighborhood of each vertex in .…
Bears with Hats and Independence Polynomials
Václav Blažej, Pavel Dvořák, Michal Opler
Consider the following hat guessing game. A bear sits on each vertex of a graph , and a demon puts on each bear a hat colored by one of colors. Each bear sees only the hat c…
Data Structures Lower Bounds and Popular Conjectures
Pavel Dvořák, Michal Koucký, Karel Král +1
In this paper, we investigate the relative power of several conjectures that attracted recently lot of interest. We establish a connection between the Network Coding Conjecture (NC…
Barrington Plays Cards: The Complexity of Card-based Protocols
Pavel Dvořák, Michal Koucký
In this paper we study the computational complexity of functions that have efficient card-based protocols. Card-based protocols were proposed by den Boer [EUROCRYPT '89] as a means…
Parameterized Inapproximability of Independent Set in -Free Graphs
Pavel Dvořák, Andreas Emil Feldmann, Ashutosh Rai +1
We study the Independent Set (IS) problem in -free graphs, i.e., graphs excluding some fixed graph as an induced subgraph. We prove several inapproximability results both fo…
Lower Bounds for Semi-adaptive Data Structures via Corruption
Pavel Dvořák, Bruno Loff
In a dynamic data structure problem we wish to maintain an encoding of some data in memory, in such a way that we may efficiently carry out a sequence of queries and updates to the…
On Induced Online Ramsey Number of Paths, Cycles, and Trees
Václav Blažej, Pavel Dvořák, Tomáš Valla
An online Ramsey game is a game between Builder and Painter, alternating in turns. They are given a graph and a graph of an infinite set of independent vertices. In each ro…
Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop +3
We study the Steiner Tree problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensive…
Solving Integer Linear Programs with a Small Number of Global Variables and Constraints
Pavel Dvořák, Eduard Eiben, Robert Ganian +2
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 understand…
Anti-Path Cover on Sparse Graph Classes
Pavel Dvořák, Dušan Knop, Tomáš Masařík
We show that it is possible to use Bondy-Chvatal closure to design an FPT algorithm that decides whether or not it is possible to cover vertices of an input graph by at most k vert…
Target Set Selection in Dense Graph Classes
Pavel Dvořák, Dušan Knop, Tomáš Toufar
In this paper, we study the Target Set Selection problem from a parameterized complexity perspective. Here for a given graph and a threshold for each vertex, the task is to find a…
Automorphisms of the Cube
Pavel Dvořák, Tomáš Valla
Consider a hypergraph where the vertices are points of the -dimensional combinatorial cube and the edges are all sets of points such that they are in one line.…
Parameterized complexity of length-bounded cuts and multi-cuts
Dušan Knop, Pavel Dvořák
We show that the Minimal Length-Bounded L-But problem can be computed in linear time with respect to L and the tree-width of the input graph as parameters. In this problem the task…