The Hierarchy of Hereditary Sorting Operators
Autoři
Jelínek, V.; Opler, M.; Pekárek, J.
Rok
2024
Publikováno
Proceedings of the 35th ACM-SIAM Symposium on Discrete Algorithms, SODA ’24. Philadelphia: SIAM, 2024. p. 1447-1464. ISBN 978-1-61197-791-2.
Typ
Stať ve sborníku
Pracoviště
Anotace
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.
The Complexity of Fair Division of Indivisible Items with Externalities
Autoři
Deligkas, A.; Eiben, E.; Korchemna, V.; Schierreich, Š.
Rok
2024
Publikováno
Proceedings of the 38th AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2024. p. 9653-9661. ISSN 2159-5399.
Typ
Stať ve sborníku
Pracoviště
Anotace
We study the computational complexity of fairly allocating a set of indivisible items under externalities. In this recently-proposed setting, in addition to the utility the agent gets from their bundle, they also receive utility from items allocated to other agents.
We focus on the extended definitions of envy-freeness up to one item (EF1) and of envy-freeness up to any item (EFX), and we provide the landscape of their complexity for several different scenarios. We prove that it is NP-complete to decide whether there exists an EFX allocation, even when there are only three agents, or even when there are only six different values for the items.
We complement these negative results by showing that when both the number of agents and the number of different values for items are bounded by a parameter the problem becomes fixed-parameter tractable. Furthermore, we prove that two-valued and binary-valued instances are equivalent and that EFX and EF1 allocations coincide for this class of instances. Finally, motivated from real-life scenarios, we focus on a class of structured valuation functions, which we term agent/item-correlated. We prove their equivalence to the "standard" setting without externalities. Therefore, all previous results for EF1 and EFX apply immediately for these valuations.
Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology
Autoři
Rok
2024
Publikováno
Proceedings of the 38th AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2024. p. 17380-17388. ISSN 2159-5399.
Typ
Stať ve sborníku
Pracoviště
Anotace
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.
The Parameterized Complexity of Maximum Betweenness Centrality
Autoři
Schierreich, Š.; Smutný, J.G.
Rok
2024
Publikováno
Proceedings of the 18th Annual Conference on Theory and Applications of Models of Computation, TAMC 2024. Springer Nature Singapore Pte Ltd., 2024. p. 221-233. Lecture Notes in Computer Science. vol. 14637. ISSN 0302-9743. ISBN 978-981-97-2339-3.
Typ
Stať ve sborníku
Pracoviště
Anotace
Arguably, one of the most central tasks in the area of social network analysis is to identify important members and communities of a given network. The importance of an agent is traditionally measured using some well-defined notion of centrality. In this work, we focus on betweenness centrality, which is based on the number of shortest paths that an agent intersects. This measure can be naturally generalized from a single agent to a group of agents.
Specifically, we study the computation complexity of the k-Maximum Betweenness Centrality problem, which consists in finding a group of size $k$ whose betweenness centrality exceeds a given threshold. Since this problem is NP-complete in general, we use the framework of parameterized complexity to reveal at least some tractable fragments. From this perspective, we show that the problem is W[1]-hard and in XP when parameterized by the group size $k$. As the threshold value is not a useful parameter in this context, we focus on the structural restrictions of the underlying social network. In this direction, we show that the problem admits FPT algorithms with respect to the vertex cover number, the distance to clique, or the twin-cover number and the group size combined.
Cluster Editing in Multi-Layer and Temporal Graphs
Autoři
Chen, J.; Molter, H.; Sorge, M.; Suchý, O.
Rok
2018
Publikováno
29th International Symposium on Algorithms and Computation (ISAAC 2018). Saarbrücken: Dagstuhl Publishing,, 2018. p. 24:1-24:13. Leibniz International Proceedings in Informatics (LIPIcs). vol. 123. ISSN 1868-8969. ISBN 978-3-95977-094-1.
Typ
Stať ve sborníku
Pracoviště
Anotace
Motivated by the recent rapid growth of research for algorithms to cluster multi-layer and temporal graphs, we study extensions of the classical Cluster Editing problem. In Multi-Layer Cluster Editing we receive a set of graphs on the same vertex set, called layers and aim to transform all layers into cluster graphs (disjoint unions of cliques) that differ only slightly. More specifically, we want to mark at most d vertices and to transform each layer into a cluster graph using at most k edge additions or deletions per layer so that, if we remove the marked vertices, we obtain the same cluster graph in all layers. In Temporal Cluster Editing we receive a sequence of layers and we want to transform each layer into a cluster graph so that consecutive layers differ only slightly. That is, we want to transform each layer into a cluster graph with at most k edge additions or deletions and to mark a distinct set of d vertices in each layer so that each two consecutive layers are the same after removing the vertices marked in the first of the two layers. We study the combinatorial structure of the two problems via their parameterized complexity with respect to the parameters d and k, among others. Despite the similar definition, the two problems behave quite differently: In particular, Multi-Layer Cluster Editing is fixed-parameter tractable with running time k^{O(k + d)} s^{O(1)} for inputs of size s, whereas Temporal Cluster Editing is W[1]-hard with respect to k even if d = 3.
Average-case complexity of a branch-and-bound algorithm for MIN DOMINATING SET
Autoři
Denat, T.; Harutyunyan, A.; Melissinos, N.; Paschos, V. T..
Rok
2024
Publikováno
Discrete Applied Mathematics. 2024, 345 4-8. ISSN 0166-218X.
Typ
Článek
Pracoviště
Anotace
The average-case complexity of a branch-and-bound algorithm for MIN DOMINATING SET problem in random graphs in the G(n, p) model is studied. We identify phase transitions between subexponential and exponential average-case complexities, depending on the growth of the probability p with respect to the number n of nodes. (c) 2023 Elsevier B.V. All rights reserved.
Polynomial kernels for tracking shortest paths
Autoři
Rok
2023
Publikováno
Information Processing Letters. 2023, 179(1), ISSN 1872-6119.
Typ
Článek
Pracoviště
Anotace
Given an undirected graph G = (V , E), vertices s,t ∈ V , and an integer k, Tracking
Shortest Paths requires deciding whether there exists a set of k vertices T ⊆ V such
that for any two distinct shortest paths between s and t, say P1 and P2, we have
T ∩ V (P1) != T ∩ V (P2). In this paper, we give the first polynomial size kernel for the
problem. Specifically we show the existence of a kernel with O(k2) vertices and edges in
general graphs and a kernel with O(k) vertices and edges in planar graphs for the Tracking Paths in DAG problem. This problem admits a polynomial parameter transformation to Tracking Shortest Paths, and this implies a kernel with O(k4) vertices and edges for Tracking Shortest Paths in general graphs and a kernel with O(k2) vertices and edges in planar graphs. Based on the above we also give a single exponential algorithm for Tracking Shortest Paths in planar graphs.
Minimum Eccentricity Shortest Path Problem with Respect to Structural Parameters
Autoři
Kučera, M.; Suchý, O.
Rok
2023
Publikováno
Algorithmica. 2023, 85(3), 762-782. ISSN 0178-4617.
Typ
Článek
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 treewidth with the desired eccentricity, and maximum leaf number.
Constant factor approximation for tracking paths and fault tolerant feedback vertex set
Autoři
Rok
2023
Publikováno
Discrete Optimization. 2023, 47 ISSN 1572-5286.
Typ
Článek
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 6-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) approximation algorithm for r-FAULT TOLERANT FEEDBACK VERTEX SET if r is a constant.
Maximizing Influence Spread through a Dynamic Social Network
Autoři
Rok
2023
Publikováno
Proceedings of the 37th AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2023. p. 16316-16317. ISSN 2159-5399.
Typ
Stať ve sborníku
Pracoviště
Anotace
Modern social networks are dynamic in their nature; new connections are appearing and old connections are disappearing all the time. However, in our algorithmic and complexity studies, we usually model social networks as static graphs.
In this paper, we propose a new paradigm for the study of the well-known Target Set Selection problem, which is a fundamental problem in viral marketing and the spread of opinion through social networks. In particular, we use temporal graphs to capture the dynamic nature of social networks.
We show that the temporal interpretation is, unsurprisingly, NP-complete in general. Then, we study computational complexity of this problem for multiple restrictions of both the threshold function and the underlying graph structure and provide multiple hardness lower-bounds.
Bribery Can Get Harder in Structured Multiwinner Approval Election
Autoři
Kusek, B.; Bredereck, R.; Faliszewski, P.; Kaczmarczyk, A.; Knop, D.
Rok
2023
Publikováno
Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2023. County of Richland: IFAAMAS, 2023. p. 1725-1733. ISSN 1548-8403. ISBN 978-1-4503-9432-1.
Typ
Stať ve sborníku
Pracoviště
Anotace
We study the complexity of constructive bribery in the context of structured multiwinner approval elections. Given such an election, we ask whether a certain candidate can join the winning committee by adding, deleting, or swapping approvals, where each such action comes at a cost and we are limited by a budget. We assume our elections to either have the candidate interval or the voter interval property, and we require the property to hold also after the bribery. While structured elections usually make manipulative attacks significantly easier, our work also shows examples of the opposite behavior. We conclude by presenting preliminary insights regarding the destructive variant of our problem.
Host Community Respecting Refugee Housing
Autoři
Rok
2023
Publikováno
Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2023. County of Richland: IFAAMAS, 2023. p. 966-975. ISSN 1548-8403. ISBN 978-1-4503-9432-1.
Typ
Stať ve sborníku
Pracoviště
Anotace
We propose a novel model for refugee housing respecting the preferences of the accepting community and the refugees themselves. In particular, we are given a topology representing the local community, a set of inhabitants occupying some vertices of topology, and a set of refugees that should be placed on the empty vertices of the graph. Both the inhabitants and the refugees have preferences over the structure of their neighbourhood.
We are specifically interested in the problem of finding placements such that the preferences of every individual are met; using game-theoretical words, we are looking for placements that are stable with respect to some well-defined notion of stability. We investigate conditions under which the existence of equilibrium is guaranteed and study the computational complexity of finding such a stable outcome. As the problem is NP-hard even in very simple settings, we employ the parameterised complexity framework to give a finer-grained view on the problem's complexity with respect to natural parameters and structural restrictions of the given topology.
Fine-grained view on bribery for group identification
Autoři
Boehmer, N.; Bredereck, R.; Knop, D.; Luo, J.
Rok
2023
Publikováno
Autonomous Agents and Multi-Agent Systems. 2023, 37(1), ISSN 1387-2532.
Typ
Článek
Pracoviště
Anotace
Given a set of agents qualifying or disqualifying each other, group identification is the task of identifying a socially qualified subgroup of agents. Social qualification depends on the specific rule used to aggregate individual qualifications . The classical bribery problem in this context asks how many agents need to change their qualifications in order to change the outcome in a certain way. Complementing previous results showing polynomial-time solvability or NP-hardness of bribery for various social rules in the constructive (aiming at making specific agents socially qualified) or destructive (aiming at making specific agents 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, nonunit prices for different bribery actions, and a more general bribery goal that combines the constructive and destructive setting.
Generating Faster Algorithms for d-Path Vertex Cover
Autoři
Červený, R.; Suchý, O.
Rok
2023
Publikováno
Proceedings of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science. Cham: Springer, 2023. p. 157-171. Lecture Notes in Computer Science. vol. 14093. ISSN 1611-3349. ISBN 978-3-031-43380-1.
Typ
Stať ve sborníku
Pracoviště
Anotace
Many algorithms which exactly solve hard problems require branching on more or less complex structures in order to do their job. Those who design such algorithms often find themselves doing a meticulous analysis of numerous different cases in order to identify these structures and design suitable branching rules, all done by hand. This process tends to be error prone and often the resulting algorithm may be difficult to implement in practice.
In this work, we aim to automate a part of this process and focus on the simplicity of the resulting implementation.
We showcase our approach on the following problem.
For a constant d, the d-Path Vertex Cover problem (d-PVC) is as follows: Given an undirected graph and an integer k, find a subset of at most k vertices of the graph, such that their deletion results in a graph not containing a path on d vertices as a subgraph.
We develop a fully automated framework to generate parameterized branching algorithms for the problem and obtain algorithms outperforming those previously known for 3 < d < 8, e.g., we show that 5-PVC can be solved in O(2.7^kn^{O(1)}) time.
Bounds on Functionality and Symmetric Difference – Two Intriguing Graph Parameters
Autoři
Dvořák, P.; Folwarczný, L.; Opler, M.; Pudlák, P.; Šámal, R.; Vu, T.A.
Rok
2023
Publikováno
Proceedings of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science. Cham: Springer, 2023. p. 305-318. Lecture Notes in Computer Science. vol. 14093. ISSN 0302-9743. ISBN 978-3-031-43379-5.
Typ
Stať ve sborníku
Pracoviště
Anotace
[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?
Odd Chromatic Number of Graph Classes
Autoři
Belmonte, R.; Harutyunyan, A.; Köhler, N.; Melissinos, N.
Rok
2023
Publikováno
Proceedings of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science. Cham: Springer, 2023. p. 44-58. Lecture Notes in Computer Science. vol. 14093. ISSN 0302-9743. ISBN 978-3-031-43379-5.
Typ
Stať ve sborníku
Pracoviště
Anotace
A graph is called odd (respectively, even) if every vertex has odd (respectively, even) degree. Gallai proved that every graph can be partitioned into two even induced subgraphs, or into an odd and an even induced subgraph. We refer to a partition into odd subgraphs as an odd colouring of G. Scott [Graphs and Combinatorics, 2001] proved that a graph admits an odd colouring if and only if it has an even number of vertices. We say that a graph G is k-odd colourable if it can be partitioned into at most k odd induced subgraphs. We initiate the systematic study of odd colouring and odd chromatic number of graph classes. In particular, we consider for a number of classes whether they have bounded odd chromatic number. Our main results are that interval graphs, graphs of bounded modular-width and graphs of bounded maximum degree all have bounded odd chromatic number.
A categorical account of composition methods in logic
Autoři
Jakl, T.; Marsden, D.; Shah, N.
Rok
2023
Publikováno
2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE Xplore, 2023. p. 1-14. ISSN 2575-5528. ISBN 979-8-3503-3587-3.
Typ
Stať ve sborníku
Pracoviště
Anotace
We present a categorical theory of the composition methods in finite model theory – a key technique enabling modular reasoning about complex structures by building them out of simpler components. The crucial results required by the composition methods are Feferman–Vaught–Mostowski (FVM) type theorems, which characterize how logical equivalence be- haves under composition and transformation of models.
Our results are developed by extending the recently introduced game comonad semantics for model comparison games. This level of abstraction allow us to give conditions yielding FVM type results in a uniform way. Our theorems are parametric in the classes of models, logics and operations involved. Furthermore, they naturally account for the positive existential fragment, and extensions with counting quantifiers of these logics. We also reveal surprising connections between FVM type theorems, and classical concepts in the theory of monads.
We illustrate our methods by recovering many classical theorems of practical interest, including a refinement of a previous result by Dawar, Severini, and Zapata concerning the 3-variable counting logic and cospectrality. To highlight the importance of our techniques being parametric in the logic of interest, we prove a family of FVM theorems for products of structures, uniformly in the logic in question, which cannot be done using specific game arguments.
Maximizing Social Welfare in Score-Based Social Distance Games
Autoři
Rok
2023
Publikováno
Proceedings of the 19th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2023. Sydney: Open Publishing Association, 2023. p. 272-286. Electronic Proceedings in Theoretical Computer Science. vol. 379. ISSN 2075-2180.
Typ
Stať ve sborníku
Pracoviště
Anotace
Social distance games have been extensively studied as a coalition formation model where the utilities of agents in each coalition were captured using a utility function u that took into account distances in a given social network. In this paper, we consider a non-normalized score-based definition of social distance games where the utility function u_v depends on a generic scoring vector v, which may be customized to match the specifics of each individual application scenario.
As our main technical contribution, we establish the tractability of computing a welfare-maximizing partitioning of the agents into coalitions on tree-like networks, for every score-based function u_v. We provide more efficient algorithms when dealing with specific choices of u_v or simpler networks, and also extend all of these results to computing coalitions that are Nash stable or individually rational. We view these results as a further strong indication of the usefulness of the proposed score-based utility function: even on very simple networks, the problem of computing a welfare-maximizing partitioning into coalitions remains open for the originally considered canonical function u.
High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming
Autoři
Bredereck, R.; Kaczmarczyk, A.; Knop, D.; Niedermeier, R.
Rok
2023
Publikováno
European Conference on Artificial Intelligence 2023. Amsterdam: IOS Press, 2023. p. 303-310. Frontiers in Artificial Intelligence and Applications. vol. 372. ISSN 0922-6389. ISBN 978-1-64368-436-9.
Typ
Stať ve sborníku
Pracoviště
Anotace
Using insights from parametric integer linear programming, we improve the work of Bredereck et al. [Proc. ACM EC 2019] on high-multiplicity fair allocation. Answering an open question from their work, we proved that the problem of finding envy-free Pareto-efficient allocations of indivisible items is fixed-parameter tractable with respect to the combined parameter “number of agents” plus “number of item types.” Our central improvement, compared to their result, is to break the condition that the corresponding utility and multiplicity values have to be encoded in unary, which is required there. Concretely, we show that, while preserving fixed-parameter tractability, these values can be encoded in binary. Thus, we substantially expand the range of feasible utility and multiplicity values.
Shortest Dominating Set Reconfiguration under Token Sliding
Autoři
Křišťan, J.; Svoboda, J.
Rok
2023
Publikováno
Proceedings of the 24th International Symposium on Fundamentals of Computation Theory. Springer, Cham, 2023. p. 333-347. ISSN 0302-9743. ISBN 978-3-031-43586-7.
Typ
Stať ve sborníku
Pracoviště
Anotace
In this paper, we present novel algorithms that efficiently compute a shortest reconfiguration sequence between two given dominating sets in trees and interval graphs under the Token Sliding model. In this problem, a graph is provided along with its two dominating sets, which can be imagined as tokens placed on vertices. The objective is to find a shortest sequence of dominating sets that transforms one set into the other, with each set in the sequence resulting from sliding a single token in the previous set. While identifying any sequence has been well studied, our work presents the first polynomial algorithms for this optimization variant in the context of dominating sets.
Parameterized Max Min Feedback Vertex Set
Autoři
Lampis, M.; Melissinos, N.; Vasilakis, M.
Rok
2023
Publikováno
Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science. Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2023. p. 62:1-62:15. vol. 272. ISSN 1868-8969. ISBN 978-3-95977-292-1.
Typ
Stať ve sborníku
Pracoviště
Anotace
Given a graph G and an integer k, Max Min FVS asks whether there exists a minimal set of vertices of size at least k whose deletion destroys all cycles. We present several results that improve upon the state of the art of the parameterized complexity of this problem with respect to both structural and natural parameters. Using standard DP techniques, we first present an algorithm of time tw^O(tw) n^O(1), significantly generalizing a recent algorithm of Gaikwad et al. of time vc^O(vc) n^O(1), where tw, vc denote the input graph’s treewidth and vertex cover respectively. Subsequently, we show that both of these algorithms are essentially optimal, since a vc^o(vc) n^O(1) algorithm would refute the ETH. With respect to the natural parameter k, the aforementioned recent work by Gaikwad et al. claimed an FPT branching algorithm with complexity 10^k n^O(1). We point out that this algorithm is incorrect and present a branching algorithm of complexity 9.34^k n^O(1).
Recontamination helps a lot to hunt a rabbit
Autoři
Dissaux, T.; Fioravantes, F.; Gahlawat, H.; Nisse, N.
Rok
2023
Publikováno
Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science. Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2023. p. 591-604. vol. 272. ISSN 1868-8969. ISBN 978-3-95977-292-1.
Typ
Stať ve sborníku
Pracoviště
Anotace
The \textsc{Hunters and Rabbit} game is played on a graph $G$ where the Hunter player shoots at $k$ vertices in every round while the Rabbit player occupies an unknown vertex and, if it is not shot, must move to a neighbouring vertex after each round. The Rabbit player wins if it can ensure that its position is never shot. The Hunter player wins otherwise. The hunter number $h(G)$ of a graph $G$ is the minimum integer $k$ such that the Hunter player has a winning strategy (i.e., allowing him to win whatever be the strategy of the Rabbit player). This game has been studied in several graph classes, in particular in bipartite graphs (grids, trees, hypercubes...), but the computational complexity of computing $h(G)$ remains open in general graphs and even in more restricted graph classes such as trees. To progress further in this study, we propose a notion of monotonicity (a well-studied and useful property in classical pursuit-evasion games such as Graph Searching games) for the \textsc{Hunters and Rabbit} game imposing that, roughly, a vertex that has already been shot ``must not host the rabbit anymore''. This allows us to obtain new results in various graph classes.
More precisely, let the monotone hunter number $mh(G)$ of a graph $G$ be the minimum integer $k$ such that the Hunter player has a monotone winning strategy. We show that $pw(G) \leq mh(G) \leq pw(G)+1$ for any graph $G$ with pathwidth $pw(G)$, which implies that computing $mh(G)$, or even approximating $mh(G)$ up to an additive constant, is \textsf{NP}-hard. Then, we show that $mh(G)$ can be computed in polynomial time in split graphs, interval graphs, cographs and trees. These results go through structural characterisations which allow us to relate the monotone hunter number with the pathwidth in some of these graph classes. In all cases, this allows us to specify the hunter number or to show that there may be an arbitrary gap between $h$ and $mh$, i.e., that monotonicity does not help. In particular, we show that, for every $k\geq 3$, there exists a tree $T$ with $h(T)=2$ and $mh(T)=k$. We conclude by proving that computing $h$ (resp., $mh$) is FPT~parameterised by the minimum size of a vertex cover.
Bandwidth Parameterized by Cluster Vertex Deletion Number
Autoři
Gima, T.; Kim, E.J.; Köhler, N.; Melissinos, N.; Vasilakis, M.
Rok
2023
Publikováno
Proceedings of the 18th International Symposium on Parameterized and Exact Computation. Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2023. p. 21:1-21:15. vol. 285. ISSN 1868-8969. ISBN 978-3-95977-305-8.
Typ
Stať ve sborníku vyzvaná či oceněná
Pracoviště
Anotace
Given a graph G and an integer b, Bandwidth asks whether there exists a bijection π from V(G) to {1, …, |V(G)|} such that max_{{u, v} ∈ E(G)} | π(u) - π(v) | ≤ b. This is a classical NP-complete problem, known to remain NP-complete even on very restricted classes of graphs, such as trees of maximum degree 3 and caterpillars of hair length 3. In the realm of parameterized complexity, these results imply that the problem remains NP-hard on graphs of bounded pathwidth, while it is additionally known to be W[1]-hard when parameterized by the treedepth of the input graph. In contrast, the problem does become FPT when parameterized by the vertex cover number of the input graph. In this paper, we make progress towards the parameterized (in)tractability of Bandwidth. We first show that it is FPT when parameterized by the cluster vertex deletion number cvd plus the clique number ω of the input graph, thus generalizing the previously mentioned result for vertex cover. On the other hand, we show that Bandwidth is W[1]-hard when parameterized only by cvd. Our results generalize some of the previous results and narrow some of the complexity gaps.
Treewidth Is NP-Complete on Cubic Graphs
Autoři
Rok
2023
Publikováno
Proceedings of the 18th International Symposium on Parameterized and Exact Computation. Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2023. p. 7:1-7:13. vol. 285. ISSN 1868-8969. ISBN 978-3-95977-305-8.
Typ
Stať ve sborníku
Pracoviště
Anotace
In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new and simpler proof of the NP-completeness of treewidth, and show that Treewidth remains NP-complete on subcubic induced subgraphs of the infinite 3-dimensional grid.
Hedonic Diversity Games: A Complexity Picture with More than Two Colors
Autoři
Rok
2023
Publikováno
Artificial Intelligence. 2023, 325 1-20. ISSN 0004-3702.
Typ
Článek
Pracoviště
Anotace
Hedonic diversity games are a variant of the classical hedonic games designed to better model a variety of questions concerning diversity and fairness. Previous works mainly targeted the case with two diversity classes (represented as colors in the model) and provided some initial complexity-theoretic and existential results concerning Nash and individually stable outcomes. Here, we design new algorithms accompanied with lower bounds which provide a comprehensive parameterized-complexity picture for computing Nash and individually stable outcomes with respect to the most natural parameterizations of the problem. Crucially, our results hold for general hedonic diversity games where the number of colors is not necessarily restricted to two, and show that---apart from two trivial cases---a necessary condition for tractability in this setting is that the number of colors is bounded by the parameter. Moreover, for the special case of two colors we resolve an open question asked in previous work~(Boehmer and Elkind, AAAI 2020).
Improved Bounds for the Binary Paint Shop Problem
Autoři
Hančl, J.; Kabela, A.; Opler, M.; Sosnovec, J.; Šámal, R.; Valtr, V.
Rok
2023
Publikováno
Computing and Combinatorics - 29th International Conference, COCOON 2023, Hawaii, HI, USA, December 15–17, 2023, Proceedings, Part II. Cham: Springer, 2023. p. 210-221. Lecture Notes in Computer Science. vol. 14423. ISSN 0302-9743. ISBN 978-3-031-49192-4.
Typ
Stať ve sborníku
Pracoviště
Anotace
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.
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.
Scheduling Kernels via Configuration LP
Autoři
Knop, D.; Koutecký, M.
Rok
2022
Publikováno
30th Annual European Symposium on Algorithms (ESA 2022). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2022. p. 73:1-73:15. Leibniz International Proceedings in Informatics (LIPIcs). vol. 244. ISSN 1868-8969. ISBN 978-3-95977-247-1.
Typ
Stať ve sborníku
Pracoviště
Anotace
Makespan minimization (on parallel identical or unrelated machines) is arguably the most natural and studied scheduling problem. A common approach in practical algorithm design is to reduce the size of a given instance by a fast preprocessing step while being able to recover key information even after this reduction. This notion is formally studied as kernelization (or simply, kernel) - a polynomial time procedure which yields an equivalent instance whose size is bounded in terms of some given parameter. It follows from known results that makespan minimization parameterized by the longest job processing time p_max has a kernelization yielding a reduced instance whose size is exponential in p_max. Can this be reduced to polynomial in p_max?
We answer this affirmatively not only for makespan minimization, but also for the (more complicated) objective of minimizing the weighted sum of completion times, also in the setting of unrelated machines when the number of machine kinds is a parameter.
Our algorithm first solves the Configuration LP and based on its solution constructs a solution of an intermediate problem, called huge N-fold integer programming. This solution is further reduced in size by a series of steps, until its encoding length is polynomial in the parameters. Then, we show that huge N-fold IP is in NP, which implies that there is a polynomial reduction back to our scheduling problem, yielding a kernel.
Our technique is highly novel in the context of kernelization, and our structural theorem about the Configuration LP is of independent interest. Moreover, we show a polynomial kernel for huge N-fold IP conditional on whether the so-called separation subproblem can be solved in polynomial time. Considering that integer programming does not admit polynomial kernels except for quite restricted cases, our "conditional kernel" provides new insight.
On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations
Autoři
Rok
2022
Publikováno
30th Annual European Symposium on Algorithms (ESA 2022). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2022. p. 22:1-22:16. Leibniz International Proceedings in Informatics (LIPIcs). vol. 244. ISSN 1868-8969. ISBN 978-3-95977-247-1.
Typ
Stať ve sborníku
Pracoviště
Anotace
For many problems, the important instances from practice possess certain structure that one should reflect in the design of specific algorithms. As data reduction is an important and inextricable part of today’s computation, we employ one of the most successful models of such precomputation - the kernelization. Within this framework, we focus on Traveling Salesperson Problem (TSP) and some of its generalizations.
We provide a kernel for TSP with size polynomial in either the feedback edge set number or the size of a modulator to constant-sized components. For its generalizations, we also consider other structural parameters such as the vertex cover number and the size of a modulator to constant-sized paths. We complement our results from the negative side by showing that the existence of a polynomial-sized kernel with respect to the fractioning number, the combined parameter maximum degree and treewidth, and, in the case of {Subset TSP}, modulator to disjoint cycles (i.e., the treewidth two graphs) is unlikely.
Multivariate Algorithmics for Eliminating Envy by Donating Goods
Autoři
Boehmer, N.; Bredereck, R.; Heeger, K.; Knop, D.; Luo, J.
Rok
2022
Publikováno
21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022. County of Richland: IFAAMAS, 2022. p. 127-135. ISSN 1548-8403. ISBN 978-1-4503-9213-6.
Typ
Stať ve sborníku
Pracoviště
Anotace
Fairly dividing a set of indivisible resources to a set of agents is
of utmost importance in some applications. However, after an allocation has been implemented the preferences of agents might
change and envy might arise. We study the following problem
to cope with such situations: Given an allocation of indivisible
resources to agents with additive utility-based preferences, is it
possible to socially donate some of the resources (which means
removing these resources from the allocation instance) such that
the resulting modified allocation is envy-free (up to one good). We
require that the number of deleted resources and/or the caused
utilitarian welfare loss of the allocation are bounded. We conduct a thorough study of the (parameterized) computational complexity
of this problem considering various natural and problem-specific
parameters (e.g., the number of agents, the number of deleted resources, or the maximum number of resources assigned to an agent
in the initial allocation) and different preference models, including
unary and 0/1-valuations. In our studies, we obtain a rich set of
(parameterized) tractability and intractability results and discover
several surprising contrasts, for instance, between the two closely
related fairness concepts envy-freeness and envy-freeness up to
one good and between the influence of the parameters maximum
number and welfare of the deleted resources.
Length-bounded cuts: Proper interval graphs and structural parameters
Autoři
Bentert, M.; Heeger, K.; Knop, D.
Rok
2022
Publikováno
Journal of Computer and System Sciences. 2022, 126 21-43. ISSN 0022-0000.
Typ
Článek
Pracoviště
Anotace
We study the LENGTH-BOUNDED CUT problem for special graph classes and from a parameterized complexity viewpoint. Here, we are given a graph G, two vertices s and t, and positive integers β and λ. The task is to find a set F of at most β edges such that each s-t-path of length at most λ in G contains some edge in F. Bazgan et al. [20] conjectured that LENGTH-BOUNDED CUT admits a polynomial-time algorithm if the input graph is a proper interval graph. We confirm this conjecture by providing a dynamic-programming-based polynomial-time algorithm. Moreover, we strengthen the W[1]-hardness result of Dvořák and Knop for LENGTH-BOUNDED CUT parameterized by pathwidth by showing W[1]-hardness for the combined parameter pathwidth and maximum degree of the input graph. Finally, we prove that LENGTH-BOUNDED CUT is W[1]-hard for the feedback vertex number. Both our hardness results complement known XP algorithms.
Integer programming in parameterized complexity: Five miniatures
Autoři
Gavenčiak, T.; Koutecký, M.; Knop, D.
Rok
2022
Publikováno
Discrete Optimization. 2022, 44 ISSN 1572-5286.
Typ
Článek
Pracoviště
Anotace
Powerful results from the theory of integer programming have recently led to substantial advances in parameterized complexity. However, our perception is that, except for Lenstra's algorithm for solving integer linear programming in fixed dimension, there is still little understanding in the parameterized complexity community of the strengths and limitations of the available tools. This is understandable: it is often difficult to infer exact runtimes or even the distinction between FPT and XP algorithms, and some knowledge is simply unwritten folklore in a different community. We wish to make a step in remedying this situation. To that end, we first provide an easy to navigate quick reference guide of integer programming algorithms from the perspective of parameterized complexity. Then, we show their applications in three case studies, obtaining FPT algorithms with runtime f(k)poly(n). We focus on: • Modeling: since the algorithmic results follow by applying existing algorithms to new models, we shift the focus from the complexity result to the modeling result, highlighting common patterns and tricks which are used. • Optimality program: after giving an FPT algorithm, we are interested in reducing the dependence on the parameter; we show which algorithms and tricks are often useful for speed-ups. • Minding the poly(n): reducing f(k) often has the unintended consequence of increasing poly(n); so we highlight the common trade-offs and show how to get the best of both worlds. Specifically, we consider graphs of bounded neighborhood diversity which are in a sense the simplest of dense graphs, and we show several FPT algorithms for CAPACITATED DOMINATING SET, SUM COLORING, MAX-q-CUT, and certain other coloring problems by modeling them as convex programs in fixed dimension, n-fold integer programs, bounded dual treewidth programs, indefinite quadratic programs in fixed dimension, parametric integer programs in fixed dimension, and 2-stage stochastic integer programs.
TARGET SET SELECTION IN DENSE GRAPH CLASSES
Autoři
Dvorak, P.; Knop, D.; Toufar, T.
Rok
2022
Publikováno
SIAM Journal on Discrete Mathematics. 2022, 36(1), 536-572. ISSN 0895-4801.
Typ
Článek
Pracoviště
Anotace
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 set of vertices (called a target set) that activates the whole graph during the following iterative process. A vertex outside the active set becomes active if the number of so far activated vertices in its neighborhood is at least its threshold. We give two parameterized algorithms for a special case where each vertex has the threshold set to half of its neighbors (the so-called MAJORITY TARGET SET SELECTION problem) for parameterizations by the neighborhood diversity and the twin cover number of the input graph. We complement these results from the negative side. We give a hardness proof for the MAJORITY TARGET SET SELECTION problem when parameterized by (a restriction of) the modular-width -a natural generalization of both previous structural parameters. We also show the TARGET SET SELECTION problem parameterized by the neighborhood diversity or by the twin cover number is W[1]-hard when there is no restriction on the thresholds.
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.
Hedonic Diversity Games: A Complexity Picture with More than Two Colors
Autoři
Rok
2022
Publikováno
Proceedings of the 36th AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2022. p. 5034-5042. ISSN 2159-5399. ISBN 978-1-57735-876-3.
Typ
Stať ve sborníku
Pracoviště
Anotace
Hedonic diversity games are a variant of the classical Hedonic games designed to better model a variety of questions concerning diversity and fairness. Previous works mainly targeted the case with two diversity classes (represented as colors in the model) and provided a set of initial complexity-theoretic and existential results concerning Nash and Individually stable outcomes. Here, we design new algorithms accompanied with lower bounds which provide a full parameterized-complexity picture for computing Nash and Individually stable outcomes with respect to the most natural parameterizations of the problem. Crucially, our results hold for general Hedonic diversity games where the number of colors is not necessarily restricted to two, and show that---apart from two trivial cases---a necessary condition for tractability in this setting is that the number of colors is bounded by the parameter. Moreover, for the special case of two colors we resolve an open question asked in previous work~(Boehmer and Elkind, AAAI 2020).
Waypoint routing on bounded treewidth graphs
Autoři
Rok
2022
Publikováno
Information Processing Letters. 2022, 173 106165:1-106165:9. ISSN 0020-0190.
Typ
Článek
Pracoviště
Anotace
In the Waypoint Routing Problem one is given an undirected capacitated and weighted graph G, a source-destination pair s, t∈V(G) and a set W⊆V(G), of waypoints. The task is to find a walk which starts at the source vertex s, visits, in any order, all waypoints, ends at the destination vertex t, respects edge capacities, that is, traverses each edge at most as many times as is its capacity, and minimizes the cost computed as the sum of costs of traversed edges with multiplicities. We study the problem for graphs of bounded treewidth and present a new algorithm for the problem working in 2^{O(tw)}·n time, significantly improving upon the previously known algorithms. We also show that this running time is optimal for the problem under Exponential Time Hypothesis
Controlling the Spread of Two Secrets in Diverse Social Networks (Student Abstract)
Autoři
Blažej, V.; Knop, D.; Schierreich, Š.
Rok
2022
Publikováno
Proceedings of the 36th AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2022. p. 12919-12920. ISSN 2159-5399. ISBN 978-1-57735-876-3.
Typ
Stať ve sborníku
Pracoviště
Anotace
nformation diffusion in social networks is a well-studied concept in social choice theory. We propose the study of the diffusion of two secrets in a heterogeneous environment from the complexity perspective, that is, there are two different networks with the same set of agents (e.g., the structure of the set of followers might be different in two distinct social networks). Formally, our model combines two group identification processes for which we do have independent desiderata---either constructive, where we would like a given group of agents to be exposed to a secret, or destructive, where a given group of agents should not be exposed to a secret. To be able to reach these targets, we can either delete an agent or introduce a previously latent agent. Our results are mostly negative---all of the problems are NP-hard. Therefore, we propose a parameterized study with respect to the natural parameters, the number of influenced agents, the size of the required/protected agent sets, and the duration of the diffusion process. Most of the studied problems remain W[1]-hard even for a combination of these parameters. We complement these results with nearly optimal XP algorithms.
Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
Autoři
Dvorak, P.; Feldmann, Andreas E.; Knop, D.; Masarik, T.; Toufar, T.; Veselý, P.
Rok
2021
Publikováno
SIAM Journal on Discrete Mathematics. 2021, 35(1), 546-574. ISSN 0895-4801.
Typ
Článek
Pracoviště
Anotace
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 extensively studied from the viewpoint of approximation and also parameterization. In particular, on one hand Steiner Tree is known to be APX-hard, and W[2]-hard on the other, if parameterized by the number of nonterminals (Steiner vertices) in the optimum solution. In contrast to this, we give an efficient parameterized approximation scheme (EPAS), which circumvents both hardness results. Moreover, our methods imply the existence of a polynomial size approximate kernelization scheme (PSAKS) for the considered parameter. We further study the parameterized approximability of other variants of Steiner Tree, such as Directed Steiner Tree and Steiner Forest. For none of these is an EPAS likely to exist for the studied parameter. For Steiner Forest an easy observation shows that the problem is APX-hard, even if the input graph contains no Steiner vertices. For Directed Steiner Tree we prove that approximating within any function of the studied parameter is W[1]-hard. Nevertheless, we show that an EPAS exists for Unweighted Directed Steiner Tree, but a PSAKS does not. We also prove that there is an EPAS and a PSAKS for Steiner Forest if in addition to the number of Steiner vertices, the number of connected components of an optimal solution is considered to be a parameter.
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.
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.
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.
Bears with Hats and Independence Polynomials
Autoři
Blažej, V.; Dvořák, P.; Opler, M.
Rok
2021
Publikováno
Graph-Theoretic Concepts in Computer Science. Cham: Springer, 2021. p. 283-295. Lecture Notes in Computer Science. vol. 12911. ISSN 0302-9743. ISBN 978-3-030-86837-6.
Typ
Stať ve sborníku
Pracoviště
Anotace
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.
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.
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
2020
Publikováno
Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK, June 24-26, 2020, Revised Selected Papers. Berlin: Springer-Verlag, 2020. p. 106-118. Lecture Notes in Computer Science. vol. 12301. ISSN 0302-9743. ISBN 978-3-030-60439-4.
Typ
Stať ve sborníku
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.
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.
The Clever Shopper Problem
Autoři
Bulteau, L.; Hermelin, D.; Knop, D.; Labarre, A.; Vialette, S.
Rok
2020
Publikováno
Theory of Computing Systems. 2020, 64(1), 17-34. ISSN 1432-4350.
Typ
Článek
Pracoviště
Anotace
We investigate a variant of the so-called Internet Shopping problem introduced by Blazewicz et al. (Appl. Math. Comput. Sci. 20, 385–390, 2010), where a customer wants to buy a list of products at the lowest possible total cost from shops which offer discounts when purchases exceed a certain threshold. Although the problem is NP-hard, we provide exact algorithms for several cases, e.g. when each shop sells only two items, and an FPT algorithm for the number of items, or for the number of shops when all prices are equal. We complement each result with hardness proofs in order to draw a tight boundary between tractable and intractable cases. Finally, we give an approximation algorithm and hardness results for the problem of maximising the sum of discounts.
Recognizing Proper Tree-Graphs
Autoři
Chaplick, S.; Golovach, P.A.; Hartmann, T.A.; Knop, D.
Rok
2020
Publikováno
15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2020. p. 8:1-8:15. ISSN 1868-8969. ISBN 978-3-95977-172-6.
Typ
Stať ve sborníku
Pracoviště
Anotace
We investigate the parameterized complexity of the recognition problem for the proper H-graphs. The H-graphs are the intersection graphs of connected subgraphs of a subdivision of a multigraph H, and the properness means that the containment relationship between the representations of the vertices is forbidden. The class of H-graphs was introduced as a natural (parameterized) generalization of interval and circular-arc graphs by Biró, Hujter, and Tuza in 1992, and the proper H-graphs were introduced by Chaplick et al. in WADS 2019 as a generalization of proper interval and circular-arc graphs. For these graph classes, H may be seen as a structural parameter reflecting the distance of a graph to a (proper) interval graph, and as such gained attention as a structural parameter in the design of efficient algorithms. We show the following results. - For a tree T with t nodes, it can be decided in 2^{𝒪(t² log t)} ⋅ n³ time, whether an n-vertex graph G is a proper T-graph. For yes-instances, our algorithm outputs a proper T-representation. This proves that the recognition problem for proper H-graphs, where H required to be a tree, is fixed-parameter tractable when parameterized by the size of T. Previously only NP-completeness was known. - Contrasting to the first result, we prove that if H is not constrained to be a tree, then the recognition problem becomes much harder. Namely, we show that there is a multigraph H with 4 vertices and 5 edges such that it is NP-complete to decide whether G is a proper H-graph.
Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters
Autoři
Bentert, M.; Heeger, K.; Knop, D.
Rok
2020
Publikováno
31st International Symposium on Algorithms and Computation (ISAAC 2020). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2020. p. 36:1-36:14. ISSN 1868-8969. ISBN 978-3-95977-173-3.
Typ
Stať ve sborníku
Pracoviště
Anotace
In the presented paper, we study the Length-Bounded Cut problem for special graph classes as well as from a parameterized-complexity viewpoint. Here, we are given a graph G, two vertices s and t, and positive integers β and λ. The task is to find a set F of edges of size at most β such that every s-t-path of length at most λ in G contains some edge in F. Bazgan et al. [Networks, 2019] conjectured that Length-Bounded Cut admits a polynomial-time algorithm if the input graph G is a proper interval graph. We confirm this conjecture by providing a dynamic-programming based polynomial-time algorithm. Moreover, we strengthen the W[1]-hardness result of Dvořák and Knop [Algorithmica, 2018] for Length-Bounded Cut parameterized by pathwidth. Our reduction is shorter, and the target of the reduction has stronger structural properties. Consequently, we give W[1]-hardness for the combined parameter pathwidth and maximum degree of the input graph. Finally, we prove that Length-Bounded Cut is W[1]-hard for the feedback vertex number. Both our hardness results complement known XP algorithms.
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.
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.
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”.
Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View
Autoři
Hušek, R.; Knop, D.; Masařík, T.
Rok
2020
Publikováno
15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2020. p. 16:1-16:18. ISSN 1868-8969. ISBN 978-3-95977-172-6.
Typ
Stať ve sborníku
Pracoviště
Anotace
In the Steiner Tree problem, we are given an edge-weighted undirected graph G = (V,E) and a set of terminals R ⊆ V. The task is to find a connected subgraph of G containing R and minimizing the sum of weights of its edges. Steiner Tree is well known to be NP-complete and is undoubtedly one of the most studied problems in (applied) computer science. We observe that many approximation algorithms for Steiner Tree follow a similar scheme (meta-algorithm) and perform (exhaustively) a similar routine which we call star contraction. Here, by a star contraction, we mean finding a star-like subgraph in (the metric closure of) the input graph minimizing the ratio of its weight to the number of contained terminals minus one; and contract. It is not hard to see that the well-known MST-approximation seeks the best star to contract among those containing two terminals only. Zelikovsky’s approximation algorithm follows a similar workflow, finding the best star among those containing three terminals. We perform an empirical study of star contractions with the relaxed condition on the number of terminals in each star contraction motivated by a recent result of Dvořák et al. [Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices, STACS 2018]. Furthermore, we propose two improvements of Zelikovsky’s 11/6-approximation algorithm and we empirically confirm that the quality of the solution returned by any of these is better than the one returned by the former algorithm. However, such an improvement is exchanged for a slower running time (up to a multiplicative factor of the number of terminals).
Kernelization of graph hamiltonicity: Proper H-graphs
Autoři
Chaplick, S.; Fomin, F.V.; Golovach, P.A.; Knop, D.; Zeman, P.
Rok
2019
Publikováno
16th International Symposium on Algorithms and Data Structures (WADS 2019). Cham: Springer, 2019. p. 296-310. vol. 11646. ISSN 0302-9743. ISBN 978-3-030-24765-2.
Typ
Stať ve sborníku
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(formula presented), that is, we design an algorithm that for an n-vertex graph G and an integer k≥ 1, in time polynomial in n and (formula presented), outputs a graph G′ of size (formula presented) 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.Cycle Cover admits a compression of size (formula presented) into another problem, called Prize Collecting Cycle Cover, that is, we design an algorithm that, in time polynomial in n and (formula presented), outputs an equivalent instance of Prize Collecting Cycle Cover of size (formula presented). In all our algorithms we assume that a proper H-decomposition is given as a part of the input.
Complexity of the Steiner Network Problem with Respect to the Number of Terminals
Rok
2019
Publikováno
36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany. Wadern: Schloss Dagstuhl - Leibniz Center for Informatics, 2019. p. 25:1-25:17. LIPIcs. vol. 126. ISSN 1868-8969. ISBN 978-3-95977-100-9.
Typ
Stať ve sborníku
Pracoviště
Anotace
In the Directed Steiner Network problem we are given an arc-weighted digraph G, a set of terminals $T\subseteq V(G)$ with |T|=q, and an (unweighted) directed request graph R with V(R)=T.
Our task is to output a subgraph $H \subseteq G$ of the minimum cost such that there is a directed path from s to t in H for all st \in A(R).
It is known that the problem can be solved in time $|V(G)|^{O(|A(R)|)}$ [Feldman\&Ruhl, SIAM J. Comput. 2006] and cannot be solved in time $|V(G)|^{o(|A(R)|)}$ even if G is planar, unless the Exponential-Time Hypothesis (ETH) fails [Chitnis et al., SODA 2014]. However, the reduction (and other reductions showing hardness of the problem) only shows that the problem cannot be solved in time $|V(G)|^{o(q)}$, unless ETH fails. Therefore, there is a significant gap in the complexity with respect to q in the exponent.
We show that \textsc{Directed Steiner Network} is solvable in time $f(q)\cdot |V(G)|^{O(c_g \cdot q)}$, where $c_g$ is a constant depending solely on the genus of G and f is a computable function.
We complement this result by showing that there is no $f(q)\cdot |V(G)|^{o(q^2/ \log q)}$ algorithm for any function f for the problem on general graphs, unless ETH fails.
Integer Programming and Incidence Treedepth
Autoři
Eiben, E.; Ganian, R.; Knop, D.; Ordyniak, S.; Pilipczuk, Mi.; Wrochna, M.
Rok
2019
Publikováno
Integer Programming and Combinatorial Optimization. Basel: Springer, 2019. p. 194-204. ISSN 0302-9743. ISBN 978-3-030-17952-6.
Typ
Stať ve sborníku
Pracoviště
Anotace
Recently a strong connection has been shown between the tractability of integer programming (IP) with bounded coefficients on the one side and the structure of its constraint matrix on the other side. To that end, integer linear programming is fixed-parameter tractable with respect to the primal (or dual) treedepth of the Gaifman graph of its constraint matrix and the largest coefficient (in absolute value). Motivated by this, Koutecký, Levin, and Onn [ICALP 2018] asked whether it is possible to extend these result to a more broader class of integer linear programs. More formally, is integer linear programming fixed-parameter tractable with respect to the incidence treedepth of its constraint matrix and the largest coefficient (in absolute value)?
We answer this question in negative. We prove that deciding the feasibility of a system in the standard form, 𝐴𝐱=𝐛,𝐥≤𝐱≤𝐮, is NP-hard even when the absolute value of any coefficient in A is 1 and the incidence treedepth of A is 5. Consequently, it is not possible to decide feasibility in polynomial time even if both the assumed parameters are constant, unless 𝖯=𝖭𝖯.
Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
Autoři
Bredereck, R.; Heeger, K.; Knop, D.; Niedermeier, R.
Rok
2019
Publikováno
30th International Symposium on Algorithms and Computation (ISAAC 2019). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2019. p. 44:1-44:14. vol. 149. ISSN 1868-8969. ISBN 978-3-95977-130-6.
Typ
Stať ve sborníku
Pracoviště
Anotace
We continue and extend previous work on the parameterized complexity analysis of the NP-hard Stable Roommates with Ties and Incomplete Lists problem, thereby strengthening earlier results both on the side of parameterized hardness as well as on the side of fixed-parameter tractability. Other than for its famous sister problem Stable Marriage which focuses on a bipartite scenario, Stable Roommates with Incomplete Lists allows for arbitrary acceptability graphs whose edges specify the possible matchings of each two agents (agents are represented by graph vertices). Herein, incomplete lists and ties reflect the fact that in realistic application scenarios the agents cannot bring all other agents into a linear order. Among our main contributions is to show that it is W[1]-hard to compute a maximum-cardinality stable matching for acceptability graphs of bounded treedepth, bounded tree-cut width, and bounded feedback vertex number (these are each time the respective parameters). However, if we `only' ask for perfect stable matchings or the mere existence of a stable matching, then we obtain fixed-parameter tractability with respect to tree-cut width but not with respect to treedepth. On the positive side, we also provide fixed-parameter tractability results for the parameter feedback edge set number.
High-Multiplicity Fair Allocation: Lenstra Empowered by N-fold Integer Programming
Autoři
Bredereck, R.; Kaczmarczyk, A.; Knop, D.; Niedermeier, R.
Rok
2019
Publikováno
EC '19 Proceedings of the 2019 ACM Conference on Economics and Computation. New York: ACM, 2019. p. 505-523. ISBN 9781450367929.
Typ
Stať ve sborníku
Pracoviště
Anotace
We study the (parameterized) computational complexity of problems in the context of fair allocations of indivisible goods. More specifically, we show fixed-parameter tractability results for a broad set of problems concerned with envy-free, Pareto-efficient allocations of items (with agent-specific utility functions) to agents. In principle, this implies efficient exact algorithms for these in general computationally intractable problems whenever we face instances with few agents and low maximum (absolute) utility values. This holds true also in high-multiplicity settings where we may have high numbers of identical items. On the technical side, our approach provides algorithmic meta-theorems covering a rich set of fair allocation problems in the additive preferences model. To achieve this, our main technical contribution is to make an elaborate use of tools from integer linear programming. More specifically, we exploit results originally going back to a famous theorem of Lenstra [Math. Oper. Res. 1983] concerning (the fixed-parameter tractability of) Integer Linear Programs (ILPs) with bounded dimension (that is, the dimension shall be considered as a (small) parameter) and the more recent framework of (combinatorial) N-fold ILPs. We reveal and exploit a fruitful interaction between these two cornerstones in the theory of integer linear programming, which may be of independent interest in applications going beyond fair allocations.
Solving Integer Quadratic Programming via Explicit and Structural Restrictions
Autoři
Eiben, E.; Ganian, R.; Knop, D.; Ordyniak, S.
Rok
2019
Publikováno
Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence. Menlo Park, California: AAAI Press, 2019. p. 1477-1484. ISSN 2159-5399. ISBN 978-1-57735-809-1.
Typ
Stať ve sborníku
Pracoviště
Anotace
We study the parameterized complexity of Integer Quadratic Programming under two kinds of restrictions: explicit restrictions on the domain or coefficients, and structural restrictions on variable interactions. We argue that both kinds of restrictions are necessary to achieve tractability for Integer Quadratic Programming, and obtain four new algorithms for the problem that are tuned to possible explicit restrictions of instances that we may wish to solve. The presented algorithms are exact, deterministic, and complemented by appropriate lower bounds.
Evaluating and Tuning n-fold Integer Programming
Autoři
Altmanová, K.; Knop, D.; Koutecký, M.
Rok
2019
Publikováno
Journal of Experimental Algorithmics. 2019, 24(1), 2.2:1-2.2:22. ISSN 1084-6654.
Typ
Článek
DOI
Pracoviště
Anotace
In recent years, algorithmic breakthroughs in stringology, computational social choice, scheduling, and so on, were achieved by applying the theory of so-called n-fold integer programming. An n-fold integer program (IP) has a highly uniform block structured constraint matrix. Hemmecke, Onn, and Romanchuk [Math. Program., 2013] showed an algorithm with runtime ΔO(rst + r2s) n3, where Δ is the largest coefficient, r,s, and t are dimensions of blocks of the constraint matrix and n is the total dimension of the IP; thus, an algorithm efficient if the blocks are of small size and with small coefficients. The algorithm works by iteratively improving a feasible solution with augmenting steps, and n-fold IPs have the special property that augmenting steps are guaranteed to exist in a not-too-large neighborhood. However, this algorithm has never been implemented and evaluated.
We have implemented the algorithm and learned the following along the way. The original algorithm is practically unusable, but we discover a series of improvements that make its evaluation possible. Crucially, we observe that a certain constant in the algorithm can be treated as a tuning parameter, which yields an efficient heuristic (essentially searching in a smaller-than-guaranteed neighborhood). Furthermore, the algorithm uses an overly expensive strategy to find a “best” step, while finding only an “approximately best” step is much cheaper, yet sufficient for quick convergence. Using this insight, we improve the asymptotic dependence on n from n3 to n2 log n.
On Induced Online Ramsey Number of Paths, Cycles, and Trees
Autoři
Blažej, V.; Dvořák, P.; Valla, T.
Rok
2019
Publikováno
The 14th International Computer Science Symposium in Russia. Springer, Cham, 2019. p. 60-69. Lecture Notes in Computer Science. vol. 11532. ISSN 0302-9743. ISBN 978-3-030-19954-8.
Typ
Stať ve sborníku
Pracoviště
Anotace
An online Ramsey game is a game between Builder and
Painter, alternating in turns.
They are given a fixed graph $H$ and a an infinite set of independent vertices $G$.
In each round Builder draws a new edge in $G$ and Painter colors it either red or blue.
Builder wins if after some finite round there is a monochromatic
copy of the graph $H$, otherwise Painter wins.
The online Ramsey number $\widetilde{r}(H)$ is the minimum number of rounds such that Builder can
force a monochromatic copy of $H$ in $G$.
This is an analogy to the size-Ramsey number $\overline{r}(H)$
defined as the minimum number such that there exists graph $G$ with $\overline{r}(H)$ edges
where for any edge two-coloring $G$ contains a monochromatic copy of $H$.
In this extended abstract, we introduce the concept of induced online Ramsey numbers:
the induced online Ramsey number $\overline{r}_{ind}(H)$ is the minimum number of rounds Builder
can force an induced monochromatic copy of $H$ in $G$.
We prove asymptotically tight bounds on the induced online Ramsey numbers of paths,
cycles and two families of trees.
Moreover, we provide a result analogous to Conlon [On-line Ramsey Numbers, SIAM J. Discr. Math. 2009],
showing that there is an infinite family of trees $T_1,T_2,\dots$, $|T_i|<|T_{i+1}|$ for $i\ge1$, such that
\[
\lim_{i\to\infty} \frac{\widetilde{r}(T_i)}{\overline{r}(T_i)} = 0.
\]
Efficient Implementation of Color Coding Algorithm for Subgraph Isomorphism Problem
Typ
Stať ve sborníku
Pracoviště
Anotace
We consider the subgraph isomorphism problem where, given two graphs G (source graph) and F (pattern graph), one is to decide whether there is a (not necessarily induced) subgraph of G isomorphic to F. While many practical heuristic algorithms have been developed for the problem, as pointed out by McCreesh et al. [JAIR 2018], for each of them there are rather small instances which they cannot cope. Therefore, developing an alternative approach that could possibly cope with these hard instances would be of interest. A seminal paper by Alon, Yuster and Zwick [J. ACM 1995] introduced the color coding approach to solve the problem, where the main part is a dynamic programming over color subsets and partial mappings. As with many exponential-time dynamic programming algorithms, the memory requirements constitute the main limiting factor for its usage. Because these requirements grow exponentially with the treewidth of the pattern graph, all existing implementations based on the color coding principle restrict themselves to specific pattern graphs, e.g., paths or trees. In contrast, we provide an efficient implementation of the algorithm significantly reducing its memory requirements so that it can be used for pattern graphs of larger treewidth. Moreover, our implementation not only decides the existence of an isomorphic subgraph, but it also enumerates all such subgraphs (or given number of them). We provide an extensive experimental comparison of our implementation to other available solvers for the problem.
Faster FPT algorithm for 5-path vertex cover
Autoři
Červený, R.; Suchý, O.
Rok
2019
Publikováno
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Wadern: Schloss Dagstuhl - Leibniz Center for Informatics, 2019. p. 32:1-32:13. Leibniz International Proceedings in Informatics (LIPIcs). vol. 138. ISSN 1868-8969. ISBN 978-3-95977-117-7.
Typ
Stať ve sborníku
Pracoviště
Anotace
The problem of \textsc{$d$-Path Vertex Cover, $d$-PVC} lies in determining a subset~$F$ of vertices of a~given graph $G=(V,E)$ such that $G \setminus F$ does not contain a~path on $d$ vertices. The paths we aim to cover need not to be induced. It is known that the \textsc{$d$-PVC} problem is NP-complete for any $d \ge 2$. When parameterized by the size of the solution $k$, \textsc{5-PVC} has direct trivial algorithm with $\mathcal{O}(5^kn^{\mathcal{O}(1)})$ running time and, since \textsc{$d$-PVC} is a special case of \textsc{$d$-Hitting Set}, an algorithm running in $\mathcal{O}(4.0755^kn^{\mathcal{O}(1)})$ time is known. In this paper we present an iterative compression algorithm that solves the \textsc{5-PVC} problem in $\mathcal{O}(4^kn^{\mathcal{O}(1)})$ time.
A Tight Lower Bound for Planar Steiner Orientation
Autoři
Chitnis, R.; Feldmann, A.; Suchý, O.
Rok
2019
Publikováno
Algorithmica. 2019, 81(8), 3200-3216. ISSN 0178-4617.
Typ
Článek
Pracoviště
Anotace
In the Steiner Orientation problem, the input is a mixed graph G (it has both directed and undirected edges) and a set of k terminal pairs T. The question is whether we can orient the undirected edges in a way such that there is a directed s?t path for each terminal pair (s,t)T. Arkin and Hassin [DAM'02] showed that the Steiner Orientation problem is NP-complete. They also gave a polynomial time algorithm for the special case when k=2. From the viewpoint of exact algorithms, Cygan et al.[ESA'12, SIDMA'13] designed an XP algorithm running in nO(k) time for all k1. Pilipczuk and Wahlstrom [SODA'16, TOCT'18] showed that the Steiner Orientation problem is W[1]-hard parameterized by k. As a byproduct of their reduction, they were able to show that under the Exponential Time Hypothesis (ETH) of Impagliazzo, Paturi and Zane [JCSS'01] the Steiner Orientation problem does not admit an f(k)no (k/logk) algorithm for any computable functionf. In this paper, we give a short and easy proof that the nO(k) algorithm of Cygan etal. is asymptotically optimal, even if the input graph is planar. Formally, we show that the Planar Steiner Orientation problem is W[1]-hard parameterized by the number k of terminal pairs, and, under ETH, cannot be solved in f(k)no (k) time for any computable function f. Moreover, under a stronger hypothesis called Gap-ETH of Dinur [ECCC'16] and Manurangsi and Raghavendra [ICALP'17], we are able to show that there is no constant ?>0 such that Planar Steiner Orientation admits an -approximation in FPT time, i.e., no f(k)no (k) time algorithm can distinguish between the case when all k pairs are satisfiable versus the case when less than k pairs are satisfiable. To the best of our knowledge, this is the first FPT inapproximability result on planar graphs.
On the m-eternal Domination Number of Cactus Graphs
Autoři
Blažej, V.; Křišťan, J.; Valla, T.
Rok
2019
Publikováno
Reachability Problems. Springer, Cham, 2019. p. 33-47. ISSN 0302-9743. ISBN 978-3-030-30805-6.
Typ
Stať ve sborníku
Pracoviště
Anotace
Given a graph $G$, guards are placed on vertices of $G$.
Then vertices are subject to an infinite sequence of attacks
so that each attack must be defended by a guard moving from a neighboring vertex.
The m-eternal domination number is the minimum number of guards such that
the graph can be defended indefinitely.
In this paper we study the m-eternal domination number of cactus graphs,
that is, connected graphs where each edge lies in at most two cycles,
and we consider three variants of the m-eternal domination number:
first variant allows multiple guards to occupy a single vertex,
second variant does not allow it, and in the third variant additional ``eviction'' attacks must be defended.
We provide a new upper bound for the m-eternal domination number of cactus graphs,
and for a subclass of cactus graphs called
Christmas cactus graphs, where each vertex lies in at most two cycles,
we prove that these three numbers are equal.
Moreover, we present a linear-time algorithm for computing them.