Two-Stage Refugee Resettlement Models: Computational Aspects of the Second Stage
Authors
Year
2024
Published
Proceedings of the 7th AAAI/ACM Conference on AI, Ethics, and Society. Menlo Park: AAAI Press, 2024. p. 50-51. ISBN 978-1-57735-892-3.
Type
Proceedings paper
Departments
Annotation
I discuss recent progresses in the analysis of computational aspects of two-stage refugee resettlement methods. I pay special attention to the second stage of these models, as it is arguably understudied compared to the first stage. I also discuss some future challenges in this area that need to be resolved before the models can be deployed and used in practice.
Parameterised Distance to Local Irregularity
Authors
Fioravantes, F.; Melissinos, N.; Triommatis, T.
Year
2024
Published
19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2024. p. 18:1-18:15. ISBN 978-3-95977-353-9.
Type
Proceedings paper
Departments
Annotation
A graph G is locally irregular if no two of its adjacent vertices have the same degree. The authors of [Fioravantes et al. Complexity of finding maximum locally irregular induced subgraph. SWAT, 2022] introduced and provided some initial algorithmic results on the problem of finding a locally irregular induced subgraph of a given graph G of maximum order, or, equivalently, computing a subset S of V(G) of minimum order, whose deletion from G results in a locally irregular graph; S is called an optimal vertex-irregulator of G. In this work we provide an in-depth analysis of the parameterised complexity of computing an optimal vertex-irregulator of a given graph G. Moreover, we introduce and study a variation of this problem, where S is a subset of the edges of G; in this case, S is denoted as an optimal edge-irregulator of G. We prove that computing an optimal vertex-irregulator of a graph G is in FPT when parameterised by various structural parameters of G, while it is W[1]-hard when parameterised by the feedback vertex set number or the treedepth of G. Moreover, computing an optimal edge-irregulator of a graph G is in FPT when parameterised by the vertex integrity of G, while it is NP-hard even if G is a planar bipartite graph of maximum degree 6, and W[1]-hard when parameterised by the size of the solution, the feedback vertex set or the treedepth of G. Our results paint a comprehensive picture of the tractability of both problems studied here.
Taxonomic classification with maximal exact matches in KATKA kernels and minimizer digests
Authors
Bohuslavová, D.; Ahmed, O.; Gagie, T.; Holub, J.; Langmead, B.; Manzini, G.; Navarro, G.
Year
2024
Published
Symposium on Experimental Algorithms. Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2024. p. 10:1-10:13. vol. 301. ISSN 1868-8969.
Type
Proceedings paper
Departments
Annotation
For taxonomic classification, we are asked to index the genomes in a phylogenetic tree such that later, given a DNA read, we can quickly choose a small subtree likely to contain the genome from which that read was drawn. Although popular classifiers such as Kraken use k-mers, recent research indicates that using maximal exact matches (MEMs) can lead to better classifications. For example, we can build an augmented FM-index over the the genomes in the tree concatenated in left-to-right order; for each MEM in a read, find the interval in the suffix array containing the starting positions of that MEM’s occurrences in those genomes; find the minimum and maximum values stored in that interval; take the lowest common ancestor (LCA) of the genomes containing the characters at those positions.
This solution is practical, however, only when the total size of the genomes in the tree is fairly small. In this paper we consider applying the same solution to three lossily compressed representations of the genomes’ concatenation: a KATKA kernel, which discards characters that are not in the first or last occurrence of any kmax-tuple, for a parameter kmax; a minimizer digest; a KATKA kernel of a minimizer digest.
With a test dataset and these three representations of it, simulated reads and various parameter settings, we checked how many reads’ longest MEMs occurred only in the sequences from which those reads were generated (“true positive” reads). For some parameter settings we achieved significant compression while only slightly decreasing the true-positive rate.
Decreasing verification radius in local certification
Authors
Feuilloley, L.; Janoušek, J.; Křišťan, J.; Sedláček, J.E.
Year
2024
Published
Algorithmics of Wireless Networks. Springer, Cham, 2024. p. 188-201. Lecture Notes in Computer Science. vol. 15026. ISSN 0302-9743. ISBN 978-3-031-74579-9.
Type
Proceedings paper
Departments
Annotation
This paper deals with local certification, specifically locally checkable proofs: given a graph property, the task is to certify whether a graph satisfies the property. The verification of this certification needs to be done locally without the knowledge of the whole graph.
More precisely, a distributed algorithm, called a verifier, is executed on each vertex. The verifier observes the local neighborhood up to a constant distance and either accepts or rejects.
We examine the trade-off between the visibility radius and the size of certificates. We describe a procedure that decreases the radius by encoding the neighbourhood of each vertex into its certificate.
We also provide a corresponding lower bound on the required certificate size increase, showing that such an approach is close to optimal.
Brief Announcement: Decreasing Verification Radius in Local Certification
Authors
Křišťan, J.; Sedláček, J.E.
Year
2024
Published
38th International Symposium on Distributed Computing (DISC 2024). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2024. p. 49:1-49:6. Leibniz International Proceedings in Informatics (LIPIcs). vol. 319. ISSN 1868-8969. ISBN 978-3-95977-352-2.
Type
Proceedings paper
Departments
Annotation
This paper deals with local certification, specifically locally checkable proofs: given a graph property, the task is to certify whether a graph satisfies the property. The verification of this certification needs to be done locally without the knowledge of the whole graph.
We examine the trade-off between the visibility radius and the size of certificates. We describe a procedure that decreases the radius by encoding the neighbourhood of each vertex into its certificate.
We also provide a corresponding lower bound on the required certificate size increase, showing that such an approach is close to optimal.
On the Complexity of Target Set Selection in Simple Geometric Networks
Authors
Year
2024
Published
Discrete Mathematics and Theoretical Computer Science. 2024, 26(2), 1-26. ISSN 1365-8050.
Type
Article
Departments
Annotation
We study the following model of disease spread in a social network. At first, all individuals are either infected or healthy. Next, in discrete rounds, the disease spreads in the network from infected to healthy individuals such that a healthy individual gets infected if and only if a sufficient number of its direct neighbors are already infected.
We represent the social network as a graph. Inspired by the real-world restrictions in the recent epidemic, especially by social and physical distancing requirements, we restrict ourselves to networks that can be represented as geometric intersection graphs. We show that finding a minimal vertex set of initially infected individuals to spread the disease in the whole network is computationally hard, already on unit disk graphs. Hence, to provide some algorithmic results, we focus ourselves on simpler geometric graph classes, such as interval graphs and grid graphs.
An Optimal Algorithm for Sorting Pattern-Avoiding Sequences
Authors
Year
2024
Published
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). USA: IEEE Computer Society, 2024. p. 689-699. ISSN 0272-5428. ISBN 979-8-3315-1675-8.
Type
Proceedings paper
Departments
Annotation
We present a deterministic comparison-based algorithm that sorts sequences avoiding a fixed permutation $\pi$ in linear time, even if $\pi$ is a priori unkown. Moreover, the dependence of the multiplicative constant on the pattern $\pi$ matches the information-theoretic lower bound. A crucial ingredient is an algorithm for performing efficient multi-way merge based on the Marcus-Tardos theorem. As a direct corollary, we obtain a linear-time algorithm for sorting permutations of bounded twin-width.
Romeo and Juliet Is EXPTIME-Complete
Authors
Gahlawat, H.; Křišťan, J.; Valla, T.
Year
2024
Published
Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2024. p. 54:1-54:16. Leibniz International Proceedings in Informatics (LIPIcs). vol. 306. ISBN 978-3-95977-335-5.
Type
Proceedings paper
Departments
Annotation
Romeo and Juliet is a two player Rendezvous game played on graphs where one player controls two agents, Romeo (ℛ) and Juliet (𝒥) who aim to meet at a vertex against k adversaries, called dividers, controlled by the other player. The optimization in this game lies at deciding the minimum number of dividers sufficient to restrict ℛ and 𝒥 from meeting in a graph, called the dynamic separation number. We establish that Romeo and Juliet is EXPTIME-complete, settling a conjecture of Fomin, Golovach, and Thilikos [Inf. and Comp., 2023] positively. We also consider the game for directed graphs and establish that although the game is EXPTIME-complete for general directed graphs, it is PSPACE-complete and co-W[2]-hard for directed acyclic graphs.
Equitable Connected Partition and Structural Parameters Revisited: N-fold Beats Lenstra
Authors
Year
2024
Published
Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2024. p. 29:1-29:16. Leibniz International Proceedings in Informatics (LIPIcs). vol. 306. ISBN 978-3-95977-335-5.
Type
Proceedings paper
Departments
Annotation
In the Equitable Connected Partition (ECP for short) problem, we are given a graph $G=(V,E)$ together with an integer $p\in\mathbb{N}$, and our goal is to find a partition of~$V$ into~$p$~parts such that each part induces a connected sub-graph of $G$ and the size of each two parts differs by at most~$1$. On the one hand, the problem is known to be NP-hard in general and W[1]-hard with respect to the path-width, the feedback-vertex set, and the number of parts~$p$ combined. On the other hand, fixed-parameter algorithms are known for parameters the vertex-integrity and the max leaf number.
In this work, we systematically study ECP with respect to various structural restrictions of the underlying graph and provide a clear dichotomy of its parameterised complexity. Specifically, we show that the problem is in FPT when parameterized by the modular-width and the distance to clique. Next, we prove W[1]-hardness with respect to the distance to cluster, the $4$-path vertex cover number, the distance to disjoint paths, and the feedback-edge set, and NP-hardness for constant shrub-depth graphs. Our hardness results are complemented by matching algorithmic upper-bounds: we give an XP algorithm for parameterisation by the tree-width and the distance to cluster. We also give an improved FPT algorithm for parameterisation by the vertex integrity and the first explicit FPT algorithm for the $3$-path vertex cover number. The main ingredient of these algorithms is a formulation of ECP as $N$-fold IP, which clearly indicates that such formulations may, in certain scenarios, significantly outperform existing algorithms based on the famous algorithm of Lenstra.
Multivariate Analysis and Structural Restrictions in Computational Social Choice
Authors
Year
2024
Published
Proceedings of the 33rd International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2024. p. 8502-8503. ISBN 978-1-956792-04-1.
Type
Proceedings paper
Departments
Annotation
In my research, I focus on computationally hard problems in the area of computational social choice. I am interested in the study of input restrictions that guarantee the existence of efficient and scalable algorithms that are of practical interest.
Individual Rationality in Topological Distance Games is Surprisingly Hard
Authors
Deligkas, A.; Eiben, E.; Knop, D.; Schierreich, Š.
Year
2024
Published
Proceedings of the 33rd International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2024. p. 2782-2790. ISBN 978-1-956792-04-1.
Type
Proceedings paper
Departments
Annotation
In the recently introduced topological distance games, strategic agents need to be assigned to a subset of vertices of a topology. In the assignment, the utility of an agent depends on both the agent's inherent utilities for other agents and its distance from them on the topology. We study the computational complexity of finding individually-rational outcomes; this notion is widely assumed to be the very minimal stability requirement and requires that the utility of every agent in a solution is non-negative.
We perform a comprehensive study of the problem's complexity, and we prove that even in very basic cases, deciding whether an individually-rational solution exists is intractable. To reach at least some tractability, one needs to combine multiple restrictions of the input instance, including the number of agents and the topology and the influence of distant agents on the utility.
Aggregation of Continuous Preferences in One Dimension
Authors
Del Pia, A.; Knop, D.; Lassota, A.; Sornat, K.; Talmon, N.
Year
2024
Published
Proceedings of the 33rd International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2024. p. 2748-2756. ISBN 978-1-956792-04-1.
Type
Proceedings paper
Departments
Annotation
We develop a general, formal model of social choice in which voters have continuous preferences over a one-dimensional space. Our model is parameterized by different restrictions that we introduce regarding the way voter preferences change in time
as well as the optimization criteria (that correspond to a normative continuum of fairness definitions) desired from an aggregation method—that outputs a continuous, one-dimensional curve—given such inputs. We discuss the applicability of the model
to different real-world situations and, as a first step towards an analysis of the different model realizations, we concentrate on identifying those cases that are computationally feasible to compute.
Evaluation of Project Performance in Participatory Budgeting
Authors
Boehmer, N.; Faliszewski, P.; Janeczko, Ł.; Peters, D.; Pierczyński, G.; Schierreich, Š.; Skowron, P.; Szufa, S.
Year
2024
Published
Proceedings of the 33rd International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2024. p. 2678-2686. ISBN 978-1-956792-04-1.
Type
Proceedings paper
Departments
Annotation
We study ways of evaluating the performance of losing projects in participatory budgeting (PB) elections by seeking actions that would have led to their victory. We focus on lowering the projects' costs, obtaining additional approvals for them, and asking supporters to refrain from approving other projects: The larger a change is needed, the less successful is the given project. We seek efficient algorithms for computing our measures and we analyze and compare them experimentally. We focus on the GreedyAV, Phragmen, and Equal-Shares PB rules.
Average-case complexity of a branch-and-bound algorithm for MIN DOMINATING SET
Authors
Denat, T.; Harutyunyan, A.; Melissinos, N.; Paschos, V. T..
Year
2024
Published
Discrete Applied Mathematics. 2024, 345 4-8. ISSN 0166-218X.
Type
Article
Departments
Annotation
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.
Generalized Coloring of Permutations
Authors
Jelínek, V.; Opler, M.; Valtr, P.
Year
2024
Published
Algorithmica. 2024, 86(7), 2174-2210. ISSN 0178-4617.
Type
Article
Departments
Annotation
A permutation π is a merge of a permutation σ and a permutation τ, if we can color the elements of π red and blue so that the red elements have the same relative order as σ and the blue ones as τ. We consider, for fixed hereditary permutation classes C and D, the complexity of determining whether a given permutation π is a merge of an element of C with an element of D. We develop general algorithmic approaches for identifying polynomially tractable cases of merge recognition. Our tools include a version of streaming recognizability of permutations via polynomially constructible nondeterministic automata, as well as a concept of bounded width decomposition, inspired by the work of Ahal and Rabinovich. As a consequence of the general results, we can provide nontrivial examples of tractable permutation merges involving commonly studied permutation classes, such as the class of layered permutations, the class of separable permutations, or the class of permutations avoiding a decreasing sequence of a given length. On the negative side, we obtain a general hardness result which implies, for example, that it is NP-complete to recognize the permutations that can be merged from two subpermutations avoiding the pattern 2413.
On kernels for d-path vertex cover
Authors
Červený, R.; Choudhary, P.; Suchý, O.
Year
2024
Published
Journal of Computer and System Sciences. 2024, 144 ISSN 0022-0000.
Type
Article
Departments
Annotation
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(4)d(2d+9)) vertices and edges for general d. (c) 2024 Elsevier Inc. All rights reserved.
Cluster Editing for Multi-Layer and Temporal Graphs
Authors
Chen, J.; Molter, H.; Sorge, M.; Suchý, O.
Year
2024
Published
Theory of Computing Systems. 2024, 68(5), 1239-1290. ISSN 1432-4350.
Type
Article
Departments
Annotation
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.
Forward linearised tree pattern matching using tree pattern border array
Authors
Year
2024
Published
Discrete Applied Mathematics. 2024, 352 33-43. ISSN 1872-6771.
Type
Article
Annotation
We define a tree pattern border array as a property of linearised trees analogous to border arrays from the string domain. We consider tree patterns with node wildcards and subtree wildcards. Then we use the tree pattern border array in a new forward tree pattern matching algorithm for ordered ranked trees. The algorithm finds all occurrences of a single linearised tree pattern in a linearised input tree. As with the classical Morris–Pratt algorithm for searching in strings, the tree pattern border array is used to determine shift lengths in the searching phase of the tree pattern matching algorithm. We compare this new algorithm with the best performing previously existing algorithms based on backward linearised tree pattern matching algorithms, (non-)linearised tree pattern matching algorithms using finite tree automata or stringpath matchers. We show that our new algorithm outperforms other tree pattern matching algorithms in single tree pattern matching.
Shortest Characteristic Factors of a Deterministic Finite Automaton and Computing Its Positive Position Run by Pattern Set Matching
Authors
Janoušek, J.; Plachý, Š.
Year
2024
Published
SOFSEM 2024: Theory and Practice of Computer Science. Springer, Cham, 2024. p. 326-339. Lecture Notes in Computer Science. vol. 14519. ISSN 0302-9743. ISBN 978-3-031-52112-6.
Type
Proceedings paper
Departments
Annotation
Given a deterministic finite automaton (DFA) A, we present a simple algorithm for constructing four deterministic finite automata that accept the shortest forbidden factors, the shortest forbidden suffixes, the shortest allowed suffixes, and the shortest forbidden prefixes. We refer to these automata as the shortest characteristic factors of automaton A. If the given automaton is local, and therefore the language it accepts is strictly locally testable, the sets of its shortest characteristic factors are finite, and these four automata are acyclic. This approach simplifies existing methods for the extraction of forbidden factors and also generalizes it for all classes of input DFAs. Furthermore, we demonstrate that this type of extraction can be used for a sublinear run of an automaton for certain inputs. We define a positive position run of a deterministic finite automaton, representing all positions in an input string where the automaton reaches a final state. Finally, we present an algorithm for computing the positive position run of the automaton, which utilizes pattern set matching of its shortest forbidden factors and its shortest allowed suffixes, provided that the sets are finite. We showcase the computation of the positive position run of a local automaton using backward pattern matching, which can achieve sublinear time.
Optimization with Pattern-Avoiding Input
Authors
Berendsohn, B.A.; Kozma, L.; Opler, M.
Year
2024
Published
STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. New York: Association for Computing Machinery, 2024. p. 671-682. ISSN 0737-8017. ISBN 979-8-4007-0383-6.
Type
Proceedings paper
Departments
Annotation
Permutation pattern-avoidance is a central concept of both enumerative and extremal combinatorics. In this paper we study the effect of permutation pattern-avoidance on the complexity of optimization problems. In the context of the dynamic optimality conjecture (Sleator, Tarjan, STOC 1983), Chalermsook, Goswami, Kozma, Mehlhorn, and Saranurak (FOCS 2015) conjectured that the amortized search cost of an optimal binary search tree (BST) is constant whenever the search sequence is pattern-avoiding. The best known bound to date is 2α(n)(1+o(1)) recently obtained by Chalermsook, Pettie, and Yingchareonthawornchai (SODA 2024); here n is the BST size and α(·) the inverse-Ackermann function. In this paper we resolve the conjecture, showing a tight (1) bound. This indicates a barrier to dynamic optimality: any candidate online BST (e.g., splay trees or greedy trees) must match this optimum, but current analysis techniques only give superconstant bounds. More broadly, we argue that the easiness of pattern-avoiding input is a general phenomenon, not limited to BSTs or even to data structures. To illustrate this, we show that when the input avoids an arbitrary, fixed, a priori unknown pattern, one can efficiently compute: (1) a k-server solution of n requests from a unit interval, with total cost n(1/logk), in contrast to the worst-case Θ(n/k) bound, and (2) a traveling salesman tour of n points from a unit box, of length (logn), in contrast to the worst-case Θ(√n) bound; similar results hold for the euclidean minimum spanning tree, Steiner tree, and nearest-neighbor graphs. We show both results to be tight. Our techniques build on the Marcus-Tardos proof of the Stanley-Wilf conjecture, and on the recently emerging concept of twin-width.
The Parameterized Complexity of Maximum Betweenness Centrality
Authors
Schierreich, Š.; Smutný, J.G.
Year
2024
Published
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.
Type
Proceedings paper
Departments
Annotation
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.
Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology
Authors
Year
2024
Published
Proceedings of the 38th AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2024. p. 17380-17388. AAAI Conference on Artificial Intelligence. vol. 38. ISSN 2159-5399.
Type
Proceedings paper
Departments
Annotation
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 Complexity of Fair Division of Indivisible Items with Externalities
Authors
Deligkas, A.; Eiben, E.; Korchemna, V.; Schierreich, Š.
Year
2024
Published
Proceedings of the 38th AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2024. p. 9653-9661. AAAI Conference on Artificial Intelligence. vol. 38. ISSN 2159-5399.
Type
Proceedings paper
Departments
Annotation
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.
The Hierarchy of Hereditary Sorting Operators
Authors
Jelínek, V.; Opler, M.; Pekárek, J.
Year
2024
Published
Proceedings of the 35th ACM-SIAM Symposium on Discrete Algorithms, SODA ’24. Philadelphia: SIAM, 2024. p. 1447-1464. ISBN 978-1-61197-791-2.
Type
Proceedings paper
Departments
Annotation
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.
Improved Bounds for the Binary Paint Shop Problem
Authors
Hančl, J.; Kabela, A.; Opler, M.; Sosnovec, J.; Šámal, R.; Valtr, V.
Year
2023
Published
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.
Type
Proceedings paper
Departments
Annotation
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.
Bears with Hats and Independence Polynomials
Authors
Blažej, V.; Dvořák, P.; Opler, M.
Year
2023
Published
Discrete Mathematics and Theoretical Computer Science. 2023, 25(2), ISSN 1365-8050.
Type
Article
Departments
Annotation
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.
Hedonic Diversity Games: A Complexity Picture with More than Two Colors
Authors
Year
2023
Published
Artificial Intelligence. 2023, 325 1-20. ISSN 0004-3702.
Type
Article
Departments
Annotation
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).
Backward Pattern Matching on Elastic-Degenerate Strings
Authors
Procházka, P.; Cvacho, O.; Krčál, L.; Holub, J.
Year
2023
Published
SN Computer Science. 2023, 4(5), ISSN 2662-995X.
Type
Article
Departments
Annotation
Recently, the concept of Elastic Degenerate Strings (EDS) was introduced as a way of representing a sequenced population of the same species. Several on-line Elastic Degenerate String Matching (EDSM) algorithms were presented so far. Some of them provide practical implementation. We propose a new on-line EDSM algorithm BNDM-EDS. Our algorithm combines two traditional algorithms BNDM and the Shift-And that were adapted to the specifics needed by Elastic Degenerate Strings. BNDM-EDS is running in O (Nmd w m e) worst-case time.
This implies O (Nm) time for small patterns, where m is the length of the searched pattern, N is the size of EDS, and w is the size of the computer word. The algorithm uses O (N + n) space, where n is the length of EDS. BNDM-EDS requires a simple preprocessing step with time and space O(m). Experimental results on real genomic data show superiority of BNDM-EDS over state-of-the-art algorithms.
Treewidth Is NP-Complete on Cubic Graphs
Authors
Year
2023
Published
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.
Type
Proceedings paper
Departments
Annotation
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.
Bandwidth Parameterized by Cluster Vertex Deletion Number
Authors
Gima, T.; Kim, E.J.; Köhler, N.; Melissinos, N.; Vasilakis, M.
Year
2023
Published
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.
Type
Proceedings paper
Departments
Annotation
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.
Recontamination helps a lot to hunt a rabbit
Authors
Dissaux, T.; Fioravantes, F.; Gahlawat, H.; Nisse, N.
Year
2023
Published
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.
Type
Proceedings paper
Departments
Annotation
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.
Inexact tree pattern matching with 1-degree edit distance using finite automata
Authors
Šestáková, E.; Guth, O.; Janoušek, J.
Year
2023
Published
Discrete Applied Mathematics. 2023, 330 78-97. ISSN 0166-218X.
Type
Article
Departments
Annotation
Given an input tree and a tree pattern, the inexact tree pattern matching problem is about finding all subtrees in the input tree that match the tree pattern with up to errors. To measure the number of errors between two labeled ordered trees, we use the 1-degree edit distance that uses operations node relabel, leaf insert, and leaf delete. The proposed solution is based on a finite automaton that reads a given input tree represented in linear, prefix bar, notation. First, we show its construction for a constrained variant of 1-degree edit distance where leaf insert/delete operations cannot be applied to the tree pattern recursively. Then, we extend this approach to both unit cost and non-unit cost 1-degree edit distance. The deterministic version of the proposed finite automaton finds all inexact occurrences of the tree pattern in time linear to the size of the input tree. However, since the size of such automaton can be exponential in the number of nodes of the tree pattern, it is practical only for small patterns. Therefore, we also consider the dynamic programming approach as a way of simulating the nondeterministic finite automaton. This approach comes with the space complexity and time complexity where is the number of nodes of the tree pattern, is the number of nodes of the input tree, and is the maximum number of errors allowed.
Parameterized Max Min Feedback Vertex Set
Authors
Lampis, M.; Melissinos, N.; Vasilakis, M.
Year
2023
Published
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.
Type
Proceedings paper
Departments
Annotation
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).
On the Smallest Synchronizing Terms of Finite Tree Automata
Authors
Blažej, V.; Janoušek, J.; Plachý, Š.
Year
2023
Published
Implementation and Application of Automata. Springer, Cham, 2023. p. 79-90. LNCS. vol. 14151. ISSN 1611-3349. ISBN 978-3-031-40247-0.
Type
Proceedings paper
Departments
Annotation
This paper deals with properties of synchronizing terms for finite tree automata, which is a generalization of the synchronization principle of deterministic finite string automata (DFA) and such terms correspond to a connected subgraph, where a state in the root is always the same regardless of states of subtrees attached to it. We ask, what is the maximum height of the smallest synchronizing term of a deterministic bottom-up tree automaton (DFTA) with n states, which naturally leads to two types of synchronizing terms, called weak and strong, that depend on whether a variable, i.e., a placeholder for a subtree, must be present in at least one leaf or all of them. We prove that the maximum height in the case of weak synchronization has a theoretical upper bound sl(𝑛)+𝑛−1, where sl(𝑛) is the maximum length of the shortest synchronizing string of an n-state DFAs. For strong synchronization, we prove exponential bounds. We provide a theoretical upper bound of 2^𝑛−𝑛−1 for the height and two constructions of automata approaching it. One achieves the height of Θ(2^(𝑛−√𝑛)) with an alphabet of linear size, and the other achieves 2^(𝑛−1)−1 with an alphabet of quadratic size.
Shortest Dominating Set Reconfiguration under Token Sliding
Authors
Křišťan, J.; Svoboda, J.
Year
2023
Published
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.
Type
Proceedings paper
Departments
Annotation
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.
High-multiplicity N-fold IP via configuration LP
Authors
Knop, D.; Koutecky, M.; Levin, A.; Mnich, M.; Onn, S.
Year
2023
Published
Mathematical Programming. 2023, 2023(200), 199-227. ISSN 0025-5610.
Type
Article
Departments
Annotation
N-fold integer programs (IPs) form an important class of block-structured IPs for which increasingly fast algorithms have recently been developed and successfully applied. We study high-multiplicityN-fold IPs, which encode IPs succinctly by presenting a description of each block type and a vector of block multiplicities. Our goal is to design algorithms which solve N-fold IPs in time polynomial in the size of the succinct encoding, which may be significantly smaller than the size of the explicit (non-succinct) instance. We present the first fixed-parameter algorithm for high-multiplicity N-fold IPs, which even works for convex objectives. Our key contribution is a novel proximity theorem which relates fractional and integer optima of the Configuration LP, a fundamental notion by Gilmore and Gomory [Oper. Res., 1961] which we generalize. Our algorithm for N-fold IP is faster than previous algorithms whenever the number of blocks is much larger than the number of block types, such as in N-fold IP models for various scheduling problems.
A categorical account of composition methods in logic
Authors
Jakl, T.; Marsden, D.; Shah, N.
Year
2023
Published
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.
Type
Proceedings paper
Departments
Annotation
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
Authors
Year
2023
Published
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.
Type
Proceedings paper
Departments
Annotation
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.
Odd Chromatic Number of Graph Classes
Authors
Belmonte, R.; Harutyunyan, A.; Köhler, N.; Melissinos, N.
Year
2023
Published
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.
Type
Proceedings paper
Departments
Annotation
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.
Generating Faster Algorithms for d-Path Vertex Cover
Authors
Červený, R.; Suchý, O.
Year
2023
Published
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.
Type
Proceedings paper
Departments
Annotation
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.
Degreewidth: A New Parameter for Solving Problems on Tournaments
Authors
Davot, T.; Isenmann, L.; Roy, S.; Thiebaut, J.
Year
2023
Published
Proceedings of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science. Cham: Springer, 2023. p. 246-260. Lecture Notes in Computer Science. vol. 14093. ISSN 0302-9743. ISBN 978-3-031-43379-5.
Type
Proceedings paper
Departments
Annotation
In the paper, we define a new parameter for tournaments called degreewidth which can be seen as a measure of how far is the tournament from being acyclic. The degreewidth of a tournament T denoted by is the minimum value k for which we can find an ordering of the vertices of T such that every vertex is incident to at most k backward arcs (i.e. an arc such that ). Thus, a tournament is acyclic if and only if its degreewidth is zero. Additionally, the class of sparse tournaments defined by Bessy et al. [ESA 2017] is exactly the class of tournaments with degreewidth one.
We study computational complexity of finding degreewidth. We show it is NP-hard and complement this result with a 3-approximation algorithm. We provide a -time algorithm to decide if a tournament is sparse, where n is its number of vertices.
Finally, we study classical graph problems DOMINATING SET and FEEDBACK VERTEX SET parameterized by degreewidth. We show the former is fixed-parameter tractable whereas the latter is NP-hard even on sparse tournaments. Additionally, we show polynomial time algorithm for FEEDBACK ARC SET on sparse tournaments.
Bounds on Functionality and Symmetric Difference – Two Intriguing Graph Parameters
Authors
Dvořák, P.; Folwarczný, L.; Opler, M.; Pudlák, P.; Šámal, R.; Vu, T.A.
Year
2023
Published
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.
Type
Proceedings paper
Departments
Annotation
[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?
Establishing Herd Immunity is Hard Even in Simple Geometric Networks
Authors
Year
2023
Published
Proceedings of the 18th Workshop on Algorithms and Models for the Web Graph. Cham: Springer, 2023. p. 68-82. Lecture Notes in Computer Science. vol. 13894. ISSN 0302-9743. ISBN 978-3-031-32295-2.
Type
Proceedings paper
Departments
Annotation
We study the following model of disease spread in a social network. In the beginning, all individuals are either ``infected'' or ``healthy''. Next, in discrete rounds, the disease spreads in the network from infected to healthy individuals such that a healthy individual gets infected if and only if a sufficient number of its direct neighbours are already infected.
We represent the social network as a graph. Inspired by the real-world restrictions in the current epidemic, especially by social and physical distancing requirements, we restrict ourselves to networks that can be represented as geometric intersection graphs.
We show that finding a minimal vertex set of initially infected individuals to spread the disease in the whole network is computationally hard, already on unit disk graphs. Hence, to provide some algorithmic results, we focus ourselves on simpler geometric graph families, such as interval graphs and grid graphs.
Improved kernels for tracking paths
Authors
Choudhary, P.; Goodrich, M.T.; Gupta, S.; Khodabandeh, H.; Matias, P.; Raman, V.
Year
2023
Published
Information Processing Letters. 2023, 181 ISSN 0020-0190.
Type
Article
Departments
Annotation
Tracking of moving objects is crucial to security systems and networks. Given a graph G,
terminal vertices s and t, and an integer k, the Tracking Paths problem asks whether there exists at most k vertices, which if marked as trackers, would ensure that the sequence of trackers encountered in each s-t path is unique. It is known that the problem is NP-hard and admits a kernel (reducible to an equivalent instance) with O(k6) vertices and O(k7) edges, when parameterized by the size of the output (tracking set) k [4]. In this paper we improve the size of the kernel substantially by providing a kernel with O (k2) vertices and edges for general graphs and a kernel with O (k) vertices and edges for planar graphs. We do this via a new concept, namely a tree-sink structure. We also show that finding a tracking set of size at most n − k for a graph on n vertices is hard for the parameterized complexity class W[1], when parameterized by k
Host Community Respecting Refugee Housing
Authors
Year
2023
Published
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.
Type
Proceedings paper
Departments
Annotation
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.
Bribery Can Get Harder in Structured Multiwinner Approval Election
Authors
Kusek, B.; Bredereck, R.; Faliszewski, P.; Kaczmarczyk, A.; Knop, D.
Year
2023
Published
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.
Type
Proceedings paper
Departments
Annotation
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.
Constant factor approximation for tracking paths and fault tolerant feedback vertex set
Authors
Year
2023
Published
Discrete Optimization. 2023, 47 ISSN 1572-5286.
Type
Article
Departments
Annotation
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.
The Parameterized Complexity of Network Microaggregation
Authors
Year
2023
Published
Proceedings of the 37th AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2023. p. 6262-6270. vol. 37. ISSN 2159-5399.
Type
Proceedings paper
Departments
Annotation
Microaggregation is a classical statistical disclosure control technique which requires the input data to be partitioned into clusters while adhering to specified size constraints. We provide novel exact algorithms and lower bounds for the task of microaggregating a given network while considering both unrestricted and connected clusterings, and analyze these from the perspective of the parameterized complexity paradigm. Altogether, our results assemble a complete complexity-theoretic picture for the network microaggregation problem with respect to the most natural parameterizations of the problem, including input-specified parameters capturing the size and homogeneity of the clusters as well as the treewidth and vertex cover number of the network.
Maximizing Influence Spread through a Dynamic Social Network
Authors
Year
2023
Published
Proceedings of the 37th AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2023. p. 16316-16317. vol. 37. ISSN 2159-5399.
Type
Proceedings paper
Departments
Annotation
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.
Polynomial kernels for tracking shortest paths
Authors
Year
2023
Published
Information Processing Letters. 2023, 179(1), ISSN 1872-6119.
Type
Article
Departments
Annotation
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
Authors
Kučera, M.; Suchý, O.
Year
2023
Published
Algorithmica. 2023, 85(3), 762-782. ISSN 0178-4617.
Type
Article
Departments
Annotation
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.