Ing. Jan Pokorný

Stať ve sborníku

10.65109/MBRB4492

Katedra teoretické informatiky

In approval elections, two candidates are called perfect clones if they are approved by exactly the same set of voters. We propose a general framework for studying approximations of this notion, and demonstrate its power using two natural approximation measures with various appealing axiomatic properties. For both of these measures, we consider two fundamental tasks: deciding whether a large approximate clone set exists in a given election, and computing a partition of the candidate set into approximate clone sets. We show that both tasks are, in general, computationally intractable. To have a better understanding of the boundary between tractable and intractable instances, we analyze the parameterized complexity of these problems with respect to several parameters, including the number of voters and candidates, the approximation threshold, the number and size of partition parts, and structural properties of the instances, such as the number of approvals per voter or per candidate. Finally, we explore how our approximation measures behave in real-world approval elections.

Stať ve sborníku

10.65109/TNYC5178

Katedra teoretické informatiky

An election is a pair (C,V) of candidates and voters. Each vote is a ranking (permutation) of the candidates. An election is d-Euclidean if there is an embedding of both candidates and voters into ℝd such that voter v prefers candidate a over b if and only if a is closer to v than b is to v in the embedding. For d ≥ 2 the problem of deciding whether (C,V) is d-Euclidean is ∃ℝ-complete. In this paper, we propose a practical approach to recognizing and refuting 2-Euclidean preferences. We design a new class of forbidden substructures that works very well on practical instances. We utilize the framework of integer linear programming (ILP) and quadratically constrained programming (QCP). We also introduce reduction rules that simplify many real-world instances significantly. Our approach beats the previous algorithm of Escoffier, Spanjaard and Tydrichová [Algorithmic Recognition of 2-Euclidean Preferences, ECAI 2023] both in number of resolved instances and the running time. In particular, we were able to lower the number of unresolved PrefLib instances from 343 to 60. Moreover, 98.7% of PrefLib instances are resolved in under 1 second using our approach.

Stať ve sborníku

Katedra teoretické informatiky

We study the complexity of candidate control in participatory budgeting elections. The goal of constructive candidate control is to ensure that a given candidate wins by either adding or deleting candidates from the election (in the destructive setting, the goal is to prevent a given candidate from winning). We show that such control problems are NP-hard to solve for many participatory budgeting voting rules, including Phragmén and Method of Equal Shares, but there are natural cases with polynomial-time algorithms (e.g., for the GreedyAV rule and projects with costs encoded in unary). We also argue that control by deleting candidates is a useful tool for assessing the performance (or, strength) of initially losing projects.

Stať ve sborníku

10.24963/ijcai.2025/425

Katedra teoretické informatiky

We study the complexity of candidate control in participatory budgeting elections. The goal of constructive candidate control is to ensure that a given candidate wins by either adding or deleting candidates from the election (in the destructive setting, the goal is to prevent a given candidate from winning). We show that such control problems are NP-hard to solve for many participatory budgeting voting rules, including Phragmén and MES, but there are natural cases with polynomial-time algorithms (e.g., for the GreedyAV rule and projects with costs encoded in unary). We also argue that control by deleting candidates is a useful tool for assessing the performance (or, strength) of initially losing projects, and we support this view with experiments.

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.MFCS.2024.29

Katedra teoretické informatiky

In the Equitable Connected Partition (ECP for short) problem, we are given a graph $G=(V,E)$ together with an integer $p\in\mathbb{N}$, and our goal is to find a partition of~$V$ into~$p$~parts such that each part induces a connected sub-graph of $G$ and the size of each two parts differs by at most~$1$. On the one hand, the problem is known to be NP-hard in general and W[1]-hard with respect to the path-width, the feedback-vertex set, and the number of parts~$p$ combined. On the other hand, fixed-parameter algorithms are known for parameters the vertex-integrity and the max leaf number. In this work, we systematically study ECP with respect to various structural restrictions of the underlying graph and provide a clear dichotomy of its parameterised complexity. Specifically, we show that the problem is in FPT when parameterized by the modular-width and the distance to clique. Next, we prove W[1]-hardness with respect to the distance to cluster, the $4$-path vertex cover number, the distance to disjoint paths, and the feedback-edge set, and NP-hardness for constant shrub-depth graphs. Our hardness results are complemented by matching algorithmic upper-bounds: we give an XP algorithm for parameterisation by the tree-width and the distance to cluster. We also give an improved FPT algorithm for parameterisation by the vertex integrity and the first explicit FPT algorithm for the $3$-path vertex cover number. The main ingredient of these algorithms is a formulation of ECP as $N$-fold IP, which clearly indicates that such formulations may, in certain scenarios, significantly outperform existing algorithms based on the famous algorithm of Lenstra.

Stať ve sborníku

10.1609/aaai.v37i5.25771

Katedra teoretické informatiky

Microaggregation is a classical statistical disclosure control technique which requires the input data to be partitioned into clusters while adhering to specified size constraints. We provide novel exact algorithms and lower bounds for the task of microaggregating a given network while considering both unrestricted and connected clusterings, and analyze these from the perspective of the parameterized complexity paradigm. Altogether, our results assemble a complete complexity-theoretic picture for the network microaggregation problem with respect to the most natural parameterizations of the problem, including input-specified parameters capturing the size and homogeneity of the clusters as well as the treewidth and vertex cover number of the network.