2021

Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Lowski, Stefanie; Melnichenko, Anna Selfish Creation of Social Networks. Conference on Artificial Intelligence (AAAI) 2021
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Understanding real-world networks has been a core research endeavor throughout the last two decades. Network Creation Games are a promising approach for this from a game-theoretic perspective. In these games, selfish agents corresponding to nodes in a network strategically decide which links to form to optimize their centrality. Many versions have been introduced and analyzed, but none of them fits to modeling the evolution of social networks. In real-world social networks, connections are often established by recommendations from common acquaintances or by a chain of such recommendations. Thus establishing and maintaining a contact with a friend of a friend is easier than connecting to complete strangers. This explains the high clustering, i.e., the abundance of triangles, in real-world social networks. We propose and analyze a network creation model inspired by real-world social networks. Edges are formed in our model via bilateral consent of both endpoints and the cost for establishing and maintaining an edge is proportional to the distance of the endpoints before establishing the connection. We provide results for generic cost functions, which essentially only must be convex functions in the distance of the endpoints without the respective edge. For this broad class of cost functions, we provide many structural properties of equilibrium networks and prove (almost) tight bounds on the diameter, the Price of Anarchy and the Price of Stability. Moreover, as a proof-of-concept we show via experiments that the created equilibrium networks of our model indeed closely mimics real-world social networks. We observe degree distributions that seem to follow a power-law, high clustering, and low diameters. This can be seen as a promising first step towards game-theoretic network creation models that predict networks featuring all core real-world properties.
@inproceedings{bilo2021selfish, abstract = {Understanding real-world networks has been a core research endeavor throughout the last two decades. Network Creation Games are a promising approach for this from a game-theoretic perspective. In these games, selfish agents corresponding to nodes in a network strategically decide which links to form to optimize their centrality. Many versions have been introduced and analyzed, but none of them fits to modeling the evolution of social networks. In real-world social networks, connections are often established by recommendations from common acquaintances or by a chain of such recommendations. Thus establishing and maintaining a contact with a friend of a friend is easier than connecting to complete strangers. This explains the high clustering, i.e., the abundance of triangles, in real-world social networks. We propose and analyze a network creation model inspired by real-world social networks. Edges are formed in our model via bilateral consent of both endpoints and the cost for establishing and maintaining an edge is proportional to the distance of the endpoints before establishing the connection. We provide results for generic cost functions, which essentially only must be convex functions in the distance of the endpoints without the respective edge. For this broad class of cost functions, we provide many structural properties of equilibrium networks and prove (almost) tight bounds on the diameter, the Price of Anarchy and the Price of Stability. Moreover, as a proof-of-concept we show via experiments that the created equilibrium networks of our model indeed closely mimics real-world social networks. We observe degree distributions that seem to follow a power-law, high clustering, and low diameters. This can be seen as a promising first step towards game-theoretic network creation models that predict networks featuring all core real-world properties.}, author = {Bilò, Davide and Friedrich, Tobias and Lenzner, Pascal and Lowski, Stefanie and Melnichenko, Anna}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {aaai annamelnichenko davidebilo pascallenzner stefanielowski tobiasfriedrich year2021}, title = {Selfish Creation of Social Networks}, year = 2021 }

Aziz, Haris; Cseh, Agnes; Dickerson, John; McElfresh, Duncan Optimal Kidney Exchange with Immunosuppressants. Conference on Artificial Intelligence (AAAI) 2021
[ BibTeX ]
 
@inproceedings{haris2021optimal, author = {Aziz, Haris and Cseh, Agnes and Dickerson, John and McElfresh, Duncan}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {aaai agnescseh duncanmcelfresh harisaziz johndickerson year2021}, title = {Optimal Kidney Exchange with Immunosuppressants}, year = 2021 }

Aziz, Haris; Chan, Hau; Cseh, Ágnes; Li, Bo; Ramezani, Fahimeh; Wang, Chenhao Multi-Robot Task Allocation—Complexity and Approximation. Autonomous Agents and Multiagent Systems (AAMAS) 2021
[ BibTeX ]
 
@inproceedings{aziz2021multirobot, author = {Aziz, Haris and Chan, Hau and Cseh, Ágnes and Li, Bo and Ramezani, Fahimeh and Wang, Chenhao}, booktitle = {Autonomous Agents and Multiagent Systems (AAMAS)}, keywords = {aamas agnescseh boli chenhaowang fahimehramezani harisaziz hauchan year2021}, title = {Multi-Robot Task Allocation—Complexity and Approximation}, year = 2021 }

Kraiczy, Sonja; Cseh, Ágnes; Manlove, David On Weakly and Strongly Popular Rankings. Autonomous Agents and Multiagent Systems (AAMAS) 2021
[ BibTeX ]
 
@inproceedings{kraiczy2021weakly, author = {Kraiczy, Sonja and Cseh, Ágnes and Manlove, David}, booktitle = {Autonomous Agents and Multiagent Systems (AAMAS)}, keywords = {aamas agnescseh davidfmanlove sonjakraiczy year2021}, title = {On Weakly and Strongly Popular Rankings}, year = 2021 }

Cooley, Madison; Greene, Casey; Issac, Davis; Pividori, Milton; Sullivan, Blair Parameterized Algorithms for Identifying Gene Co-Expression Modules via Weighted Clique Decomposition. Applied and Computational Discrete Algorithms (ACDA) 2021
[ Abstract ] [ BibTeX ]
 
We present a new combinatorial model for identifying regulatory modules in gene co-expression data using a decomposition into weighted cliques. To capture complex interaction effects, we generalize the previously-studied weighted edge clique partition problem. As a first step, we restrict ourselves to the noise-free setting, and show that the problem is fixed parameter tractable when parameterized by the number of modules (cliques). We present two new algorithms for finding these decompositions, using linear programming and integer partitioning to determine the clique weights. Further, we implement these algorithms in Python and test them on a biologically-inspired synthetic corpus generated using real-world data from transcription factors and a latent variable analysis of co-expression in varying cell types.
@inproceedings{cooley2021parameterized, abstract = {We present a new combinatorial model for identifying regulatory modules in gene co-expression data using a decomposition into weighted cliques. To capture complex interaction effects, we generalize the previously-studied weighted edge clique partition problem. As a first step, we restrict ourselves to the noise-free setting, and show that the problem is fixed parameter tractable when parameterized by the number of modules (cliques). We present two new algorithms for finding these decompositions, using linear programming and integer partitioning to determine the clique weights. Further, we implement these algorithms in Python and test them on a biologically-inspired synthetic corpus generated using real-world data from transcription factors and a latent variable analysis of co-expression in varying cell types.}, author = {Cooley, Madison and Greene, Casey and Issac, Davis and Pividori, Milton and Sullivan, Blair}, booktitle = {Applied and Computational Discrete Algorithms (ACDA)}, keywords = {sys:relevantfor:ae acda blairsullivan caseygreene davisissac madisoncooley miltonpividori year2021}, title = {Parameterized Algorithms for Identifying Gene Co-Expression Modules via Weighted Clique Decomposition}, year = 2021 }

Quinzan, Francesco; Doskoč, Vanja; Göbel, Andreas; Friedrich, Tobias Adaptive Sampling for Fast Constrained Maximization of Submodular Functions. Artificial Intelligence and Statistics (AISTATS) 2021: 964–972
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Several large-scale machine learning tasks, such as data summarization, can be approached by maximizing functions that satisfy submodularity. These optimization problems often involve complex side constraints, imposed by the underlying application. In this paper, we develop an algorithm with poly-logarithmic adaptivity for non-monotone submodular maximization under general side constraints. The adaptive complexity of a problem is the minimal number of sequential rounds required to achieve the objective. Our algorithm is suitable to maximize a non-monotone submodular function under a \(p\)-system side constraint, and it achieves a \((p + O({\sqrt{p}}))\)-approximation for this problem, after only poly-logarithmic adaptive rounds and polynomial queries to the valuation oracle function. Furthermore, our algorithm achieves a \(p + O(1))\)-approximation when the given side constraint is a \(p\)-extendible system. This algorithm yields an exponential speed-up, with respect to the adaptivity, over any other known constant-factor approximation algorithm for this problem. It also competes with previous known results in terms of the query complexity. We perform various experiments on various real-world applications. We find that, in comparison with commonly used heuristics, our algorithm performs better on these instances.
@inproceedings{doskoc2021adaptive, abstract = {Several large-scale machine learning tasks, such as data summarization, can be approached by maximizing functions that satisfy submodularity. These optimization problems often involve complex side constraints, imposed by the underlying application. In this paper, we develop an algorithm with poly-logarithmic adaptivity for non-monotone submodular maximization under general side constraints. The adaptive complexity of a problem is the minimal number of sequential rounds required to achieve the objective. Our algorithm is suitable to maximize a non-monotone submodular function under a \(p\)-system side constraint, and it achieves a \((p + O({\sqrt{p}}))\)-approximation for this problem, after only poly-logarithmic adaptive rounds and polynomial queries to the valuation oracle function. Furthermore, our algorithm achieves a \(p + O(1))\)-approximation when the given side constraint is a \(p\)-extendible system. This algorithm yields an exponential speed-up, with respect to the adaptivity, over any other known constant-factor approximation algorithm for this problem. It also competes with previous known results in terms of the query complexity. We perform various experiments on various real-world applications. We find that, in comparison with commonly used heuristics, our algorithm performs better on these instances.}, author = {Quinzan, Francesco and Doskoč, Vanja and Göbel, Andreas and Friedrich, Tobias}, booktitle = {Artificial Intelligence and Statistics (AISTATS)}, keywords = {aistats andreasgoebel francescoquinzan tobiasfriedrich vanjadoskoc year2021}, pages = {964-972}, title = {Adaptive Sampling for Fast Constrained Maximization of Submodular Functions}, year = 2021 }

Borndörfer, Ralf; Casel, Katrin; Issac, Davis; Niklanovits, Aikaterini; Schwartz, Stephan; Zeif, Ziena Connected k-Partition of k-Connected Graphs and c-Claw-Free Graphs. Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2021
[ Abstract ] [ BibTeX ]
 
A connected partition is a partition of the vertices of a graph into sets that induce connected subgraphs. Such partitions naturally occur in many application areas such as road networks, and image processing. In these settings, it is often desirable to partition into a fixed number of parts of roughly of the same size or weight. The resulting computational problem is called Balanced Connected Partition (BCP). The two classical objectives for BCP are to maximize the weight of the smallest, or minimize the weight of the largest component. We study BCP on \(c\)-claw-free graphs, the class of graphs that do not have \(K_{1,c}\) as an induced subgraph, and present efficient \((c-1)\)-approximation algorithms for both objectives. In particular, for \(3\)-claw-free graphs, also simply known as claw-free graphs, we obtain a \(2\)-approximation. Due to the claw-freeness of line graphs, this also implies a \(2\)-approximation for the edge-partition version of BCP in general graphs. A harder connected partition problem arises from demanding a connected partition into k parts that have (possibly) heterogeneous target weights \(w_1, \dots, w_k\). In the 1970s Győri and Lovász showed that if \(G\) is \(k\)-connected and the target weights sum to the total size of \(G\), such a partition exists. However, to this day no polynomial algorithm to compute such partitions exists for \(k > 4\). Towards finding such a partition \(T_1, \dots, T_k\) in \(k\)-connected graphs for general \(k\), we show how to efficiently compute connected partitions that at least approximately meet the target weights, subject to the mild assumption that each \(w_i\) is greater than the weight of the heaviest vertex. In particular, we give a \(3\)-approximation for both the lower and the upper bounded version i.e. we guarantee that each \(T_i\) has weight at least \(\frac{w_i}{3}\) or that each \(T_i\) has weight most \(3 w_i\), respectively. Also, we present a both-side bounded version that produces a connected partition where each \(T_i\) has size at least \(\frac{w_i}{3}\) and at most \(\max(\{r, 3\}) w_i \), where \(r \geq 1\) is the ratio between the largest and smallest value in \(w_1, \dots, w_k\). In particular for the balanced version, i.e. \(w_1 = w_2 =, \dots , = w k\), this gives a partition with \(\frac{w_i}{3} leq w(T_i) \leq 3 w_i\).
@inproceedings{borndorfer2021connected, abstract = {A connected partition is a partition of the vertices of a graph into sets that induce connected subgraphs. Such partitions naturally occur in many application areas such as road networks, and image processing. In these settings, it is often desirable to partition into a fixed number of parts of roughly of the same size or weight. The resulting computational problem is called Balanced Connected Partition (BCP). The two classical objectives for BCP are to maximize the weight of the smallest, or minimize the weight of the largest component. We study BCP on \(c\)-claw-free graphs, the class of graphs that do not have \(K_{1,c}\) as an induced subgraph, and present efficient \((c-1)\)-approximation algorithms for both objectives. In particular, for \(3\)-claw-free graphs, also simply known as claw-free graphs, we obtain a \(2\)-approximation. Due to the claw-freeness of line graphs, this also implies a \(2\)-approximation for the edge-partition version of BCP in general graphs. A harder connected partition problem arises from demanding a connected partition into k parts that have (possibly) heterogeneous target weights \(w_1, \dots, w_k\). In the 1970s Győri and Lovász showed that if \(G\) is \(k\)-connected and the target weights sum to the total size of \(G\), such a partition exists. However, to this day no polynomial algorithm to compute such partitions exists for \(k > 4\). Towards finding such a partition \(T_1, \dots, T_k\) in \(k\)-connected graphs for general \(k\), we show how to efficiently compute connected partitions that at least approximately meet the target weights, subject to the mild assumption that each \(w_i\) is greater than the weight of the heaviest vertex. In particular, we give a \(3\)-approximation for both the lower and the upper bounded version i.e. we guarantee that each \(T_i\) has weight at least \(\frac{w_i}{3}\) or that each \(T_i\) has weight most \(3 w_i\), respectively. Also, we present a both-side bounded version that produces a connected partition where each \(T_i\) has size at least \(\frac{w_i}{3}\) and at most \(\max(\{r, 3\}) w_i \), where \(r \geq 1\) is the ratio between the largest and smallest value in \(w_1, \dots, w_k\). In particular for the balanced version, i.e. \(w_1 = w_2 =, \dots , = w k\), this gives a partition with \(\frac{w_i}{3} leq w(T_i) \leq 3 w_i\).}, author = {Borndörfer, Ralf and Casel, Katrin and Issac, Davis and Niklanovits, Aikaterini and Schwartz, Stephan and Zeif, Ziena}, booktitle = {Approximation Algorithms for Combinatorial Optimization Problems (APPROX)}, keywords = {sys:relevantfor:ae aikaterininiklanovits approx davisissac katrincasel ralfborndörfer stephanschwartz year2021}, title = {Connected k-Partition of k-Connected Graphs and c-Claw-Free Graphs}, year = 2021 }

Berger, Julian; Böther, Maximilian; Doskoč, Vanja; Gadea Harder, Jonathan; Klodt, Nicolas; Kötzing, Timo; Lötzsch, Winfried; Peters, Jannik; Schiller, Leon; Seifert, Lars; Wells, Armin; Wietheger, Simon Learning Languages with Decidable Hypotheses. Computability in Europe (CiE) 2021
[ BibTeX ] [ Download ]
 
@inproceedings{berger2021learning, author = {Berger, Julian and Böther, Maximilian and Doskoč, Vanja and Gadea Harder, Jonathan and Klodt, Nicolas and Kötzing, Timo and Lötzsch, Winfried and Peters, Jannik and Schiller, Leon and Seifert, Lars and Wells, Armin and Wietheger, Simon}, booktitle = {Computability in Europe (CiE)}, keywords = {arminwells cie jannikpeters jonathangadeaharder julianberger larsseifert leonschiller maximilianboether nicolasklodt simonwietheger timokoetzing vanjadoskoc winfriedloetzsch year2021}, title = {Learning Languages with Decidable Hypotheses}, year = 2021 }

Doskoč, Vanja; Kötzing, Timo Mapping Monotonic Restrictions in Inductive Inference. Computability in Europe (CiE) 2021
[ BibTeX ] [ Download ]
 
@inproceedings{doskoc2021mapping, author = {Doskoč, Vanja and Kötzing, Timo}, booktitle = {Computability in Europe (CiE)}, keywords = {cie timokoetzing vanjadoskoc year2021}, title = {Mapping Monotonic Restrictions in Inductive Inference}, year = 2021 }

Khazraei, Ardalan; Kötzing, Timo; Seidel, Karen Towards a Map for Incremental Learning in the Limit from Positive and Negative Information. Computability in Europe (CiE) 2021
[ BibTeX ] [ Download ]
 
@inproceedings{khazraei2021towards, author = {Khazraei, Ardalan and Kötzing, Timo and Seidel, Karen}, booktitle = {Computability in Europe (CiE)}, keywords = {ardalankhazraei cie karenseidel timokoetzing year2021}, title = {Towards a Map for Incremental Learning in the Limit from Positive and Negative Information}, year = 2021 }

Doskoč, Vanja; Kötzing, Timo Normal Forms for Semantically Witness-Based Learners in Inductive Inference. Computability in Europe (CiE) 2021
[ BibTeX ] [ Download ]
 
@inproceedings{doskoc2021normal, author = {Doskoč, Vanja and Kötzing, Timo}, booktitle = {Computability in Europe (CiE)}, keywords = {cie timokoetzing vanjadoskoc year2021}, title = {Normal Forms for Semantically Witness-Based Learners in Inductive Inference}, year = 2021 }

Kötzing, Timo; Seidel, Karen Learning Languages in the Limit from Positive Information with Finitely Many Memory Changes. Computability in Europe (CiE) 2021
[ BibTeX ] [ Download ]
 
@inproceedings{kotzing2021learning, author = {Kötzing, Timo and Seidel, Karen}, booktitle = {Computability in Europe (CiE)}, keywords = {cie karenseidel timokoetzing year2021}, title = {Learning Languages in the Limit from Positive Information with Finitely Many Memory Changes}, year = 2021 }

Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry. European Symposium on Algorithms (ESA) 2021
[ Abstract ] [ BibTeX ]
 
Finding a minimum vertex cover in a network is a fundamental NP-complete graph problem. One way to deal with its computational hardness, is to trade the qualitative performance of an algorithm (allowing non-optimal outputs) for an improved running time. For the vertex cover problem, there is a gap between theory and practice when it comes to understanding this tradeoff. On the one hand, it is known that it is NP-hard to approximate a minimum vertex cover within a factor of \(\sqrt{2}\). On the other hand, a simple greedy algorithm yields close to optimal approximations in practice. A promising approach towards understanding this discrepancy is to recognize the differences between theoretical worst-case instances and real-world networks. Following this direction, we close the gap between theory and practice by providing an algorithm that efficiently computes nearly optimal vertex cover approximations on hyperbolic random graphs; a network model that closely resembles real-world networks in terms of degree distribution, clustering, and the small-world property. More precisely, our algorithm computes a \((1 + o(1))\)-approximation, asymptotically almost surely, and has a running time of \(\mathcal{O}(m \log(n))\). The proposed algorithm is an adaption of the successful greedy approach, enhanced with a procedure that improves on parts of the graph where greedy is not optimal. This makes it possible to introduce a parameter that can be used to tune the tradeoff between approximation performance and running time. Our empirical evaluation on real-world networks shows that this allows for improving over the near-optimal results of the greedy approach.
@inproceedings{blasius2021efficiently, abstract = {Finding a minimum vertex cover in a network is a fundamental NP-complete graph problem. One way to deal with its computational hardness, is to trade the qualitative performance of an algorithm (allowing non-optimal outputs) for an improved running time. For the vertex cover problem, there is a gap between theory and practice when it comes to understanding this tradeoff. On the one hand, it is known that it is NP-hard to approximate a minimum vertex cover within a factor of \(\sqrt{2}\). On the other hand, a simple greedy algorithm yields close to optimal approximations in practice. A promising approach towards understanding this discrepancy is to recognize the differences between theoretical worst-case instances and real-world networks. Following this direction, we close the gap between theory and practice by providing an algorithm that efficiently computes nearly optimal vertex cover approximations on hyperbolic random graphs; a network model that closely resembles real-world networks in terms of degree distribution, clustering, and the small-world property. More precisely, our algorithm computes a \((1 + o(1))\)-approximation, asymptotically almost surely, and has a running time of \(\mathcal{O}(m \log(n))\). The proposed algorithm is an adaption of the successful greedy approach, enhanced with a procedure that improves on parts of the graph where greedy is not optimal. This makes it possible to introduce a parameter that can be used to tune the tradeoff between approximation performance and running time. Our empirical evaluation on real-world networks shows that this allows for improving over the near-optimal results of the greedy approach.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {esa maximiliankatzmann thomasblaesius tobiasfriedrich year2021}, title = {Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry}, year = 2021 }

Bilò, Davide; Cohen, Sarel; Friedrich, Tobias; Schirneck, Martin Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles. European Symposium on Algorithms (ESA) 2021
[ Abstract ] [ BibTeX ]
 
Given a graph with a distinguished source vertex \(s\), the Single Source Replacement Paths (SSRP) problem is to compute and output, for any target vertex \(t\) and edge \(e\), the length \(d(s,t,e)\) of a shortest path from \(s\) to \(t\) that avoids a failing edge \(e\). A Single-Source Distance Sensitivity Oracle (Single-Source DSO) is a compact data structure that answers queries of the form \((t,e)\) by returning the distance \(d(s,t,e)\). We show how to compress the output of the SSRP problem on \(n\)-vertex, \(m\)-edge graphs with integer edge weights in the range \([1,M]\) into a deterministic Single-Source DSO that has size \(O(M^{1/2} n^{3/2})\) and query time \(\widetilde{O}(1)\). We prove that the space requirement is optimal (up to the word size). Our techniques can also handle vertex failures within the same bounds. Chechik and Cohen [SODA 2019] presented a combinatorial randomized \(\widetilde{O}(m\sqrt{n}+n^2)\) time SSRP algorithm for undirected and unweighted graphs. We derandomize their algorithm with the same asymptotic running time and apply our compression to obtain a deterministic Single-Source DSO with \(\widetilde{O}(m\sqrt{n}+n^2)\) preprocessing time, \(O(n^{3/2})\) space, and \(\widetilde{O}(1)\) query time. Our combinatorial Single-Source DSO has near-optimal space, preprocessing and query time for dense unweighted graphs, improving the preprocessing time by a \(\sqrt{n}\)-factor compared to previous results. Grandoni and Vassilevska Williams [FOCS 2012, TALG 2020] gave an algebraic randomized \(\widetilde{O}(Mn^\omega)\) time SSRP algorithm for (undirected and directed) graphs with integer edge weights in the range \([1,M]\), where \(\omega < 2.373\) is the matrix multiplication exponent. We derandomize their algorithm for undirected graphs and apply our compression to obtain an algebraic Single-Source DSO with \(\widetilde{O}(Mn^\omega)\) preprocessing time, \(O(M^{1/2} n^{3/2})\) space, and \(\widetilde{O}(1)\) query time. This improves the preprocessing time of algebraic Single-Source DSOs by polynomial factors compared to previous results. We also present further improvements of our Single-Source DSOs. We show that the query time can be reduced to a constant at the cost of increasing the size of the oracle to \(O(M^{1/3} n^{5/3})\) and that all our oracles can be made path-reporting. On sparse graphs with \(m=O(\frac{n^{5/4-\varepsilon}}{M^{7/4}})\) edges, for any constant \(\varepsilon > 0\), we reduce the preprocessing to randomized \(\widetilde{O}(M^{7/8} m^{1/2} n^{11/8}) = O(n^{2-\varepsilon/2})\) time. To the best of our knowledge, this is the first truly subquadratic time algorithm for building Single-Source DSOs on sparse graphs.
@inproceedings{bilo2021nearoptimal, abstract = {Given a graph with a distinguished source vertex \(s\), the Single Source Replacement Paths (SSRP) problem is to compute and output, for any target vertex \(t\) and edge \(e\), the length \(d(s,t,e)\) of a shortest path from \(s\) to \(t\) that avoids a failing edge \(e\). A Single-Source Distance Sensitivity Oracle (Single-Source DSO) is a compact data structure that answers queries of the form \((t,e)\) by returning the distance \(d(s,t,e)\). We show how to compress the output of the SSRP problem on \(n\)-vertex, \(m\)-edge graphs with integer edge weights in the range \([1,M]\) into a deterministic Single-Source DSO that has size \(O(M^{1/2} n^{3/2})\) and query time \(\widetilde{O}(1)\). We prove that the space requirement is optimal (up to the word size). Our techniques can also handle vertex failures within the same bounds. Chechik and Cohen [SODA 2019] presented a combinatorial randomized \(\widetilde{O}(m\sqrt{n}+n^2)\) time SSRP algorithm for undirected and unweighted graphs. We derandomize their algorithm with the same asymptotic running time and apply our compression to obtain a deterministic Single-Source DSO with \(\widetilde{O}(m\sqrt{n}+n^2)\) preprocessing time, \(O(n^{3/2})\) space, and \(\widetilde{O}(1)\) query time. Our combinatorial Single-Source DSO has near-optimal space, preprocessing and query time for dense unweighted graphs, improving the preprocessing time by a \(\sqrt{n}\)-factor compared to previous results. Grandoni and Vassilevska Williams [FOCS 2012, TALG 2020] gave an algebraic randomized \(\widetilde{O}(Mn^\omega)\) time SSRP algorithm for (undirected and directed) graphs with integer edge weights in the range \([1,M]\), where \(\omega < 2.373\) is the matrix multiplication exponent. We derandomize their algorithm for undirected graphs and apply our compression to obtain an algebraic Single-Source DSO with \(\widetilde{O}(Mn^\omega)\) preprocessing time, \(O(M^{1/2} n^{3/2})\) space, and \(\widetilde{O}(1)\) query time. This improves the preprocessing time of algebraic Single-Source DSOs by polynomial factors compared to previous results. We also present further improvements of our Single-Source DSOs. We show that the query time can be reduced to a constant at the cost of increasing the size of the oracle to \(O(M^{1/3} n^{5/3})\) and that all our oracles can be made path-reporting. On sparse graphs with \(m=O(\frac{n^{5/4-\varepsilon}}{M^{7/4}})\) edges, for any constant \(\varepsilon > 0\), we reduce the preprocessing to randomized \(\widetilde{O}(M^{7/8} m^{1/2} n^{11/8}) = O(n^{2-\varepsilon/2})\) time. To the best of our knowledge, this is the first truly subquadratic time algorithm for building Single-Source DSOs on sparse graphs.}, author = {Bilò, Davide and Cohen, Sarel and Friedrich, Tobias and Schirneck, Martin}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {davidebilo esa martinschirneck sarelcohen tobiasfriedrich year2021}, title = {Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles}, year = 2021 }

Casel, Katrin; Friedrich, Tobias; Issac, Davis; Niklanovits, Aikaterini; Zeif, Ziena Balanced Crown Decomposition for Connectivity Constraints. European Symposium on Algorithms (ESA) 2021
[ Abstract ] [ BibTeX ]
 
We introduce the balanced crown decomposition that captures the structure imposed on graphs by their connected induced subgraphs of a given size. Such subgraphs are a popular modeling tool in various application areas, where the non-local nature of the connectivity condition usually results in very challenging algorithmic tasks. The balanced crown decomposition is a combination of a crown decomposition and a balanced partition which makes it applicable to graph editing as well as graph packing and partitioning problems. We illustrate this by deriving improved approximation algorithms and kernelization for a variety of such problems. In particular, through this structure, we obtain the first constant-factor approximation for the Balanced Connected Partition (BCP) problem, where the task is to partition a vertex-weighted graph into k connected components of approximately equal weight. We derive a \(3\)-approximation for the two most commonly used objectives of maximizing the weight of the lightest component or minimizing the weight of the heaviest component.
@inproceedings{casel2021balanced, abstract = {We introduce the balanced crown decomposition that captures the structure imposed on graphs by their connected induced subgraphs of a given size. Such subgraphs are a popular modeling tool in various application areas, where the non-local nature of the connectivity condition usually results in very challenging algorithmic tasks. The balanced crown decomposition is a combination of a crown decomposition and a balanced partition which makes it applicable to graph editing as well as graph packing and partitioning problems. We illustrate this by deriving improved approximation algorithms and kernelization for a variety of such problems. In particular, through this structure, we obtain the first constant-factor approximation for the Balanced Connected Partition (BCP) problem, where the task is to partition a vertex-weighted graph into k connected components of approximately equal weight. We derive a \(3\)-approximation for the two most commonly used objectives of maximizing the weight of the lightest component or minimizing the weight of the heaviest component.}, author = {Casel, Katrin and Friedrich, Tobias and Issac, Davis and Niklanovits, Aikaterini and Zeif, Ziena}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {sys:relevantfor:ae aikaterininiklanovits davisissac esa katrincasel tobiasfriedrich year2021 zienazeif}, title = {Balanced Crown Decomposition for Connectivity Constraints}, year = 2021 }

Behrendt, Lukas; Casel, Katrin; Friedrich, Tobias; Lagodzinski, J. A. Gregor; Löser, Alexander; Wilhelm, Marcus From Symmetry to Asymmetry: Generalizing TSP Approximations by Parametrization. Fundamentals of Computation Theory (FCT) 2021
[ Abstract ] [ BibTeX ] [ Download ]
 
We generalize the tree doubling and Christofides algorithm to parameterized approximations for ATSP. The parameters we consider for the respective generalizations are upper bounded by the number of asymmetric distances, which yields algorithms to efficiently compute good approximations also for moderately asymmetric TSP instances. As generalization of the Christofides algorithm, we derive a parameterized 2.5-approximation, where the parameter is the size of a vertex cover for the subgraph induced by the asymmetric distances. Our generalization of the tree doubling algorithm gives a parameterized 3-approximation, where the parameter is the minimum number of asymmetric distances in a minimum spanning arborescence. Further, we combine these with a notion of symmetry relaxation which allows to trade approximation guarantee for runtime. Since the two parameters we consider are theoretically incomparable, we present experimental results which show that generalized tree doubling frequently outperforms generalized Christofides with respect to parameter size.
@inproceedings{behrendt2021symmetry, abstract = {We generalize the tree doubling and Christofides algorithm to parameterized approximations for ATSP. The parameters we consider for the respective generalizations are upper bounded by the number of asymmetric distances, which yields algorithms to efficiently compute good approximations also for moderately asymmetric TSP instances. As generalization of the Christofides algorithm, we derive a parameterized 2.5-approximation, where the parameter is the size of a vertex cover for the subgraph induced by the asymmetric distances. Our generalization of the tree doubling algorithm gives a parameterized 3-approximation, where the parameter is the minimum number of asymmetric distances in a minimum spanning arborescence. Further, we combine these with a notion of symmetry relaxation which allows to trade approximation guarantee for runtime. Since the two parameters we consider are theoretically incomparable, we present experimental results which show that generalized tree doubling frequently outperforms generalized Christofides with respect to parameter size.}, author = {Behrendt, Lukas and Casel, Katrin and Friedrich, Tobias and Lagodzinski, J. A. Gregor and Löser, Alexander and Wilhelm, Marcus}, booktitle = {Fundamentals of Computation Theory (FCT)}, editor = {Bampis, Evripidis and Pagourtzis, Aris}, keywords = {alexanderloeser fct gregorlagodzinski katrincasel lukasbehrend marcuswilhelm tobiasfriedrich year2021}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {From Symmetry to Asymmetry: Generalizing TSP Approximations by Parametrization}, year = 2021 }

Berger, Julian; Bleidt, Tibor; Büßemeyer, Martin; Ding, Marcus; Feldmann, Moritz; Feuerpfeil, Moritz; Jacoby, Janusch; Schröter, Valentin; Sievers, Bjarne; Spranger, Moritz; Stadlinger, Simon; Wullenweber, Paul; Cohen, Sarel; Doskoč, Vanja; Friedrich, Tobias Fine-Grained Localization, Classification and Segmentation of Lungs with Various Diseases. CVPR Workshop on Fine-Grained Visual Categorization (FGVC@CVPR) 2021
[ BibTeX ] [ Download ]
 
@inproceedings{berger2021finegrained, author = {Berger, Julian and Bleidt, Tibor and Büßemeyer, Martin and Ding, Marcus and Feldmann, Moritz and Feuerpfeil, Moritz and Jacoby, Janusch and Schröter, Valentin and Sievers, Bjarne and Spranger, Moritz and Stadlinger, Simon and Wullenweber, Paul and Cohen, Sarel and Doskoč, Vanja and Friedrich, Tobias}, booktitle = {CVPR Workshop on Fine-Grained Visual Categorization (FGVC@CVPR)}, keywords = {bjarnesievers fgvc@cvpr januschjacoby julianberger marcusding martinbuessemeyer moritzfeldmann moritzfeuerpfeil moritzspranger paulwullenweber sarelcohen simonstadlinger tiborbleidt tobiasfriedrich valentinschroeter vanjadoskoc year2021}, title = {Fine-Grained Localization, Classification and Segmentation of Lungs with Various Diseases}, year = 2021 }

Doerr, Benjamin; Kötzing, Timo Lower Bounds from Fitness Levels Made Easy. Genetic and Evolutionary Computation Conference (GECCO) 2021
[ Abstract ] [ BibTeX ] [ Download ]
 
One of the first and easy to use techniques for proving run time bounds for evolutionary algorithms is the so-called method of fitness levels by Wegener. It uses a partition of the search space into a sequence of levels which are traversed by the algorithm in increasing order, possibly skipping levels. An easy, but often strong upper bound for the run time can then be derived by adding the reciprocals of the probabilities to leave the levels (or upper bounds for these). Unfortunately, a similarly effective method for proving lower bounds has not yet been established. The strongest such method, proposed by Sudholt (2013), requires a careful choice of the viscosity parameters gamma. In this paper we present two new variants of the method, one for upper and one for lower bounds. Besides the level leaving probabilities, they only rely on the probabilities that levels are visited at all. We show that these can be computed or estimated without greater difficulties and apply our method to reprove the following known results in an easy and natural way. (i) The precise run time of the (1+1) EA on LeadingOnes. (ii) A lower bound for the run time of the (1+1) EA on OneMax, tight apart from an O(n) term. (iii) A lower bound for the run time of the (1+1) EA on long k-paths.
@inproceedings{doerr2021lower, abstract = {One of the first and easy to use techniques for proving run time bounds for evolutionary algorithms is the so-called method of fitness levels by Wegener. It uses a partition of the search space into a sequence of levels which are traversed by the algorithm in increasing order, possibly skipping levels. An easy, but often strong upper bound for the run time can then be derived by adding the reciprocals of the probabilities to leave the levels (or upper bounds for these). Unfortunately, a similarly effective method for proving lower bounds has not yet been established. The strongest such method, proposed by Sudholt (2013), requires a careful choice of the viscosity parameters gamma. In this paper we present two new variants of the method, one for upper and one for lower bounds. Besides the level leaving probabilities, they only rely on the probabilities that levels are visited at all. We show that these can be computed or estimated without greater difficulties and apply our method to reprove the following known results in an easy and natural way. (i) The precise run time of the (1+1) EA on LeadingOnes. (ii) A lower bound for the run time of the (1+1) EA on OneMax, tight apart from an O(n) term. (iii) A lower bound for the run time of the (1+1) EA on long k-paths.}, author = {Doerr, Benjamin and Kötzing, Timo}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {benjamindoerr gecco timokoetzing year2021}, title = {Lower Bounds from Fitness Levels Made Easy}, year = 2021 }

Böther, Maximilian; Schiller, Leon; Fischbeck, Philipp; Molitor, Louise; Krejca, Martin S.; Friedrich, Tobias Evolutionary Minimization of Traffic Congestion. Genetic and Evolutionary Computation Conference (GECCO) 2021: 937–945
Best Paper Award (RWA Track)
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Traffic congestion is a major issue that can be solved by suggesting drivers alternative routes they are willing to take. This concept has been formalized as a strategic routing problem in which a single alternative route is suggested to an existing one. We extend this formalization and introduce the Multiple-Routes problem, which is given a start and a destination and then aims at finding up to \(n\) different routes that the drivers strategically disperse over, minimizing the overall travel time of the system. Due to the NP-hard nature of the problem, we introduce the Multiple-Routes evolutionary algorithm (MREA) as a heuristic solver. We study several mutation and crossover operators and evaluate them on real-world data of the city of Berlin, Germany. We find that a combination of all operators yields the best result, improving the overall travel time by a factor between 1.8 and 3, in the median, compared to all drivers taking the fastest route. For the base case \(n=2\), we compare our MREA to the highly tailored optimal solver by Bläsius etal. [ATMOS 2020] and show that, in the median, our approach finds solutions of quality at least \(99.69\%\) of an optimal solution while only requiring \(40\%\) of the time.
@inproceedings{boether2021evolutionary, abstract = {Traffic congestion is a major issue that can be solved by suggesting drivers alternative routes they are willing to take. This concept has been formalized as a strategic routing problem in which a single alternative route is suggested to an existing one. We extend this formalization and introduce the Multiple-Routes problem, which is given a start and a destination and then aims at finding up to \(n\) different routes that the drivers strategically disperse over, minimizing the overall travel time of the system. Due to the NP-hard nature of the problem, we introduce the Multiple-Routes evolutionary algorithm (MREA) as a heuristic solver. We study several mutation and crossover operators and evaluate them on real-world data of the city of Berlin, Germany. We find that a combination of all operators yields the best result, improving the overall travel time by a factor between 1.8 and 3, in the median, compared to all drivers taking the fastest route. For the base case \(n=2\), we compare our MREA to the highly tailored optimal solver by Bläsius etal. [ATMOS 2020] and show that, in the median, our approach finds solutions of quality at least \(99.69\%\) of an optimal solution while only requiring \(40\%\) of the time.}, author = {Böther, Maximilian and Schiller, Leon and Fischbeck, Philipp and Molitor, Louise and Krejca, Martin S. and Friedrich, Tobias}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco leonschiller louisemolitor martinskrejca maximilianboether philippfischbeck tobiasfriedrich year2021}, note = {Best Paper Award (RWA Track)}, pages = {937&ndash;945}, title = {Evolutionary Minimization of Traffic Congestion}, year = 2021 }

Friedrich, Tobias; Göbel, Andreas; Krejca, Martin; Pappik, Marcus A spectral independence view on hard spheres via block dynamics. International Colloquium on Automata, Languages and Programming (ICALP) 2021: 66:1–66:15
[ Abstract ] [ BibTeX ] [ DOI ]
 
The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand-canonical partition function of the hard-sphere model in \(d\) dimensions. Up to a fugacity of \( \lambda < \text{e}/2^d\), the runtime of our algorithm is polynomial in the volume of the system. This covers the entire known real-valued regime for the uniqueness of the Gibbs measure. Key to our approach is to define a discretization that closely approximates the partition function of the continuous model. This results in a discrete hard-core instance that is exponential in the size of the initial hard-sphere model. Our approximation bound follows directly from the correlation decay threshold of an infinite regular tree with degree equal to the maximum degree of our discretization. To cope with the exponential blow-up of the discrete instance we use clique dynamics, a Markov chain that was recently introduced in the setting of abstract polymer models. We prove rapid mixing of clique dynamics up to the tree threshold of the univariate hard-core model. This is achieved by relating clique dynamics to block dynamics and adapting the spectral expansion method, which was recently used to bound the mixing time of Glauber dynamics within the same parameter regime.
@inproceedings{fgkp-asivohsvbd-2021, abstract = {The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand-canonical partition function of the hard-sphere model in \(d\) dimensions. Up to a fugacity of \( \lambda < \text{e}/2^d\), the runtime of our algorithm is polynomial in the volume of the system. This covers the entire known real-valued regime for the uniqueness of the Gibbs measure. Key to our approach is to define a discretization that closely approximates the partition function of the continuous model. This results in a discrete hard-core instance that is exponential in the size of the initial hard-sphere model. Our approximation bound follows directly from the correlation decay threshold of an infinite regular tree with degree equal to the maximum degree of our discretization. To cope with the exponential blow-up of the discrete instance we use clique dynamics, a Markov chain that was recently introduced in the setting of abstract polymer models. We prove rapid mixing of clique dynamics up to the tree threshold of the univariate hard-core model. This is achieved by relating clique dynamics to block dynamics and adapting the spectral expansion method, which was recently used to bound the mixing time of Glauber dynamics within the same parameter regime.}, author = {Friedrich, Tobias and Göbel, Andreas and Krejca, Martin and Pappik, Marcus}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {andreasgoebel icalp marcuspappik martinskrejca tobiasfriedrich year2021}, pages = {66:1-66:15}, title = {A spectral independence view on hard spheres via block dynamics}, volume = 198, year = 2021 }

Lagodzinski, J. A. Gregor; Göbel, Andreas; Casel, Katrin; Friedrich, Tobias On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order. International Colloquium on Automata, Languages and Programming (ICALP) 2021: 91:1–91:15
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study the problem of counting the number of homomorphisms from an input graph \(G\) to a fixed (quantum) graph \(\bar{H}\) in any finite field of prime order \(\mathbb{Z}_p\). The subproblem with graph \(H\) was introduced by Faben and Jerrum [ToC'15] and its complexity is still uncharacterised despite active research, e.g. the very recent work of Focke, Goldberg, Roth, and Zivný [SODA'21]. Our contribution is threefold. First, we introduce the study of quantum graphs to the study of modular counting homomorphisms. We show that the complexity for a quantum graph \(\bar{H}\) collapses to the complexity criteria found at dimension 1: graphs. Second, in order to prove cases of intractability we establish a further reduction to the study of bipartite graphs. Lastly, we establish a dichotomy for all bipartite \((K_{3,3}\backslash\{e\},\, {domino})\)-free graphs by a thorough structural study incorporating both local and global arguments. This result subsumes all results on bipartite graphs known for all prime moduli and extends them significantly. Even for the subproblem with \(p=2\) this establishes new results.
@inproceedings{lagodzinski2021counting, abstract = {We study the problem of counting the number of homomorphisms from an input graph \(G\) to a fixed (quantum) graph \(\bar{H}\) in any finite field of prime order \(\mathbb{Z}_p\). The subproblem with graph \(H\) was introduced by Faben and Jerrum [ToC'15] and its complexity is still uncharacterised despite active research, e.g. the very recent work of Focke, Goldberg, Roth, and Zivný [SODA'21]. Our contribution is threefold. First, we introduce the study of quantum graphs to the study of modular counting homomorphisms. We show that the complexity for a quantum graph \(\bar{H}\) collapses to the complexity criteria found at dimension 1: graphs. Second, in order to prove cases of intractability we establish a further reduction to the study of bipartite graphs. Lastly, we establish a dichotomy for all bipartite \((K_{3,3}\backslash\{e\},\, {domino})\)-free graphs by a thorough structural study incorporating both local and global arguments. This result subsumes all results on bipartite graphs known for all prime moduli and extends them significantly. Even for the subproblem with \(p=2\) this establishes new results.}, author = {Lagodzinski, J. A. Gregor and Göbel, Andreas and Casel, Katrin and Friedrich, Tobias}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, keywords = {andreasgoebel gregorlagodzinski icalp katrincasel tobiasfriedrich year2021}, pages = {91:1&ndash;91:15}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{{ü}}r Informatik}, series = {LIPIcs}, title = {On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order}, volume = 198, year = 2021 }

Casel, Katrin; Schmid, Markus L. Fine-Grained Complexity of Regular Path Queries. International Conference on Database Theory (ICDT) 2021
[ Abstract ] [ BibTeX ] [ Download ]
 
A regular path query (RPQ) is a regular expression \(q\) that returns all node pairs \((u, v)\) from a graph database that are connected by an arbitrary path labelled with a word from \(L(q)\). The obvious algorithmic approach to RPQ-evaluation (called PG-approach), i.e., constructing the product graph between an NFA for \(q\) and the graph database, is appealing due to its simplicity and also leads to efficient algorithms. However, it is unclear whether the PG-approach is optimal. We address this question by thoroughly investigating which upper complexity bounds can be achieved by the PG-approach, and we complement these with conditional lower bounds (in the sense of the fine-grained complexity framework). A special focus is put on enumeration and delay bounds, as well as the data complexity perspective. A main insight is that we can achieve optimal (or near optimal) algorithms with the PG-approach, but the delay for enumeration is rather high (linear in the database). We explore three successful approaches towards enumeration with sub-linear delay: super-linear preprocessing, approximations of the solution sets, and restricted classes of RPQs.
@inproceedings{casel2021finegrained, abstract = {A regular path query (RPQ) is a regular expression \(q\) that returns all node pairs \((u, v)\) from a graph database that are connected by an arbitrary path labelled with a word from \(L(q)\). The obvious algorithmic approach to RPQ-evaluation (called PG-approach), i.e., constructing the product graph between an NFA for \(q\) and the graph database, is appealing due to its simplicity and also leads to efficient algorithms. However, it is unclear whether the PG-approach is optimal. We address this question by thoroughly investigating which upper complexity bounds can be achieved by the PG-approach, and we complement these with conditional lower bounds (in the sense of the fine-grained complexity framework). A special focus is put on enumeration and delay bounds, as well as the data complexity perspective. A main insight is that we can achieve optimal (or near optimal) algorithms with the PG-approach, but the delay for enumeration is rather high (linear in the database). We explore three successful approaches towards enumeration with sub-linear delay: super-linear preprocessing, approximations of the solution sets, and restricted classes of RPQs.}, author = {Casel, Katrin and Schmid, Markus L.}, booktitle = {International Conference on Database Theory (ICDT)}, keywords = {icdt katrincasel markuslschmid year2021}, title = {Fine-Grained Complexity of Regular Path Queries}, year = 2021 }

Krogmann, Simon; Lenzner, Pascal; Molitor, Louise; Skopalik, Alexander Two-Stage Facility Location Games with Strategic Clients and Facilities. International Joint Conference on Artificial Intelligence (IJCAI) 2021
[ Abstract ] [ BibTeX ] [ Download ]
 
We consider non-cooperative facility location games where both facilities and clients act strategically and heavily influence each other. This contrasts established game-theoretic facility location models with non-strategic clients that simply select the closest opened facility. In our model, every facility location has a set of attracted clients and each client has a set of shopping locations and a weight that corresponds to her spending capacity. Facility agents selfishly select a location for opening their facility to maximize the attracted total spending capacity, whereas clients strategically decide how to distribute their spending capacity among the opened facilities in their shopping range. We focus on a natural client behavior similar to classical load balancing: our selfish clients aim for a distribution that minimizes their maximum waiting times for getting serviced, where a facility’s waiting time corresponds to its total attracted client weight. We show that subgame perfect equilibria exist and give almost tight constant bounds on the Price of Anarchy and the Price of Stability, which even hold for a broader class of games with arbitrary client behavior. Since facilities and clients influence each other, it is crucial for the facilities to anticipate the selfish clients’ behavior when selecting their location. For this, we provide an efficient algorithm that also implies an efficient check for equilibrium. Finally, we show that computing a socially optimal facility placement is NP-hard and that this result holds for all feasible client weight distributions.
@inproceedings{krogmann2021twostage, abstract = {We consider non-cooperative facility location games where both facilities and clients act strategically and heavily influence each other. This contrasts established game-theoretic facility location models with non-strategic clients that simply select the closest opened facility. In our model, every facility location has a set of attracted clients and each client has a set of shopping locations and a weight that corresponds to her spending capacity. Facility agents selfishly select a location for opening their facility to maximize the attracted total spending capacity, whereas clients strategically decide how to distribute their spending capacity among the opened facilities in their shopping range. We focus on a natural client behavior similar to classical load balancing: our selfish clients aim for a distribution that minimizes their maximum waiting times for getting serviced, where a facility’s waiting time corresponds to its total attracted client weight. We show that subgame perfect equilibria exist and give almost tight constant bounds on the Price of Anarchy and the Price of Stability, which even hold for a broader class of games with arbitrary client behavior. Since facilities and clients influence each other, it is crucial for the facilities to anticipate the selfish clients’ behavior when selecting their location. For this, we provide an efficient algorithm that also implies an efficient check for equilibrium. Finally, we show that computing a socially optimal facility placement is NP-hard and that this result holds for all feasible client weight distributions.}, author = {Krogmann, Simon and Lenzner, Pascal and Molitor, Louise and Skopalik, Alexander}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {ijcai louisemolitor pascallenzner simonkrogmann year2021}, title = {Two-Stage Facility Location Games with Strategic Clients and Facilities}, year = 2021 }

Casel, Katrin; Friedrich, Tobias; Issac, Davis; Klodt, Nicolas; Seifert, Lars; Zahn, Arthur A Color-blind 3-Approximation for Chromatic Correlation Clustering and Improved Heuristics. Knowledge Discovery and Data Mining (KDD) 2021
[ Abstract ] [ BibTeX ]
 
Chromatic Correlation Clustering (CCC) models clustering of objects with categorical pairwise relationships. The model can be viewed as clustering the vertices of a graph with edge-labels (colors). Bonchi et al. [KDD 2012] introduced it as a natural generalization of the well studied problem Correlation Clustering (CC), motivated by real-world applications from data-mining, social networks and bioinformatics. We give theoretical as well as practical contributions to the study of CCC. Our main theoretical contribution is an alternative analysis of the famous Pivot algorithm for CC. We show that, when simply run color-blind, Pivot is also a linear time 3-approximation for CCC. The previous best theoretical results for CCC were a 4-approximation with a high-degree polynomial runtime and a linear time 11-approximation, both by Anava et al. [WWW 2015]. While this theoretical result justifies Pivot as a baseline comparison for other heuristics, its blunt color-blindness performs poorly in practice. We develop a color-sensitive, practical heuristic we call Greedy Expansion that empirically outperforms all heuristics proposed for CCC so far, both on real-world and synthetic instances. Further, we propose a novel generalization of CCC allowing for multi-labelled edges. We argue that it is more suitable for many of the real-world applications and extend our results to this model.
@inproceedings{casel2021colorblind, abstract = {Chromatic Correlation Clustering (CCC) models clustering of objects with categorical pairwise relationships. The model can be viewed as clustering the vertices of a graph with edge-labels (colors). Bonchi et al. [KDD 2012] introduced it as a natural generalization of the well studied problem Correlation Clustering (CC), motivated by real-world applications from data-mining, social networks and bioinformatics. We give theoretical as well as practical contributions to the study of CCC. Our main theoretical contribution is an alternative analysis of the famous Pivot algorithm for CC. We show that, when simply run color-blind, Pivot is also a linear time 3-approximation for CCC. The previous best theoretical results for CCC were a 4-approximation with a high-degree polynomial runtime and a linear time 11-approximation, both by Anava et al. [WWW 2015]. While this theoretical result justifies Pivot as a baseline comparison for other heuristics, its blunt color-blindness performs poorly in practice. We develop a color-sensitive, practical heuristic we call Greedy Expansion that empirically outperforms all heuristics proposed for CCC so far, both on real-world and synthetic instances. Further, we propose a novel generalization of CCC allowing for multi-labelled edges. We argue that it is more suitable for many of the real-world applications and extend our results to this model.}, author = {Casel, Katrin and Friedrich, Tobias and Issac, Davis and Klodt, Nicolas and Seifert, Lars and Zahn, Arthur}, booktitle = {Knowledge Discovery and Data Mining (KDD)}, keywords = {sys:relevantfor:ae arthurzahn davisissac katrincasel kdd larsseifert nicolasklodt tobiasfriedrich year2021}, title = {A Color-blind 3-Approximation for Chromatic Correlation Clustering and Improved Heuristics}, year = 2021 }

Bilò, Davide; Cohen, Sarel; Friedrich, Tobias; Schirneck, Martin Space-Efficient Fault-Tolerant Diameter Oracles. Mathematical Foundations of Computer Science (MFCS) 2021
[ Abstract ] [ BibTeX ]
 
We design \(f\)-edge fault-tolerant diameter oracles (\(f\)-FDO, or simply FDO if \(f=1\)). For a given directed or undirected and possibly edge-weighted graph \(G\) with \(n\) vertices and \(m\) edges and a positive integer \(f\), we preprocess the graph and construct a data structure that, when queried with a set \(F\) of edges, where \(|F| \leq f\), returns the diameter of \(G - F\). An \(f\)-FDO has stretch \(\sigma \geq 1\) if the returned value \(\widehat D\) satisfies \(\operatorname{diam}(G - F) leq widehat D leq sigma \operatorname{diam}(G - F)\). For the case of a single edge failure (\(f=1\)) in an unweighted directed graph, there exists an approximate FDO by Henzinger et al. [ITCS 2017] with stretch \((1+\varepsilon)\), constant query time, space \(O(m)\), and a combinatorial preprocessing time of \(\widetilde{O}(mn + n^{1.5} \sqrt{Dm/\varepsilon})\), where \(D\) is the diameter. We present a near-optimal FDO with the same stretch, query time, and space. It has a preprocessing time of \(\widetilde{O}(mn + n^2/\varepsilon)\), which is better for any constant \(\varepsilon > 0\). The preprocessing time nearly matches a conditional lower bound for combinatorial algorithms, also by Henzinger et al. When using fast matrix multiplication instead, we achieve a preprocessing time of \(\widetilde{O}(n^{2.5794} + n^2/\varepsilon)\). We further prove an information-theoretic lower bound showing that any FDO with stretch better than \(3/2\) requires \(\Omega(m)\) bits of space. Thus, for constant \(0 < \varepsilon < 3/2\), our combinatorial \((1+ \varepsilon)\)-approximate FDO is near-optimal in all the parameters. In the case of multiple edge failures (\(f>1\)) in undirected graphs with non-negative edge weights, we give an \(f\)-FDO with stretch \((f+2)\), query time \(O(f^2\log^2{n})\), \(\widetilde{O}(fn)\) space, and preprocessing time \(\widetilde{O}(fm)\). We complement this with a lower bound excluding any finite stretch in \(o(fn)\) space. Many real-world networks have polylogarithmic diameter. We show that for those graphs and up to \(f = o(\log n/ \log\log n)\) failures one can swap approximation for query time and space. We present an exact combinatorial \(f\)-FDO with preprocessing time \(mn^{1+o(1)}\), query time \(n^{o(1)}\), and space \(n^{2+o(1)}\). With fast matrix multiplication, the preprocessing time can be improved to \(n^{\omega+o(1)}\), where \(\omega < 2.373\) is the matrix multiplication exponent.
@inproceedings{bilo2021spaceefficient, abstract = {We design \(f\)-edge fault-tolerant diameter oracles (\(f\)-FDO, or simply FDO if \(f=1\)). For a given directed or undirected and possibly edge-weighted graph \(G\) with \(n\) vertices and \(m\) edges and a positive integer \(f\), we preprocess the graph and construct a data structure that, when queried with a set \(F\) of edges, where \(|F| \leq f\), returns the diameter of \(G - F\). An \(f\)-FDO has stretch \(\sigma \geq 1\) if the returned value \(\widehat D\) satisfies \(\operatorname{diam}(G - F) leq widehat D leq sigma \operatorname{diam}(G - F)\). For the case of a single edge failure (\(f=1\)) in an unweighted directed graph, there exists an approximate FDO by Henzinger et al. [ITCS 2017] with stretch \((1+\varepsilon)\), constant query time, space \(O(m)\), and a combinatorial preprocessing time of \(\widetilde{O}(mn + n^{1.5} \sqrt{Dm/\varepsilon})\), where \(D\) is the diameter. We present a near-optimal FDO with the same stretch, query time, and space. It has a preprocessing time of \(\widetilde{O}(mn + n^2/\varepsilon)\), which is better for any constant \(\varepsilon > 0\). The preprocessing time nearly matches a conditional lower bound for combinatorial algorithms, also by Henzinger et al. When using fast matrix multiplication instead, we achieve a preprocessing time of \(\widetilde{O}(n^{2.5794} + n^2/\varepsilon)\). We further prove an information-theoretic lower bound showing that any FDO with stretch better than \(3/2\) requires \(\Omega(m)\) bits of space. Thus, for constant \(0 < \varepsilon < 3/2\), our combinatorial \((1+ \varepsilon)\)-approximate FDO is near-optimal in all the parameters. In the case of multiple edge failures (\(f>1\)) in undirected graphs with non-negative edge weights, we give an \(f\)-FDO with stretch \((f+2)\), query time \(O(f^2\log^2{n})\), \(\widetilde{O}(fn)\) space, and preprocessing time \(\widetilde{O}(fm)\). We complement this with a lower bound excluding any finite stretch in \(o(fn)\) space. Many real-world networks have polylogarithmic diameter. We show that for those graphs and up to \(f = o(\log n/ \log\log n)\) failures one can swap approximation for query time and space. We present an exact combinatorial \(f\)-FDO with preprocessing time \(mn^{1+o(1)}\), query time \(n^{o(1)}\), and space \(n^{2+o(1)}\). With fast matrix multiplication, the preprocessing time can be improved to \(n^{\omega+o(1)}\), where \(\omega < 2.373\) is the matrix multiplication exponent.}, author = {Bilò, Davide and Cohen, Sarel and Friedrich, Tobias and Schirneck, Martin}, booktitle = {Mathematical Foundations of Computer Science (MFCS)}, keywords = {davidebilo martinschirneck mfcs sarelcohen tobiasfriedrich year2021}, title = {Space-Efficient Fault-Tolerant Diameter Oracles}, year = 2021 }

Kißig, Otto; Taraz, Martin; Cohen, Sarel; Doskoč, Vanja; Friedrich, Tobias Drug Repurposing for Multiple COVID Strains using Collaborative Filtering. ICLR Workshop on Machine Learning for Preventing and Combating Pandemics (MLPCP@ICLR) 2021
[ BibTeX ] [ Download ]
 
@inproceedings{kissig2021repurposing, author = {Kißig, Otto and Taraz, Martin and Cohen, Sarel and Doskoč, Vanja and Friedrich, Tobias}, booktitle = {ICLR Workshop on Machine Learning for Preventing and Combating Pandemics (MLPCP@ICLR)}, keywords = {martintaraz mlpcp@iclr ottokissig sarelcohen tobiasfriedrich vanjadoskoc year2021}, title = {Drug Repurposing for Multiple COVID Strains using Collaborative Filtering}, year = 2021 }

Friedrich, Tobias; Neumann, Frank; Rothenberger, Ralf; Sutton, Andrew M. Solving Non-Uniform Planted and Filtered Random SAT Formulas Greedily. Theory and Applications of Satisfiability Testing (SAT) 2021
[ Abstract ] [ BibTeX ]
 
Recently, there has been an interest in studying non-uniform random \(k\)-satisfiability (\(k\)-SAT) models in order to address the non-uniformity of formulas arising from real-world applications. While uniform random \(k\)-SAT has been extensively studied from both a theoretical and experimental perspective, understanding the algorithmic complexity of heterogeneous distributions is still an open challenge. When a sufficiently dense formula is guaranteed to be satisfiable by conditioning or a planted assignment, it is well-known that uniform random \(k\)-SAT is easy on average. We generalize this result to the broad class of non-uniform random \(k\)-SAT models that are characterized only by an ensemble of distributions over variables with a mild balancing condition. This balancing condition rules out extremely skewed distributions in which nearly half the variables occur less frequently than a small constant fraction of the most frequent variables, but generalizes recently studied non-uniform \(k\)-SAT distributions such as power-law and geometric formulas. We show that for all formulas generated from this model of at least logarithmic densities, a simple greedy algorithm can find a solution with high probability. As a side result we show that the total variation distance between planted and filtered (conditioned on satisfiability) models is \(o(1)\) once the planted model produces formulas with a unique solution with probability \(1-o(1)\). This holds for all random \(k\)-SAT models where the signs of variables are drawn uniformly and independently at random.
@inproceedings{rothenberger2021solving, abstract = {Recently, there has been an interest in studying non-uniform random \(k\)-satisfiability (\(k\)-SAT) models in order to address the non-uniformity of formulas arising from real-world applications. While uniform random \(k\)-SAT has been extensively studied from both a theoretical and experimental perspective, understanding the algorithmic complexity of heterogeneous distributions is still an open challenge. When a sufficiently dense formula is guaranteed to be satisfiable by conditioning or a planted assignment, it is well-known that uniform random \(k\)-SAT is easy on average. We generalize this result to the broad class of non-uniform random \(k\)-SAT models that are characterized only by an ensemble of distributions over variables with a mild balancing condition. This balancing condition rules out extremely skewed distributions in which nearly half the variables occur less frequently than a small constant fraction of the most frequent variables, but generalizes recently studied non-uniform \(k\)-SAT distributions such as power-law and geometric formulas. We show that for all formulas generated from this model of at least logarithmic densities, a simple greedy algorithm can find a solution with high probability. As a side result we show that the total variation distance between planted and filtered (conditioned on satisfiability) models is \(o(1)\) once the planted model produces formulas with a unique solution with probability \(1-o(1)\). This holds for all random \(k\)-SAT models where the signs of variables are drawn uniformly and independently at random.}, author = {Friedrich, Tobias and Neumann, Frank and Rothenberger, Ralf and Sutton, Andrew M.}, booktitle = {Theory and Applications of Satisfiability Testing (SAT)}, keywords = {andrewmsutton frankneumann ralfrothenberger sat tobiasfriedrich year2021}, title = {Solving Non-Uniform Planted and Filtered Random SAT Formulas Greedily}, year = 2021 }

Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian Force-Directed Embedding of Scale-Free Networks in the Hyperbolic Plane. Symposium on Experimental Algorithms (SEA) 2021: 22:1–22:18
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Force-directed drawing algorithms are the most commonly used approach to visualize networks. While they are usually very robust, the performance of Euclidean spring embedders decreases if the graph exhibits the high level of heterogeneity that typically occurs in scale-free real-world networks. As heterogeneity naturally emerges from hyperbolic geometry (in fact, scale-free networks are often perceived to have an underlying hyperbolic geometry), it is natural to embed them into the hyperbolic plane instead. Previous techniques that produce hyperbolic embeddings usually make assumptions about the given network, which (if not met) impairs the quality of the embedding. It is still an open problem to adapt force-directed embedding algorithms to make use of the heterogeneity of the hyperbolic plane, while also preserving their robustness. We identify fundamental differences between the behavior of spring embedders in Euclidean and hyperbolic space, and adapt the technique to take advantage of the heterogeneity of the hyperbolic plane.
@inproceedings{bfk-fdesfnhp-2021, abstract = {Force-directed drawing algorithms are the most commonly used approach to visualize networks. While they are usually very robust, the performance of Euclidean spring embedders decreases if the graph exhibits the high level of heterogeneity that typically occurs in scale-free real-world networks. As heterogeneity naturally emerges from hyperbolic geometry (in fact, scale-free networks are often perceived to have an underlying hyperbolic geometry), it is natural to embed them into the hyperbolic plane instead. Previous techniques that produce hyperbolic embeddings usually make assumptions about the given network, which (if not met) impairs the quality of the embedding. It is still an open problem to adapt force-directed embedding algorithms to make use of the heterogeneity of the hyperbolic plane, while also preserving their robustness. We identify fundamental differences between the behavior of spring embedders in Euclidean and hyperbolic space, and adapt the technique to take advantage of the heterogeneity of the hyperbolic plane.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian}, booktitle = {Symposium on Experimental Algorithms (SEA)}, keywords = {maximiliankatzmann sea thomasblaesius tobiasfriedrich year2021}, pages = {22:1-22:18}, title = {Force-Directed Embedding of Scale-Free Networks in the Hyperbolic Plane}, year = 2021 }

Bläsius, Thomas; Friedrich, Tobias; Göbel, Andreas; Levy, Jordi; Rothenberger, Ralf The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability. Symposium on Discrete Algorithms (SODA) 2021: 42–53
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Satisfiability is considered the canonical NP-complete problem and is used as a starting point for hardness reductions in theory, while in practice heuristic SAT solving algorithms can solve large-scale industrial SAT instances very efficiently. This disparity between theory and practice is believed to be a result of inherent properties of industrial SAT instances that make them tractable. Two characteristic properties seem to be prevalent in the majority of real-world SAT instances, heterogeneous degree distribution and locality. To understand the impact of these two properties on SAT, we study the proof complexity of random k-SAT models that allow to control heterogeneity and locality. Our findings show that heterogeneity alone does not make SAT easy as heterogeneous random k-SAT instances have superpolynomial resolution size. This implies intractability of these instances for modern SAT-solvers. On the other hand, modeling locality with an underlying geometry leads to small unsatisfiable subformulas, which can be found within polynomial time. A key ingredient for the result on geometric random k-SAT can be found in the complexity of higher-order Voronoi diagrams. As an additional technical contribution, we show an upper bound on the number of non-empty Voronoi regions, that holds for points with random positions in a very general setting. In particular, it covers arbitrary p-norms, higher dimensions, and weights affecting the area of influence of each point multiplicatively. Our bound is linear in the total weight. This is in stark contrast to quadratic lower bounds for the worst case.
@inproceedings{blasius2021impact, abstract = {Satisfiability is considered the canonical NP-complete problem and is used as a starting point for hardness reductions in theory, while in practice heuristic SAT solving algorithms can solve large-scale industrial SAT instances very efficiently. This disparity between theory and practice is believed to be a result of inherent properties of industrial SAT instances that make them tractable. Two characteristic properties seem to be prevalent in the majority of real-world SAT instances, heterogeneous degree distribution and locality. To understand the impact of these two properties on SAT, we study the proof complexity of random k-SAT models that allow to control heterogeneity and locality. Our findings show that heterogeneity alone does not make SAT easy as heterogeneous random k-SAT instances have superpolynomial resolution size. This implies intractability of these instances for modern SAT-solvers. On the other hand, modeling locality with an underlying geometry leads to small unsatisfiable subformulas, which can be found within polynomial time. A key ingredient for the result on geometric random k-SAT can be found in the complexity of higher-order Voronoi diagrams. As an additional technical contribution, we show an upper bound on the number of non-empty Voronoi regions, that holds for points with random positions in a very general setting. In particular, it covers arbitrary p-norms, higher dimensions, and weights affecting the area of influence of each point multiplicatively. Our bound is linear in the total weight. This is in stark contrast to quadratic lower bounds for the worst case.}, author = {Bläsius, Thomas and Friedrich, Tobias and Göbel, Andreas and Levy, Jordi and Rothenberger, Ralf}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {andreasgoebel jordilevy ralfrothenberger soda thomasblaesius tobiasfriedrich year2021}, pages = {42-53}, publisher = {SIAM}, title = {The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability}, year = 2021 }

Friedemann, Wilhelm; Friedrich, Tobias; Gawendowicz, Hans; Lenzner, Pascal; Melnichenko, Anna; Peters, Jannik; Stephan, Daniel; Vaichenker, Michael Efficiency and Stability in Euclidean Network Design. Symposium on Parallelism in Algorithms and Architectures (SPAA) 2021: 232–242
[ BibTeX ] [ DOI ] [ Download ]
 
@inproceedings{friedemann2021efficiency, author = {Friedemann, Wilhelm and Friedrich, Tobias and Gawendowicz, Hans and Lenzner, Pascal and Melnichenko, Anna and Peters, Jannik and Stephan, Daniel and Vaichenker, Michael}, booktitle = {Symposium on Parallelism in Algorithms and Architectures (SPAA)}, keywords = {annamelnichenko pascallenzner spaa tobiasfriedrich year2021}, pages = {232&ndash;242}, publisher = {ASM}, title = {Efficiency and Stability in Euclidean Network Design}, year = 2021 }

2021

Cseh, Ágnes; Juhos, Attila Pairwise Preferences in the Stable Marriage Problem. ACM Transactions on Economics and Computation (TEAC) 2021: 1–28
[ BibTeX ] [ Download ]
 
@article{cseh2021pairwise, author = {Cseh, Ágnes and Juhos, Attila}, journal = {ACM Transactions on Economics and Computation (TEAC)}, keywords = {sys:relevantfor:ae agnescseh}, number = 1, pages = {1&ndash;28}, publisher = {ACM New York, NY, USA}, title = {Pairwise Preferences in the Stable Marriage Problem}, volume = 9, year = 2021 }

Cseh, Ágnes; Kavitha, Telikepalli Popular matchings in complete graphs. Algorithmica 2021: 1–31
[ BibTeX ] [ URL ]
 
@article{cseh2021popular, author = {Cseh, Ágnes and Kavitha, Telikepalli}, journal = {Algorithmica}, keywords = {sys:relevantfor:ae agnescseh}, pages = {1&ndash;31}, publisher = {Springer}, title = {Popular matchings in complete graphs}, year = 2021 }

Andersson, Tommy; Cseh, Ágnes; Ehlers, Lars; Erlanson, Albin Organizing time exchanges: Lessons from matching markets. American Economic Journal: Microeconomics 2021: 338–73
[ BibTeX ] [ Download ]
 
@article{andersson2021organizing, author = {Andersson, Tommy and Cseh, Ágnes and Ehlers, Lars and Erlanson, Albin}, journal = {American Economic Journal: Microeconomics}, keywords = {sys:relevantfor:ae agnescseh}, number = 1, pages = {338&ndash;73}, title = {Organizing time exchanges: Lessons from matching markets}, volume = 13, year = 2021 }

Doerr, Benjamin; Krejca, Martin S. A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes. Theoretical Computer Science 2021: 121–128
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
With elementary means, we prove in this note a stronger run time guarantee for the univariate marginal distribution algorithm (UMDA) optimizing the LeadingOnes benchmark function in the desirable regime with low genetic drift. If the population size \(\mu\) is at least \(128 n \ln(n)\) and the selection rate \(\mu/\lambda\) is at most some constant less than \(\frac{1}{4e \approx 0.092\), then the UMDA samples the optimum within \(O\big(n\frac{\lambda}{log (\lambda/\mu)}\big)\) fitness evaluations with high probability. This improves over the previous \(O(n \lambda \log\lambda)\) guarantee that was obtained by Dang and Lehre (2015) via the deep level-based population method. With similar arguments as in our upper-bound analysis, we also obtain the first lower bound for this problem. Under similar assumptions, we prove that a bound of \(\Omega\big(lambda \frac{n - \log(n\lambda)}log (\lambda / \mu)}\big)\) fitness evaluations holds with high probability.
@article{doerr2021simplified, abstract = {With elementary means, we prove in this note a stronger run time guarantee for the univariate marginal distribution algorithm (UMDA) optimizing the LeadingOnes benchmark function in the desirable regime with low genetic drift. If the population size \(\mu\) is at least \(128 n \ln(n)\) and the selection rate \(\mu/\lambda\) is at most some constant less than \(\frac{1}{4e \approx 0.092\), then the UMDA samples the optimum within \(O\big(n\frac{\lambda}{log (\lambda/\mu)}\big)\) fitness evaluations with high probability. This improves over the previous \(O(n \lambda \log\lambda)\) guarantee that was obtained by Dang and Lehre (2015) via the deep level-based population method. With similar arguments as in our upper-bound analysis, we also obtain the first lower bound for this problem. Under similar assumptions, we prove that a bound of \(\Omega\big(lambda \frac{n - \log(n\lambda)}log (\lambda / \mu)}\big)\) fitness evaluations holds with high probability.}, author = {Doerr, Benjamin and Krejca, Martin S.}, journal = {Theoretical Computer Science}, keywords = {benjamindoerr martinskrejca tcs year2021}, pages = {121-128}, title = {A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes}, volume = 851, year = 2021 }

Casel, Katrin; Fernau, Henning; Gaspers, Serge; Gras, Benjamin; Schmid, Markus L. On the Complexity of the Smallest Grammar Problem over Fixed Alphabets. Theory of Computing Systems 2021: 344–409
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In the smallest grammar problem, we are given a word \(w\)and we want to compute a preferably small context-free grammar \(G\) for the singleton language \(\{w\}\) (where the size of a grammar is the sum of the sizes of its rules, and the size of a rule is measured by the length of its right side). It is known that, for unbounded alphabets, the decision variant of this problem is \(\mathsf{NP}\)-hard and the optimisation variant does not allow a polynomial-time approximation scheme, unless \(\mathsf{P}\) = \(\mathsf{NP}\). We settle the long-standing open problem whether these hardness results also hold for the more realistic case of a constant-size alphabet. More precisely, it is shown that the smallest grammar problem remains \(\mathsf{NP}\)-complete (and its optimisation version is \(\mathsf{APX}\)-hard), even if the alphabet is fixed and has size of at least 17. The corresponding reduction is robust in the sense that it also works for an alternative size-measure of grammars that is commonly used in the literature (i.e., a size measure also taking the number of rules into account), and it also allows to conclude that even computing the number of rules required by a smallest grammar is a hard problem. On the other hand, if the number of nonterminals (or, equivalently, the number of rules) is bounded by a constant, then the smallest grammar problem can be solved in polynomial time, which is shown by encoding it as a problem on graphs with interval structure. However, treating the number of rules as a parameter (in terms of parameterised complexity) yields \(\mathsf{W}\)[1]-hardness. Furthermore, we present an \(O(3^{|w|})\) exact exponential-time algorithm, based on dynamic programming. These three main questions are also investigated for 1-level grammars, i.e., grammars for which only the start rule contains nonterminals on the right side; thus, investigating the impact of the ``hierarchical depth'' of grammars on the complexity of the smallest grammar problem. In this regard, we obtain for 1-level grammars similar, but slightly stronger results.
@article{casel2020article, abstract = {In the smallest grammar problem, we are given a word \(w\)and we want to compute a preferably small context-free grammar \(G\) for the singleton language \(\{w\}\) (where the size of a grammar is the sum of the sizes of its rules, and the size of a rule is measured by the length of its right side). It is known that, for unbounded alphabets, the decision variant of this problem is \(\mathsf{NP}\)-hard and the optimisation variant does not allow a polynomial-time approximation scheme, unless \(\mathsf{P}\) = \(\mathsf{NP}\). We settle the long-standing open problem whether these hardness results also hold for the more realistic case of a constant-size alphabet. More precisely, it is shown that the smallest grammar problem remains \(\mathsf{NP}\)-complete (and its optimisation version is \(\mathsf{APX}\)-hard), even if the alphabet is fixed and has size of at least 17. The corresponding reduction is robust in the sense that it also works for an alternative size-measure of grammars that is commonly used in the literature (i.e., a size measure also taking the number of rules into account), and it also allows to conclude that even computing the number of rules required by a smallest grammar is a hard problem. On the other hand, if the number of nonterminals (or, equivalently, the number of rules) is bounded by a constant, then the smallest grammar problem can be solved in polynomial time, which is shown by encoding it as a problem on graphs with interval structure. However, treating the number of rules as a parameter (in terms of parameterised complexity) yields \(\mathsf{W}\)[1]-hardness. Furthermore, we present an \(O(3^{|w|})\) exact exponential-time algorithm, based on dynamic programming. These three main questions are also investigated for 1-level grammars, i.e., grammars for which only the start rule contains nonterminals on the right side; thus, investigating the impact of the ``hierarchical depth'' of grammars on the complexity of the smallest grammar problem. In this regard, we obtain for 1-level grammars similar, but slightly stronger results.}, author = {Casel, Katrin and Fernau, Henning and Gaspers, Serge and Gras, Benjamin and Schmid, Markus L.}, editor = {Springer}, journal = {Theory of Computing Systems}, keywords = {benjamingras henningfernau katrincasel markuslschmid sergegaspers tocs year2020}, number = 2, pages = {344–409}, title = {On the Complexity of the Smallest Grammar Problem over Fixed Alphabets}, volume = 65, year = 2021 }

Bläsius, Thomas; Friedrich, Tobias; Schirneck, Martin The Complexity of Dependency Detection and Discovery in Relational Databases. CoRR 2021
ArXiv preprint
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Multi-column dependencies in relational databases come associated with two different computational tasks. The detection problem is to decide whether a dependency of a certain type and size holds in a given database, the discovery problem asks to enumerate all valid dependencies of that type. We settle the complexity of both of these problems for unique column combinations (UCCs), functional dependencies (FDs), and inclusion dependencies (INDs). We show that the detection of UCCs and FDs is W[2]-complete when parameterized by the solution size. The discovery of inclusion-wise minimal UCCs is proven to be equivalent under parsimonious reductions to the transversal hypergraph problem of enumerating the minimal hitting sets of a hypergraph. The discovery of FDs is equivalent to the simultaneous enumeration of the hitting sets of multiple input hypergraphs. We further identify the detection of INDs as one of the first natural W[3]-complete problems. The discovery of maximal INDs is shown to be equivalent to enumerating the maximal satisfying assignments of antimonotone, 3-normalized Boolean formulas.
@article{blasius2021detectiondiscovery, abstract = {Multi-column dependencies in relational databases come associated with two different computational tasks. The detection problem is to decide whether a dependency of a certain type and size holds in a given database, the discovery problem asks to enumerate all valid dependencies of that type. We settle the complexity of both of these problems for unique column combinations (UCCs), functional dependencies (FDs), and inclusion dependencies (INDs). We show that the detection of UCCs and FDs is W[2]-complete when parameterized by the solution size. The discovery of inclusion-wise minimal UCCs is proven to be equivalent under parsimonious reductions to the transversal hypergraph problem of enumerating the minimal hitting sets of a hypergraph. The discovery of FDs is equivalent to the simultaneous enumeration of the hitting sets of multiple input hypergraphs. We further identify the detection of INDs as one of the first natural W[3]-complete problems. The discovery of maximal INDs is shown to be equivalent to enumerating the maximal satisfying assignments of antimonotone, 3-normalized Boolean formulas.}, author = {Bläsius, Thomas and Friedrich, Tobias and Schirneck, Martin}, journal = {CoRR}, keywords = {arxiv martinschirneck thomasblaesius tobiasfriedrich year2021}, note = {ArXiv preprint}, title = {The Complexity of Dependency Detection and Discovery in Relational Databases}, volume = {arXiv:2103.13331}, year = 2021 }