Mgr. Michal Opler, Ph.D.

Stať ve sborníku

10.4230/LIPIcs.ESA.2026.92

Katedra teoretické informatiky

Pattern-avoiding permutations are a central object of study in both combinatorics and theoretical computer science. In this paper we design a data structure that can store any size-n permutation τ that avoids an arbitrary (and unknown) fixed pattern π in the asymptotically optimal 𝒪(n lg{s_π}) bits, where s_π is the Stanley-Wilf limit of π. Our data structure supports τ(i) and τ^{-1}(i) queries in 𝒪(1) time, sidestepping the lower bounds that hold for general permutations. Comparable results were previously known only in more restricted cases, e.g., when τ is separable, which means avoiding the patterns 2413 and 3142. We also extend our data structure to support more complex geometric queries on pattern-avoiding permutations (or planar point sets) such as rectangle range counting in 𝒪(lg lg n) time. This result circumvents the lower bound of Ω(lg{n}/lg lg{n}) by Pătraşcu (STOC 2007) for the general case. For bounded treewidth permutation classes (which include the above-mentioned separable class), we further reduce the space overhead to a lower order additive term, making our data structure succinct. This extends and improves results of Chakraborty et al. (ISAAC 2024) obtained for separable permutations via different techniques. All our data structures can be constructed in linear time.

Stať ve sborníku

10.1609/aaai.v40i17.38435

Katedra teoretické informatiky

In their AAAI 2024 paper, Horiyama et al. studied the problem of generating graph instances that possess a unique minimum vertex cover under specific conditions. Their approach involved pre-assigning certain vertices to be part of the solution or excluding them from it. Notably, for the Vertex Cover problem, pre-assigning a vertex is equivalent to removing it from the graph. Horiyama et al. focused on maintaining the size of the minimum vertex cover after these modifications. In this work, we extend their study by relaxing this constraint: our goal is to ensure a unique minimum vertex cover, even if the removal of a vertex may not incur a decrease on the size of said cover. Surprisingly, our relaxation introduces significant theoretical challenges. We observe that the problem is Σ²_P-complete, and remains so even for planar graphs of maximum degree 5. Nevertheless, we provide a linear time algorithm for trees, which is then further leveraged to show that MU-VC is in FPT when parameterized by the combination of treewidth and maximum degree. Finally, we show that MU-VC is in XP when parameterized by clique-width while it is fixed-parameter tractable (FPT) if we add the size of the solution as part of the parameter.

Článek

10.1613/jair.1.19325

Katedra teoretické informatiky

Consider the scenario where multiple agents have to move in an optimal way through a network, each one towards their ending position while avoiding collisions. By optimal, we mean as fast as possible, which is evaluated by a measure known as the makespan of the proposed solution. This is the setting studied in the Multiagent Path Finding problem. In this work, we additionally provide the agents with a way to communicate with each other. Due to size constraints, it is reasonable to assume that the range of communication of each agent will be limited. What should be the trajectories of the agents to, additionally, maintain a backbone of communication? In this work, we study the Multiagent Path Finding with Communication Constraints problem under the parameterized complexity framework. Our main contribution is three exact algorithms that are efficient when considering particular structures for the input network. We provide such algorithms for the case when the communication range and the number of agents (the makespan resp.) are provided in the input and the network has a tree topology, or bounded maximum degree (has a tree-like topology, i.e., bounded treewidth resp.). We complement these results by showing that it is highly unlikely to construct efficient algorithms when considering the number of agents as part of the input, even if the makespan is 3 and the communication range is 1.

Stať ve sborníku

10.4230/LIPIcs.ICALP.2026.145

Katedra teoretické informatiky

Detecting and counting copies of permutation patterns are fundamental algorithmic problems, with applications in the analysis of rankings, nonparametric statistics, and property testing tasks such as independence and quasirandomness testing. From an algorithmic perspective, there is a sharp difference in complexity between detecting and counting the copies of a given length-k pattern in a length-n permutation. The former admits a 2^𝒪(k²) ⋅ n time algorithm (Guillemot and Marx, 2014) while the latter cannot be solved in time f(k) ⋅ n^o(k/log k) unless the Exponential Time Hypothesis (ETH) fails (Berendsohn, Kozma, and Marx, 2021). In fact already for patterns of length 4, exact counting is unlikely to admit near-linear time algorithms under standard fine-grained complexity assumptions (Dudek and Gawrychowski, 2020). Recently, Ben-Eliezer, Mitrović and Srivastava (2026) showed that for patterns of length up to 5, a (1+ε)-approximation of the pattern count can be computed in near-linear time, yielding a separation between exact and approximate counting for small patterns, and conjectured that approximate counting is asymptotically easier than exact counting in general. We strongly refute their conjecture by showing that, under ETH, no algorithm running in time f(k)⋅ n^o(k/log k) can approximate the number of copies of a length-k pattern within a multiplicative factor n^(1/2-ε)k. The lower bound on runtime matches the conditional lower bound for exact pattern counting, and the obtained bound on the multiplicative error factor is essentially tight, as an n^{k/2}-approximation can be computed in 2^𝒪(k²) ⋅ n time using an algorithm for pattern detection.

Stať ve sborníku

10.1609/aaai.v39i22.34483

Katedra teoretické informatiky

Consider the scenario where multiple agents have to move in an optimal way through a network, each one towards their ending position while avoiding collisions. By optimal, we mean as fast as possible, which is evaluated by a measure known as the makespan of the proposed solution. This is the setting studied in the Multiagent Path Finding problem. In this work, we additionally provide the agents with a way to communicate with each other. Due to size constraints, it is reasonable to assume that the range of communication of each agent will be limited. What should be the trajectories of the agents to, additionally, maintain a backbone of communication? In this work, we study the Multiagent Path Finding with Communication Constraint problem under the parameterized complexity framework. Our main contribution is three exact algorithms that are efficient when considering particular structures for the input network. We provide such algorithms for the case when the communication range and the number of agents (the makespan resp.) are provided in the input and the network has a tree topology, or bounded maximum degree (has a tree-like topology, i.e., bounded treewidth resp.). We complement these results by showing that it is highly unlikely to construct efficient algorithms when considering the number of agents as part of the input, even if the makespan is 3 and the communication range is 1.

Stať ve sborníku

10.4230/LIPIcs.ISAAC.2025.28

Katedra teoretické informatiky

In this paper, we study the problem of pathfinding on traversal-dependent graphs, i.e., graphs whose edges change depending on the previously visited vertices. In particular, we study self-deleting graphs, introduced by Carmesin et al. [Sarah Carmesin et al., 2023], which consist of a graph G = (V, E) and a function f: V → 2^E, where f(v) is the set of edges that will be deleted after visiting the vertex v. In the (Shortest) Self-Deleting s-t-path problem we are given a self-deleting graph and its vertices s and t, and we are asked to find a (shortest) path from s to t, such that it does not traverse an edge in f(v) after visiting v for any vertex v. We prove that Self-Deleting s-t-path is NP-hard even if the given graph is outerplanar, bipartite, has maximum degree 3, bandwidth 2 and |f(v)| ≤ 1 for each vertex v. We show that Shortest Self-Deleting s-t-path is W[1]-complete parameterized by the length of the sought path and that Self-Deleting s-t-path is W[1]-complete parameterized by the vertex cover number, feedback vertex set number and treedepth. We also show that the problem becomes FPT when we parameterize by the maximum size of f(v) and several structural parameters. Lastly, we show that the problem does not admit a polynomial kernel even for parameterization by the vertex cover number and the maximum size of f(v) combined already on 2-outerplanar graphs.

Stať ve sborníku

10.4230/LIPIcs.ISAAC.2025.23

Katedra teoretické informatiky

Let G be a graph with a set of precolored vertices, and let us be given an integer distance parameter d and a set of integer demands d₁,… ,d_c. The Distance Precoloring Extension with Demands (DPED) problem is to compute a vertex c-coloring of G such that the following three conditions hold: (i) the resulting coloring respects the colors of the precolored vertices, (ii) the distance of two vertices of the same color is at least d, and (iii) the number of vertices colored by color i is exactly d_i. This problem is motivated by a program scheduling in commercial broadcast channels with constraints on content repetition and placement, which leads precisely to the DPED problem for paths. In this paper, we study DPED on paths and present a polynomial time exact algorithm when precolored vertices are restricted to the two ends of the path and devise an approximation algorithm for DPED with an additive approximation factor polynomially bounded by d and the number of precolored vertices. Then, we prove that the Distance Precoloring Extension problem on paths, a less restrictive version of DPED without the demand constraints, and then DPED itself, is NP-complete. Motivated by this result, we further study the parameterized complexity of DPED on paths. We establish that the DPED problem on paths is W[1]-hard when parameterized by the number of colors and the distance. On the positive side, we devise a fixed parameter tractable (FPT) algorithm for DPED on paths when the number of colors, the distance, and the number of precolored vertices are considered as the parameters. Moreover, we prove that Distance Precoloring Extension is FPT parameterized by the distance. As a byproduct, we also obtain several results for the Distance List Coloring problem on paths.

Stať ve sborníku

10.1609/aaai.v39i22.34484

Katedra teoretické informatiky

The Mutliagent Path Finding (MAPF) problem consists of identifying the trajectories that a set of agents should follow inside a given network in order to reach their desired destinations as soon as possible, but without colliding with each other. We aim to minimize the maximum time any agent takes to reach their goal, ensuring optimal path length. In this work, we complement a recent thread of results that aim to systematically study the algorithmic behavior of this problem, through the parameterized complexity point of view. First, we show that MAPF is NP-hard when the given network has a star-like topology (bounded vertex cover number) or is a tree with 11 leaves. Both of these results fill important gaps in our understanding of the tractability of this problem that were left untreated in the recent work of [Fioravantes et al. Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology. AAAI'24]. Nevertheless, our main contribution is an exact algorithm that scales well as the input grows (FPT) when the topology of the given network is highly centralized (bounded distance to clique). This parameter is significant as it mirrors real-world networks. In such environments, a bunch of central hubs (e.g., processing areas) are connected to only few peripheral nodes.

Stať ve sborníku

10.1109/FOCS61266.2024.00049

Katedra teoretické informatiky

We present a deterministic comparison-based algorithm that sorts sequences avoiding a fixed permutation $\pi$ in linear time, even if $\pi$ is a priori unkown. Moreover, the dependence of the multiplicative constant on the pattern $\pi$ matches the information-theoretic lower bound. A crucial ingredient is an algorithm for performing efficient multi-way merge based on the Marcus-Tardos theorem. As a direct corollary, we obtain a linear-time algorithm for sorting permutations of bounded twin-width.

Stať ve sborníku

10.1609/aaai.v38i16.29686

Katedra teoretické informatiky

In the Multiagent Path Finding (MAPF for short) problem, we focus on efficiently finding non-colliding paths for a set of k agents on a given graph G, where each agent seeks a path from its source vertex to a target. An important measure of the quality of the solution is the length of the proposed schedule l, that is, the length of a longest path (including the waiting time). In this work, we propose a systematic study under the parameterized complexity framework. The hardness results we provide align with many heuristics used for this problem, whose running time could potentially be improved based on our Fixed-Parameter Tractability (FPT) results. We show that MAPF is W[1]-hard with respect to k (even if k is combined with the maximum degree of the input graph). The problem remains NP-hard in planar graphs even if the maximum degree and the makespan l are fixed constants. On the positive side, we show an FPT algorithm for k+l. As we continue, the structure of G comes into play. We give an FPT algorithm for parameter k plus the diameter of the graph G. The MAPF problem is W[1]-hard for cliquewidth of G plus l while it is FPT for treewidth of G plus l.

Článek

10.1007/s00453-024-01220-9

Katedra teoretické informatiky

A permutation π is a merge of a permutation σ and a permutation τ, if we can color the elements of π red and blue so that the red elements have the same relative order as σ and the blue ones as τ. We consider, for fixed hereditary permutation classes C and D, the complexity of determining whether a given permutation π is a merge of an element of C with an element of D. We develop general algorithmic approaches for identifying polynomially tractable cases of merge recognition. Our tools include a version of streaming recognizability of permutations via polynomially constructible nondeterministic automata, as well as a concept of bounded width decomposition, inspired by the work of Ahal and Rabinovich. As a consequence of the general results, we can provide nontrivial examples of tractable permutation merges involving commonly studied permutation classes, such as the class of layered permutations, the class of separable permutations, or the class of permutations avoiding a decreasing sequence of a given length. On the negative side, we obtain a general hardness result which implies, for example, that it is NP-complete to recognize the permutations that can be merged from two subpermutations avoiding the pattern 2413.

Stať ve sborníku

10.1145/3618260.3649631

Katedra teoretické informatiky

Permutation pattern-avoidance is a central concept of both enumerative and extremal combinatorics. In this paper we study the effect of permutation pattern-avoidance on the complexity of optimization problems. In the context of the dynamic optimality conjecture (Sleator, Tarjan, STOC 1983), Chalermsook, Goswami, Kozma, Mehlhorn, and Saranurak (FOCS 2015) conjectured that the amortized search cost of an optimal binary search tree (BST) is constant whenever the search sequence is pattern-avoiding. The best known bound to date is 2α(n)(1+o(1)) recently obtained by Chalermsook, Pettie, and Yingchareonthawornchai (SODA 2024); here n is the BST size and α(·) the inverse-Ackermann function. In this paper we resolve the conjecture, showing a tight (1) bound. This indicates a barrier to dynamic optimality: any candidate online BST (e.g., splay trees or greedy trees) must match this optimum, but current analysis techniques only give superconstant bounds. More broadly, we argue that the easiness of pattern-avoiding input is a general phenomenon, not limited to BSTs or even to data structures. To illustrate this, we show that when the input avoids an arbitrary, fixed, a priori unknown pattern, one can efficiently compute: (1) a k-server solution of n requests from a unit interval, with total cost n(1/logk), in contrast to the worst-case Θ(n/k) bound, and (2) a traveling salesman tour of n points from a unit box, of length (logn), in contrast to the worst-case Θ(√n) bound; similar results hold for the euclidean minimum spanning tree, Steiner tree, and nearest-neighbor graphs. We show both results to be tight. Our techniques build on the Marcus-Tardos proof of the Stanley-Wilf conjecture, and on the recently emerging concept of twin-width.

Stať ve sborníku

10.1137/1.9781611977912.59

Katedra teoretické informatiky

We consider the following general model of a sorting procedure: we fix a hereditary permutation class C, which corresponds to the operations that the procedure is allowed to perform in a single step. The input of sorting is a permutation π of the set [n] = {1, 2,…,n}, i.e., a sequence where each element of [n] appears once. In every step, the sorting procedure picks a permutation σ of length n from C, and rearranges the current permutation of numbers by composing it with σ. The goal is to transform the input π into the sorted sequence 1, 2,…,n in as few steps as possible. Formally, for a hereditary permutation class C and a permutation π of [n], we say that C can sort π in k steps, if the inverse of π can be obtained by composing k (not necessarily distinct) permutations from C. The C-sorting time of π, denoted st(C; π), is the smallest k such that C can sort π in k steps; if no such k exists, we put st(C; π) = +∞. For an integer n, the worst-case C-sorting time, denoted wst(C; n), is the maximum of st(C; π) over all permutations π of [n]. This model of sorting captures not only classical sorting algorithms, like insertion sort or bubble sort, but also sorting by series of devices, like stacks or parallel queues, as well as sorting by block operations commonly considered, e.g., in the context of genome rearrangement. Our goal is to describe the possible asymptotic behavior of the function wst(C; n), and relate it to structural properties of C. As the main result, we show that any hereditary permutation class C falls into one of the following five categories: • wst(C; n) = +∞ for n large enough, • wst(C; n) = Θ(n2), • Ω(√n) ≤ wst(C; n) ≤ O(n), • Ω(log n) ≤ wst(C; n) ≤ O(log2 n), or • wst(C; n) = 1 for all n ≥ 2. In addition, we characterize the permutation classes in each of the five categories.

Článek

10.46298/DMTCS.10802

Katedra teoretické informatiky

Consider the following hat guessing game. A bear sits on each vertex of a graph G, and a demon puts on each bear a hat colored by one of h colors. Each bear sees only the hat colors of his neighbors. Based on this information only, each bear has to guess g colors and he guesses correctly if his hat color is included in his guesses. The bears win if at least one bear guesses correctly for any hat arrangement. We introduce a new parameter - fractional hat chromatic number μ^, arising from the hat guessing game. The parameter μ^ is related to the hat chromatic number which has been studied before. We present a surprising connection between the hat guessing game and the independence polynomial of graphs. This connection allows us to compute the fractional hat chromatic number of chordal graphs in polynomial time, to bound fractional hat chromatic number by a function of maximum degree of G, and to compute the exact value of μ^ of cliques, paths, and cycles.

Stať ve sborníku

10.1007/978-3-031-43380-1_22

Katedra teoretické informatiky

[Alecu et al.: Graph functionality, JCTB2021] define functionality, a graph parameter that generalizes graph degeneracy. They research the relation of functionality to many other graph parameters (tree-width, clique-width, VC-dimension, etc.). Extending their research, we prove logarithmic lower bound for functionality of the random graph~$G(n,1/2)$. Previously known graphs have functionality logarithmic in number of vertices. We show that for every graph~$G$ on~$n$ vertices we have $\mathrm{fun}(G) \le O(\sqrt{n \log n})$ and we give a nearly matching $\Omega(\sqrt{n})$-lower bound provided by projective planes. Further, we study a related graph parameter \emph{symmetric difference}, the minimum of $|N(u) \Delta N(v)|$ over all pairs of vertices of the ``worst possible'' induced subgraph. It was observed by Alecu et al. that $\mathrm{fun}(G) \le \mathrm{sd}(G)+1$ for every graph~$G$. We compare $\mathrm{fun}$ and $\mathrm{sd}$ for the class~$\mathrm{INT}$ of interval graphs and $\mathrm{CA}$ of circular-arc graphs. We let $\mathrm{INT}_n$ denote the $n$-vertex interval graphs, similarly for $\mathrm{CA}_n$. Alecu et al. ask, whether $\mathrm{fun}(\mathrm{INT})$ is bounded. Dallard et al. answer this positively in a recent preprint. On the other hand, we show that $\Omega(\sqrt[4]{n}) \leq \sd(\mathrm{INT}_n) \leq O(\sqrt[3]{n})$. For the related class $\mathrm{CA}$ we show that $\mathrm{sd}(\mathrm{CA}_n) = \Theta(\sqrt{n})$. We propose a follow-up question: is $\mathrm{fun}(\mathrm{CA})$ bounded?

Stať ve sborníku

10.1007/978-3-031-49193-1_16

Katedra teoretické informatiky

We improve bounds for the binary paint shop problem posed by Meunier and Neveu [Computing solutions of the paintshop-necklace problem. Comput. Oper. Res. 39, 11 (2012), 2666-2678]. In particular, we disprove their conjectured upper bound for the number of color changes by giving a linear lower bound. We show that the recursive greedy heuristics is not optimal by providing a tiny improvement. We also introduce a new heuristics, recursive star greedy, that a preliminary analysis shows to be 10% better.