2022

Hacker, Philipp; Naumann, Felix; Friedrich, Tobias; Grundmann, Stefan; Lehmann, Anja AI Compliance - Challenges of Bridging Data Science and LawACM Journal of Data and Information Quality 2022
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
This vision paper outlines the main building blocks of what we term AI Compliance, an effort to bridge two complementary research areas: computer science and the law. Such research has the goal to model, measure, and affect the quality of AI artifacts, such as data, models and applications, to then facilitate adherence to legal standards.
@article{hacker2022compliance, abstract = {This vision paper outlines the main building blocks of what we term AI Compliance, an effort to bridge two complementary research areas: computer science and the law. Such research has the goal to model, measure, and affect the quality of AI artifacts, such as data, models and applications, to then facilitate adherence to legal standards.}, author = {Hacker, Philipp and Naumann, Felix and Friedrich, Tobias and Grundmann, Stefan and Lehmann, Anja}, journal = {ACM Journal of Data and Information Quality}, keywords = {myown tobiasfriedrich}, title = {AI Compliance - Challenges of Bridging Data Science and Law}, year = 2022 }

Bläsius, Thomas; Freiberger, Cedric; Friedrich, Tobias; Katzmann, Maximilian; Montenegro-Retana, Felix; Thieffry, Marianne Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic GeometryACM Transactions on Algorithms 2022: 1–32
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
A standard approach to accelerating shortest path algorithms on networks is the bidirectional search, which explores the graph from the start and the destination, simultaneously. In practice this strategy performs particularly well on scale-free real-world networks. Such networks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry. To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is \(\tilde{O}(n\)\(^{2 - 1/ \alpha}+\)\(n^{1/(2\alpha)}\)\(+ \delta_{\max})\) with high probability, where \(\alpha\)\(\in\)\((0.5, 1)\) controls the power-law exponent of the degree distribution, and \(\delta_{\max}\) is the maximum degree. This bound is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.
@article{blasius2022efficient, abstract = {A standard approach to accelerating shortest path algorithms on networks is the bidirectional search, which explores the graph from the start and the destination, simultaneously. In practice this strategy performs particularly well on scale-free real-world networks. Such networks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry. To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is \(\tilde{O}(n\)\(^{2 - 1/ \alpha}+\)\(n^{1/(2\alpha)}\)\(+ \delta_{\max})\) with high probability, where \(\alpha\)\(\in\)\((0.5, 1)\) controls the power-law exponent of the degree distribution, and \(\delta_{\max}\) is the maximum degree. This bound is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.}, author = {Bläsius, Thomas and Freiberger, Cedric and Friedrich, Tobias and Katzmann, Maximilian and Montenegro-Retana, Felix and Thieffry, Marianne}, journal = {ACM Transactions on Algorithms}, keywords = {sys:relevantfor:ae thomasblaesius tobiasfriedrich mariannethieffry cedricfreiberger maximiliankatzmann year2022 felixmontenegroretana}, pages = {1-32}, title = {Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry}, year = 2022 }

Bilò, Davide; Bilò, Vittorio; Lenzner, Pascal; Molitor, Louise Topological Influence and Locality in Swap Schelling GamesAutonomous Agents and Multi-Agent Systems (AGNT) 2022: 47
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Residential segregation is a wide-spread phenomenon that can be observed in almost every major city. In these urban areas residents with different racial or socioeconomic background tend to form homogeneous clusters. Schelling's famous agent-based model for residential segregation explains how such clusters can form even if all agents are tolerant, i.e., if they agree to live in mixed neighborhoods. For segregation to occur, all it needs is a slight bias towards agents preferring similar neighbors. Very recently, Schelling's model has been investigated from a game-theoretic point of view with selfish agents that strategically select their residential location. In these games, agents can improve on their current location by performing a location swap with another agent who is willing to swap. We significantly deepen these investigations by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy and on the dynamic properties of the resulting strategic multi-agent system. Moreover, as a new conceptual contribution, we also consider the influence of locality, i.e., if the location swaps are restricted to swaps of neighboring agents. We give improved almost tight bounds on the Price of Anarchy for arbitrary underlying graphs and we present (almost) tight bounds for regular graphs, paths and cycles. Moreover, we give almost tight bounds for grids, which are commonly used in empirical studies. For grids we also show that locality has a severe impact on the game dynamics.
@article{bilo2022topological, abstract = {Residential segregation is a wide-spread phenomenon that can be observed in almost every major city. In these urban areas residents with different racial or socioeconomic background tend to form homogeneous clusters. Schelling's famous agent-based model for residential segregation explains how such clusters can form even if all agents are tolerant, i.e., if they agree to live in mixed neighborhoods. For segregation to occur, all it needs is a slight bias towards agents preferring similar neighbors. Very recently, Schelling's model has been investigated from a game-theoretic point of view with selfish agents that strategically select their residential location. In these games, agents can improve on their current location by performing a location swap with another agent who is willing to swap. We significantly deepen these investigations by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy and on the dynamic properties of the resulting strategic multi-agent system. Moreover, as a new conceptual contribution, we also consider the influence of locality, i.e., if the location swaps are restricted to swaps of neighboring agents. We give improved almost tight bounds on the Price of Anarchy for arbitrary underlying graphs and we present (almost) tight bounds for regular graphs, paths and cycles. Moreover, we give almost tight bounds for grids, which are commonly used in empirical studies. For grids we also show that locality has a severe impact on the game dynamics.}, author = {Bilò, Davide and Bilò, Vittorio and Lenzner, Pascal and Molitor, Louise}, journal = {Autonomous Agents and Multi-Agent Systems (AGNT)}, keywords = {louisemolitor agnt year2022 pascallenzner}, number = 2, pages = 47, title = {Topological Influence and Locality in Swap Schelling Games}, volume = 36, year = 2022 }

Casel, Katrin; Fischbeck, Philipp; Friedrich, Tobias; Göbel, Andreas; Lagodzinski, J. A. Gregor Zeros and approximations of Holant polynomials on the complex planeComputational Complexity 2022: 11
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We present fully polynomial time approximation schemesfor a broad class of Holant problems with complex edge weights, which we call Holant polynomials. We transform these problems into partition functions of abstract combinatorial structures known as polymers in statistical physics. Our method involves establishing zero-free regions for the partition functions of polymer models and using the mostsignificant terms of the cluster expansion to approximate them. Results of our technique include new approximation and sampling algorithms for a diverse class of Holant polynomials in the low-temperature regime (i.e. small external field) and approximation algorithms for general Holant problems with small signature weights. Additionally, we give randomised approximation and sampling algorithms with faster running times for more restrictive classes. Finally, we improve the known zero-free regions for a perfect matching polynomial.
@article{casel2022zeros, abstract = {We present fully polynomial time approximation schemesfor a broad class of Holant problems with complex edge weights, which we call Holant polynomials. We transform these problems into partition functions of abstract combinatorial structures known as polymers in statistical physics. Our method involves establishing zero-free regions for the partition functions of polymer models and using the mostsignificant terms of the cluster expansion to approximate them. Results of our technique include new approximation and sampling algorithms for a diverse class of Holant polynomials in the low-temperature regime (i.e. small external field) and approximation algorithms for general Holant problems with small signature weights. Additionally, we give randomised approximation and sampling algorithms with faster running times for more restrictive classes. Finally, we improve the known zero-free regions for a perfect matching polynomial.}, author = {Casel, Katrin and Fischbeck, Philipp and Friedrich, Tobias and Göbel, Andreas and Lagodzinski, J. A. Gregor}, journal = {Computational Complexity}, keywords = {gregorlagodzinski philippfischbeck katrincasel andreasgoebel tobiasfriedrich year2022 cc}, number = 2, pages = 11, title = {Zeros and approximations of Holant polynomials on the complex plane}, volume = 31, year = 2022 }

Casel, Katrin; Fernau, Henning; Grigoriev, Alexander; Schmid, Markus L.; Whitesides, Sue Combinatorial Properties and Recognition of Unit Square Visibility GraphsDiscrete \& Computational Geometry 2022
[ Abstract ] [ BibTeX ] [ Download ]
 
Unit square visibility graphs (USV) are described by axis-parallel visibility between unit squares placed in the plane. If the squares are required to be placed on integer grid coordinates, then USV become unit square grid visibility graphs (USGV), an alternative characterisation of the well-known rectilinear graphs. We extend known combinatorial results for USGV and we show that, in the weak case (i.e., visibilities do not necessarily translate into edges of the represented combinatorial graph), the area minimisation variant of their recognition problem is NP-hard. We also provide combinatorial insights with respect to USV, and as our main result, we prove their recognition problem to be $\mathcal{NP}$-hard, which settles an open question.
@article{casel2022combinatorial, abstract = {Unit square visibility graphs (USV) are described by axis-parallel visibility between unit squares placed in the plane. If the squares are required to be placed on integer grid coordinates, then USV become unit square grid visibility graphs (USGV), an alternative characterisation of the well-known rectilinear graphs. We extend known combinatorial results for USGV and we show that, in the weak case (i.e., visibilities do not necessarily translate into edges of the represented combinatorial graph), the area minimisation variant of their recognition problem is NP-hard. We also provide combinatorial insights with respect to USV, and as our main result, we prove their recognition problem to be $\mathcal{NP}$-hard, which settles an open question.}, author = {Casel, Katrin and Fernau, Henning and Grigoriev, Alexander and Schmid, Markus L. and Whitesides, Sue}, journal = {Discrete \& Computational Geometry}, keywords = {katrincasel dcg year2022}, title = {Combinatorial Properties and Recognition of Unit Square Visibility Graphs}, year = 2022 }

Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, Martin Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data ProfilingJournal of Computer and System Sciences 2022: 192–213
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The transversal hypergraph problem asks to enumerate the minimal hitting sets of a hypergraph. If the solutions have bounded size, Eiter and Gottlob [SICOMP’95] gave an algorithm running in output-polynomial time, but whose space requirement also scales with the output. We improve this to polynomial delay and space. Central to our approach is the extension problem, deciding for a set X of vertices whether it is contained in any minimal hitting set. We show that this is one of the first natural problems to be W[3]-complete. We give an algorithm for the extension problem running in time O(m |X|+1 n) and prove a SETH-lower bound showing that this is close to optimal. We apply our enumeration method to the discovery problem of minimal unique column combinations from data profiling. Our empirical evaluation suggests that the algorithm outperforms its worst-case guarantees on hypergraphs stemming from real-world databases.
@article{Blaesius22Efficiently, abstract = {The transversal hypergraph problem asks to enumerate the minimal hitting sets of a hypergraph. If the solutions have bounded size, Eiter and Gottlob [SICOMP’95] gave an algorithm running in output-polynomial time, but whose space requirement also scales with the output. We improve this to polynomial delay and space. Central to our approach is the extension problem, deciding for a set X of vertices whether it is contained in any minimal hitting set. We show that this is one of the first natural problems to be W[3]-complete. We give an algorithm for the extension problem running in time O(m |X|+1 n) and prove a SETH-lower bound showing that this is close to optimal. We apply our enumeration method to the discovery problem of minimal unique column combinations from data profiling. Our empirical evaluation suggests that the algorithm outperforms its worst-case guarantees on hypergraphs stemming from real-world databases.}, author = {Bläsius, Thomas and Friedrich, Tobias and Lischeid, Julius and Meeks, Kitty and Schirneck, Martin}, journal = {Journal of Computer and System Sciences}, keywords = {kittymeeks thomasblaesius juliuslischeid tobiasfriedrich year2022 martinschirneck}, pages = {192-213}, title = {Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling}, volume = 124, year = 2022 }

Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, Marcus A Spectral Independence View on Hard Spheres via Block DynamicsSIAM Journal on Discrete Mathematics 2022: 2282–2322
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
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 < \mathrm{e} / 2d\), the runtime of our algorithm is polynomial in the volume of the system. 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 block dynamics, a Markov chain that generalizes the more frequently studied Glauber dynamics by grouping the vertices of the graph into blocks and updating an entire block instead of a single vertex in each step. We prove rapid mixing of block dynamics, based on disjoint cliques as blocks, up to the tree threshold of the univariate hard-core model. This is achieved by adapting the spectral expansion method, which was recently used for bounding the mixing time of Glauber dynamics within the same parameter regime.
@article{friedrich2022spectral, 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 < \mathrm{e} / 2d\), the runtime of our algorithm is polynomial in the volume of the system. 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 block dynamics, a Markov chain that generalizes the more frequently studied Glauber dynamics by grouping the vertices of the graph into blocks and updating an entire block instead of a single vertex in each step. We prove rapid mixing of block dynamics, based on disjoint cliques as blocks, up to the tree threshold of the univariate hard-core model. This is achieved by adapting the spectral expansion method, which was recently used for bounding the mixing time of Glauber dynamics within the same parameter regime.}, author = {Friedrich, Tobias and Göbel, Andreas and Krejca, Martin S. and Pappik, Marcus}, journal = {SIAM Journal on Discrete Mathematics}, keywords = {marcuspappik martinskrejca andreasgoebel tobiasfriedrich year2022}, number = 3, pages = {2282-2322}, title = {A Spectral Independence View on Hard Spheres via Block Dynamics}, volume = 36, year = 2022 }

Bläsius, Thomas; Friedrich, Tobias; Schirneck, Martin The Complexity of Dependency Detection and Discovery in Relational DatabasesTheoretical Computer Science 2022: 79–96
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ 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{blaesius2022complexity, 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 = {Theoretical Computer Science}, keywords = {tcs thomasblaesius tobiasfriedrich year2022 martinschirneck}, pages = {79-96}, title = {The Complexity of Dependency Detection and Discovery in Relational Databases}, volume = 900, year = 2022 }

Bandyapadhyay, Sayan; Fomin, Fedor V.; Golovach, Petr A.; Lochet, William; Purohit, Nidhi; Simonov, Kirill How to Find a Good Explanation for Clustering?Conference on Artificial Intelligence (AAAI) 2022: 3904–3912
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
\(k\)-means and \(k\)-median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependences on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, Dasgupta, Rashtchian, and Frost proposed an elegant model of explainable \(k\)-means and \(k\)-median clustering in ICML 2020. In this model, a decision tree with \(k\) leaves provides a straightforward characterization of the data set into clusters. We study two natural algorithmic questions about explainable clustering. (1) For a given clustering, how to find the ``best explanation'' by using a decision tree with \(k\) leaves? (2) For a given set of points, how to find a decision tree with \(k\) leaves minimizing the \(k\)-means/median objective of the resulting explainable clustering? To address the first question, we introduce a new model of explainable clustering. Our model, inspired by the notion of outliers in robust statistics, is the following. We are seeking a small number of points (outliers) whose removal makes the existing clustering well-explainable. For addressing the second question, we initiate the study of the model of Moshkovitz et al. from the perspective of multivariate complexity. Our rigorous algorithmic analysis sheds some light on the influence of parameters like the input size, dimension of the data, the number of outliers, the number of clusters, and the approximation ratio, on the computational complexity of explainable clustering.
@inproceedings{bandyapadhyay2022explanation, abstract = {\(k\)-means and \(k\)-median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependences on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, Dasgupta, Rashtchian, and Frost proposed an elegant model of explainable \(k\)-means and \(k\)-median clustering in ICML 2020. In this model, a decision tree with \(k\) leaves provides a straightforward characterization of the data set into clusters. We study two natural algorithmic questions about explainable clustering. (1) For a given clustering, how to find the ``best explanation'' by using a decision tree with \(k\) leaves? (2) For a given set of points, how to find a decision tree with \(k\) leaves minimizing the \(k\)-means/median objective of the resulting explainable clustering? To address the first question, we introduce a new model of explainable clustering. Our model, inspired by the notion of outliers in robust statistics, is the following. We are seeking a small number of points (outliers) whose removal makes the existing clustering well-explainable. For addressing the second question, we initiate the study of the model of Moshkovitz et al. from the perspective of multivariate complexity. Our rigorous algorithmic analysis sheds some light on the influence of parameters like the input size, dimension of the data, the number of outliers, the number of clusters, and the approximation ratio, on the computational complexity of explainable clustering.}, author = {Bandyapadhyay, Sayan and Fomin, Fedor V. and Golovach, Petr A. and Lochet, William and Purohit, Nidhi and Simonov, Kirill}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {sys:relevantfor:ae kirillsimonov aaai year2022}, pages = {3904-3912}, title = {How to Find a Good Explanation for Clustering?}, year = 2022 }

Cseh, Ágnes; Peters, Jannik Three-Dimensional Popular Matching with Cyclic PreferencesAutonomous Agents and Multi-Agent Systems (AAMAS) 2022: 77–87
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Two actively researched problem settings in matchings under preferences are popular matchings and the three-dimensional stable matching problem with cyclic preferences. In this paper, we apply the optimality notion of the first topic to the input characteristics of the second one. We investigate the connection between stability, popularity, and their strict variants, strong stability and strong popularity in three-dimensional instances with cyclic preferences. Furthermore, we also derive results on the complexity of these problems when the preferences are derived from master lists.
@inproceedings{cseh2022threedimensional, abstract = {Two actively researched problem settings in matchings under preferences are popular matchings and the three-dimensional stable matching problem with cyclic preferences. In this paper, we apply the optimality notion of the first topic to the input characteristics of the second one. We investigate the connection between stability, popularity, and their strict variants, strong stability and strong popularity in three-dimensional instances with cyclic preferences. Furthermore, we also derive results on the complexity of these problems when the preferences are derived from master lists.}, author = {Cseh, Ágnes and Peters, Jannik}, booktitle = {Autonomous Agents and Multi-Agent Systems (AAMAS)}, keywords = {jannikpeters agnescseh aamas year2022}, pages = {77&ndash;87}, title = {Three-Dimensional Popular Matching with Cyclic Preferences}, year = 2022 }

Berenbrink, Petra; Hoefer, Martin; Kaaser, Dominik; Lenzner, Pascal; Rau, Malin; Schmand, Daniel Asynchronous Opinion Dynamics in Social NetworksAutonomous Agents and Multi-Agent Systems (AAMAS) 2022: 109–117
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Opinion spreading in a society decides the fate of elections, the success of products, and the impact of political or social movements. The model by Hegselmann and Krause is a well-known theoretical model to study such opinion formation processes in social networks. In contrast to many other theoretical models, it does not converge towards a situation where all agents agree on the same opinion. Instead, it assumes that people find an opinion reasonable if and only if it is close to their own. The system converges towards a stable situation where agents sharing the same opinion form a cluster, and agents in different clusters do not influence each other. We focus on the social variant of the Hegselmann-Krause model where agents are connected by a social network and their opinions evolve in an iterative process. When activated, an agent adopts the average of the opinions of its neighbors having a similar opinion. By this, the set of influencing neighbors of an agent may change over time. To the best of our knowledge, social Hegselmann-Krause systems with asynchronous opinion updates have only been studied with the complete graph as social network. We show that such opinion dynamics with random agent activation are guaranteed to converge for any social network. We provide an upper bound of \(\mathcal{O}(n |E|^2 (\varepsilon/\delta)^2)\) on the expected number of opinion updates until convergence, where |E| is the number of edges of the social network. For the complete social network we show a bound of \( \mathcal{O}(n^3(n^2 + (\varepsilon/\delta)^2)) \) that represents a major improvement over the previously best upper bound of \( \mathcal{O}(n^9(\varepsilon/\delta)^2) \). Our bounds are complemented by simulations that indicate asymptotically matching lower bounds.
@inproceedings{berenbrink2022asynchronous, abstract = {Opinion spreading in a society decides the fate of elections, the success of products, and the impact of political or social movements. The model by Hegselmann and Krause is a well-known theoretical model to study such opinion formation processes in social networks. In contrast to many other theoretical models, it does not converge towards a situation where all agents agree on the same opinion. Instead, it assumes that people find an opinion reasonable if and only if it is close to their own. The system converges towards a stable situation where agents sharing the same opinion form a cluster, and agents in different clusters do not influence each other. We focus on the social variant of the Hegselmann-Krause model where agents are connected by a social network and their opinions evolve in an iterative process. When activated, an agent adopts the average of the opinions of its neighbors having a similar opinion. By this, the set of influencing neighbors of an agent may change over time. To the best of our knowledge, social Hegselmann-Krause systems with asynchronous opinion updates have only been studied with the complete graph as social network. We show that such opinion dynamics with random agent activation are guaranteed to converge for any social network. We provide an upper bound of \(\mathcal{O}(n |E|^2 (\varepsilon/\delta)^2)\) on the expected number of opinion updates until convergence, where |E| is the number of edges of the social network. For the complete social network we show a bound of \( \mathcal{O}(n^3(n^2 + (\varepsilon/\delta)^2)) \) that represents a major improvement over the previously best upper bound of \( \mathcal{O}(n^9(\varepsilon/\delta)^2) \). Our bounds are complemented by simulations that indicate asymptotically matching lower bounds.}, author = {Berenbrink, Petra and Hoefer, Martin and Kaaser, Dominik and Lenzner, Pascal and Rau, Malin and Schmand, Daniel}, booktitle = {Autonomous Agents and Multi-Agent Systems (AAMAS)}, keywords = {aamas year2022 pascallenzner}, pages = {109&ndash;117}, title = {Asynchronous Opinion Dynamics in Social Networks}, year = 2022 }

Cseh, Ágnes; Friedrich, Tobias; Peters, Jannik Pareto Optimal and Popular House Allocation with Lower and Upper QuotasAutonomous Agents and Multi-Agent Systems (AAMAS) 2022: 300–308
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In the house allocation problem with lower and upper quotas, we are given a set of applicants and a set of projects. Each applicant has a strictly ordered preference list over the projects, while the projects are equipped with a lower and an upper quota. A feasible matching assigns the applicants to the projects in such a way that a project is either matched to no applicant or to a number of applicants between its lower and upper quota. In this model we study two classic optimality concepts: Pareto optimality and popularity. We show that finding a popular matching is hard even if the maximum lower quota is 2 and that finding a perfect Pareto optimal matching, verifying Pareto optimality, and verifying popularity are all NP-complete even if the maximum lower quota is 3. We complement the last three negative results by showing that the problems become polynomial-time solvable when the maximum lower quota is 2, thereby answering two open questions of Cechlárová and Fleiner. Finally, we also study the parameterized complexity of all four mentioned problems.
@inproceedings{cseh2022pareto, abstract = {In the house allocation problem with lower and upper quotas, we are given a set of applicants and a set of projects. Each applicant has a strictly ordered preference list over the projects, while the projects are equipped with a lower and an upper quota. A feasible matching assigns the applicants to the projects in such a way that a project is either matched to no applicant or to a number of applicants between its lower and upper quota. In this model we study two classic optimality concepts: Pareto optimality and popularity. We show that finding a popular matching is hard even if the maximum lower quota is 2 and that finding a perfect Pareto optimal matching, verifying Pareto optimality, and verifying popularity are all NP-complete even if the maximum lower quota is 3. We complement the last three negative results by showing that the problems become polynomial-time solvable when the maximum lower quota is 2, thereby answering two open questions of Cechlárová and Fleiner. Finally, we also study the parameterized complexity of all four mentioned problems.}, author = {Cseh, Ágnes and Friedrich, Tobias and Peters, Jannik}, booktitle = {Autonomous Agents and Multi-Agent Systems (AAMAS)}, keywords = {jannikpeters agnescseh tobiasfriedrich aamas year2022}, pages = {300&ndash;308}, title = {Pareto Optimal and Popular House Allocation with Lower and Upper Quotas}, year = 2022 }

Bläsius, Thomas; Friedrich, Tobias; Stangl, David; Weyand, Christopher An Efficient Branch-and-Bound Solver for Hitting SetAlgorithm Engineering and Experiments (ALENEX) 2022
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The hitting set problem asks for a collection of sets over a universe \(U\) to find a minimum subset of \(U\) that intersects each of the given sets. It is NP-hard and equivalent to the problem set cover. We give a branch-and-bound algorithm to solve hitting set. Though it requires exponential time in the worst case, it can solve many practical instance from different domains in reasonable time. Our algorithm outperforms a modern ILP solver, the state-of-the-art for hitting set, by at least an order of magnitude on most instances.
@inproceedings{blasius2022efficient, abstract = {The hitting set problem asks for a collection of sets over a universe \(U\) to find a minimum subset of \(U\) that intersects each of the given sets. It is NP-hard and equivalent to the problem set cover. We give a branch-and-bound algorithm to solve hitting set. Though it requires exponential time in the worst case, it can solve many practical instance from different domains in reasonable time. Our algorithm outperforms a modern ILP solver, the state-of-the-art for hitting set, by at least an order of magnitude on most instances.}, author = {Bläsius, Thomas and Friedrich, Tobias and Stangl, David and Weyand, Christopher}, booktitle = {Algorithm Engineering and Experiments (ALENEX)}, keywords = {alenex thomasblaesius tobiasfriedrich christopherweyand davidstangl year2022}, title = {An Efficient Branch-and-Bound Solver for Hitting Set}, year = 2022 }

Friedrich, Tobias; Issac, Davis; Kumar, Nikhil; Mallek, Nadym; Zeif, Ziena A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 GraphsApproximation Algorithms for Combinatorial Optimization Problems (APPROX) 2022: 55:1–55:18
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study the problem of multicommodity flow and multicut in treewidth-2 graphs and prove bounds on the multiflow-multicut gap. In particular, we give a primal-dual algorithm for computing multicommodity flow and multicut in treewidth-2 graphs and prove the following approximate max-flow min-cut theorem: given a treewidth-2 graph, there exists a multicommodity flow of value \(f\) with congestion \(4\), and a multicut of capacity \(c\) such that \(c \leq 20f \) . This implies a multiflow-multicut gap of \(80\) and improves upon the previous best known bounds for such graphs. Our algorithm runs in polynomial time when all the edges have capacity one. Our algorithm is completely combinatorial and builds upon the primal-dual algorithm of Garg, Vazirani and Yannakakis for multicut in trees and the augmenting paths framework of Ford and Fulkerson.
@inproceedings{friedrich2022primaldual, abstract = {We study the problem of multicommodity flow and multicut in treewidth-2 graphs and prove bounds on the multiflow-multicut gap. In particular, we give a primal-dual algorithm for computing multicommodity flow and multicut in treewidth-2 graphs and prove the following approximate max-flow min-cut theorem: given a treewidth-2 graph, there exists a multicommodity flow of value \(f\) with congestion \(4\), and a multicut of capacity \(c\) such that \(c \leq 20f \) . This implies a multiflow-multicut gap of \(80\) and improves upon the previous best known bounds for such graphs. Our algorithm runs in polynomial time when all the edges have capacity one. Our algorithm is completely combinatorial and builds upon the primal-dual algorithm of Garg, Vazirani and Yannakakis for multicut in trees and the augmenting paths framework of Ford and Fulkerson.}, author = {Friedrich, Tobias and Issac, Davis and Kumar, Nikhil and Mallek, Nadym and Zeif, Ziena}, booktitle = {Approximation Algorithms for Combinatorial Optimization Problems (APPROX)}, keywords = {sys:relevantfor:ae zienazeif nikhilkumar davisissac tobiasfriedrich approx nadymmallek year2022}, pages = {55:1&ndash;55:18}, title = {A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs}, year = 2022 }

Doskoč, Vanja; Kötzing, Timo Maps of Restrictions for Behaviourally Correct LearningComputability in Europe (CiE) 2022: 103–114
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In language learning in the limit, we study computable devices (learners) learning formal languages. We consider learning tasks paired with restrictions regarding, for example, the hypotheses made by the learners. We compare such restrictions with each other in order to study their impact and depict the results in overviews, the so-called maps. In~the case of explanatory learning, the literature already provides various maps. On the other hand, in the case of behaviourally correct learning, only partial results are known. In this work, we complete these results and provide full behaviourally correct maps for different types of data presentation. In particular, in all studied settings, we observe that monotone learning implies non-U-shaped learning and that cautiousness, semantic conservativeness and weak monotonicity are equally powerful.
@inproceedings{doskoc2022restrictions, abstract = {In language learning in the limit, we study computable devices (learners) learning formal languages. We consider learning tasks paired with restrictions regarding, for example, the hypotheses made by the learners. We compare such restrictions with each other in order to study their impact and depict the results in overviews, the so-called maps. In&nbsp;the case of explanatory learning, the literature already provides various maps. On the other hand, in the case of behaviourally correct learning, only partial results are known. In this work, we complete these results and provide full behaviourally correct maps for different types of data presentation. In particular, in all studied settings, we observe that monotone learning implies non-U-shaped learning and that cautiousness, semantic conservativeness and weak monotonicity are equally powerful.}, author = {Doskoč, Vanja and Kötzing, Timo}, booktitle = {Computability in Europe (CiE)}, keywords = {vanjadoskoc timokoetzing year2022 cie}, pages = {103-114}, title = {Maps of Restrictions for Behaviourally Correct Learning}, volume = 13359, year = 2022 }

Friedrich, Tobias; Göbel, Andreas; Katzmann, Maximilian; Krejca, Martin S.; Pappik, Marcus Algorithms for hard-constraint point processes via discretizationInternational Computing and Combinatorics Conference (COCOON) 2022
[ Abstract ] [ BibTeX ] [ Download ]
 
We study the algorithmic applications of a natural discretization for the hard-sphere model and the Widom--Rowlinson model in a region of \(d\)-dimensional Euclidean space \(V \subset \mathbf{R}^{d}\). These continuous models are frequently used in statistical physics to describe mixtures of one or multiple particle types subjected to hard-core interactions. For each type, particles are distributed according to a Poisson point process with a type-specific activity parameter, called fugacity. The Gibbs distribution over all possible system states is characterized by the mixture of these point processes conditioned that no two particles are closer than some type-dependent distance threshold. A key part in better understanding the Gibbs distribution is its normalizing constant, called partition function. Our main algorithmic result is the first deterministic approximation algorithm for the partition function of the hard-sphere model and the Widom--Rowlinson model in box-shaped regions of Euclidean space. Our algorithms have quasi-polynomial running time in the volume of the region \(\nu(V)\) if the fugacity is below a certain threshold. For the \(d\)-dimensional hard-sphere model with particles of unit volume, this threshold is \(\mathrm{e}/2^d\). As the number of dimensions \(d\) increases, this bound asymptotically matches the best known results for randomized approximation of the hard-sphere partition function. We prove similar bounds for the Widom--Rowlinson model. To the best of our knowledge, this is the first rigorous algorithmic result for this model.
@inproceedings{friedrich2022algorithms, abstract = {We study the algorithmic applications of a natural discretization for the hard-sphere model and the Widom&ndash;Rowlinson model in a region of \(d\)-dimensional Euclidean space \(V \subset \mathbf{R}^{d}\). These continuous models are frequently used in statistical physics to describe mixtures of one or multiple particle types subjected to hard-core interactions. For each type, particles are distributed according to a Poisson point process with a type-specific activity parameter, called fugacity. The Gibbs distribution over all possible system states is characterized by the mixture of these point processes conditioned that no two particles are closer than some type-dependent distance threshold. A key part in better understanding the Gibbs distribution is its normalizing constant, called partition function. Our main algorithmic result is the first deterministic approximation algorithm for the partition function of the hard-sphere model and the Widom&ndash;Rowlinson model in box-shaped regions of Euclidean space. Our algorithms have quasi-polynomial running time in the volume of the region \(\nu(V)\) if the fugacity is below a certain threshold. For the \(d\)-dimensional hard-sphere model with particles of unit volume, this threshold is \(\mathrm{e}/2^d\). As the number of dimensions \(d\) increases, this bound asymptotically matches the best known results for randomized approximation of the hard-sphere partition function. We prove similar bounds for the Widom&ndash;Rowlinson model. To the best of our knowledge, this is the first rigorous algorithmic result for this model.}, author = {Friedrich, Tobias and Göbel, Andreas and Katzmann, Maximilian and Krejca, Martin S. and Pappik, Marcus}, booktitle = {International Computing and Combinatorics Conference (COCOON)}, keywords = {marcuspappik martinskrejca andreasgoebel tobiasfriedrich cocoon maximiliankatzmann year2022}, title = {Algorithms for hard-constraint point processes via discretization}, year = 2022 }

Hildebrandt, Philipp; Schulze, Maximilian; Cohen, Sarel; Doskoč, Vanja; Saabni, Raid; Friedrich, Tobias Optical Character Recognition Guided Image Super ResolutionSymposium on Document Engineering (DocEng) 2022: 1–4
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Recognizing disturbed text in real-life images is a difficult problem, as information that is missing due to low resolution or out-of-focus text has to be recreated. Combining text super-resolution and optical character recognition deep learning models can be a valuable tool to enlarge and enhance text images for better readability, as well as recognize text automatically afterwards. We achieve improved peak signal-to-noise ratio and text recognition accuracy scores over a state-of-the-art text super-resolution model TBSRN on the real-world low-resolution dataset TextZoom while having a smaller theoretical model size due to the usage of quantization techniques. In addition, we show how different training strategies influence the performance of the resulting model.
@inproceedings{hildebrandt2022optical, abstract = {Recognizing disturbed text in real-life images is a difficult problem, as information that is missing due to low resolution or out-of-focus text has to be recreated. Combining text super-resolution and optical character recognition deep learning models can be a valuable tool to enlarge and enhance text images for better readability, as well as recognize text automatically afterwards. We achieve improved peak signal-to-noise ratio and text recognition accuracy scores over a state-of-the-art text super-resolution model TBSRN on the real-world low-resolution dataset TextZoom while having a smaller theoretical model size due to the usage of quantization techniques. In addition, we show how different training strategies influence the performance of the resulting model.}, author = {Hildebrandt, Philipp and Schulze, Maximilian and Cohen, Sarel and Doskoč, Vanja and Saabni, Raid and Friedrich, Tobias}, booktitle = {Symposium on Document Engineering (DocEng)}, keywords = {sarelcohen vanjadoskoc philipphildebrandt maximilianschulze tobiasfriedrich doceng raidsaabni year2022}, pages = {1-4}, title = {Optical Character Recognition Guided Image Super Resolution}, year = 2022 }

Führlich, Pascal; Cseh, Ágnes; Lenzner, Pascal Improving Ranking Quality and Fairness in Swiss-System Chess TournamentsACM Conference on Economics and Computation (EC) 2022: 1101–1102
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The International Chess Federation (FIDE) imposes a voluminous and complex set of player pairing criteria in Swiss-system chess tournaments and endorses computer programs that are able to calculate the prescribed pairings. The purpose of these formalities is to ensure that players are paired fairly during the tournament and that the final ranking corresponds to the players' true strength order. We contest the official FIDE player pairing routine by presenting alternative pairing rules. These can be enforced by computing maximum weight matchings in a carefully designed graph. We demonstrate by extensive experiments that a tournament format using our mechanism (1) yields fairer pairings in the rounds of the tournament and (2) produces a final ranking that reflects the players' true strengths better than the state-of-the-art FIDE pairing system.
@inproceedings{fuhrlich2022improving, abstract = {The International Chess Federation (FIDE) imposes a voluminous and complex set of player pairing criteria in Swiss-system chess tournaments and endorses computer programs that are able to calculate the prescribed pairings. The purpose of these formalities is to ensure that players are paired fairly during the tournament and that the final ranking corresponds to the players' true strength order. We contest the official FIDE player pairing routine by presenting alternative pairing rules. These can be enforced by computing maximum weight matchings in a carefully designed graph. We demonstrate by extensive experiments that a tournament format using our mechanism (1) yields fairer pairings in the rounds of the tournament and (2) produces a final ranking that reflects the players' true strengths better than the state-of-the-art FIDE pairing system.}, author = {Führlich, Pascal and Cseh, Ágnes and Lenzner, Pascal}, booktitle = {ACM Conference on Economics and Computation (EC)}, keywords = {agnescseh year2022 ec pascallenzner}, pages = {1101 &ndash; 1102}, publisher = {ACM}, title = {Improving Ranking Quality and Fairness in Swiss-System Chess Tournaments}, year = 2022 }

Bläsius, Thomas; Fischbeck, Philipp On the External Validity of Average-Case Analyses of Graph AlgorithmsEuropean Symposium on Algorithms (ESA) 2022: 21:1–21:14
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The number one criticism of average-case analysis is that we do not actually know the probability distribution of real-world inputs. Thus, analyzing an algorithm on some random model has no implications for practical performance. At its core, this criticism doubts the existence of external validity, i.e., it assumes that algorithmic behavior on the somewhat simple and clean models does not translate beyond the models to practical performance real-world input. With this paper, we provide a first step towards studying the question of external validity systematically. To this end, we evaluate the performance of six graph algorithms on a collection of 2751 sparse real-world networks depending on two properties; the heterogeneity (variance in the degree distribution) and locality (tendency of edges to connect vertices that are already close). We compare this with the performance on generated networks with varying locality and heterogeneity. We find that the performance in the idealized setting of network models translates surprisingly well to real-world networks. Moreover, heterogeneity and locality appear to be the core properties impacting the performance of many graph algorithms.
@inproceedings{blasius2022external, abstract = {The number one criticism of average-case analysis is that we do not actually know the probability distribution of real-world inputs. Thus, analyzing an algorithm on some random model has no implications for practical performance. At its core, this criticism doubts the existence of external validity, i.e., it assumes that algorithmic behavior on the somewhat simple and clean models does not translate beyond the models to practical performance real-world input. With this paper, we provide a first step towards studying the question of external validity systematically. To this end, we evaluate the performance of six graph algorithms on a collection of 2751 sparse real-world networks depending on two properties; the heterogeneity (variance in the degree distribution) and locality (tendency of edges to connect vertices that are already close). We compare this with the performance on generated networks with varying locality and heterogeneity. We find that the performance in the idealized setting of network models translates surprisingly well to real-world networks. Moreover, heterogeneity and locality appear to be the core properties impacting the performance of many graph algorithms.}, author = {Bläsius, Thomas and Fischbeck, Philipp}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {philippfischbeck esa thomasblaesius year2022}, pages = {21:1&ndash;21:14}, title = {On the External Validity of Average-Case Analyses of Graph Algorithms}, year = 2022 }

Kumar, Nikhil An Approximate Generalization of the Okamura-Seymour TheoremSymposium on Foundations of Computer Science (FOCS) 2022
[ Abstract ] [ BibTeX ] [ Download ]
 
We consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient for routing demands. We consider the following generalization of this setting and prove an approximate max flow-min cut theorem: for every demand edge, there exists a face containing both its end points. We show that the cut-condition is sufficient for routing \(\Omega(1)\)-fraction of all the demands. To prove this, we give a \(L_1\)-embedding of the planar metric which approximately preserves distance between all pair of points on the same face.
@inproceedings{kumar2022approximate, abstract = {We consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient for routing demands. We consider the following generalization of this setting and prove an approximate max flow-min cut theorem: for every demand edge, there exists a face containing both its end points. We show that the cut-condition is sufficient for routing \(\Omega(1)\)-fraction of all the demands. To prove this, we give a \(L_1\)-embedding of the planar metric which approximately preserves distance between all pair of points on the same face.}, author = {Kumar, Nikhil}, booktitle = {Symposium on Foundations of Computer Science (FOCS)}, keywords = {sys:relevantfor:ae nikhilkumar focs year2022}, title = {An Approximate Generalization of the Okamura-Seymour Theorem}, year = 2022 }

Angrick, Sebastian; Bals, Ben; Hastrich, Niko; Kleissl, Maximilian; Schmidt, Jonas; Doskoč, Vanja; Katzmann, Maximilian; Molitor, Louise; Friedrich, Tobias Towards Explainable Real Estate Valuation via Evolutionary AlgorithmsGenetic and Evolutionary Computation Conference (GECCO) 2022: 1130–1138
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Human lives are increasingly influenced by algorithms, which therefore need to meet higher standards not only in accuracy but also with respect to explainability. This is especially true for high-stakes areas such as real estate valuation. Unfortunately, the methods applied there often exhibit a trade-off between accuracy and explainability. One explainable approach is case-based reasoning (CBR), whereeach decision is supported by specific previous cases. However, such methods can be wanting in accuracy. The unexplainable machine learning approaches are often observed to provide higher accuracy but are not scrutable in their decision-making. In this paper, we apply evolutionary algorithms (EAs) to CBR predictors in order to improve their performance. In particular, we deploy EAs to the similarity functions (used in CBR to find comparable cases), which are fitted to the data set at hand. As a consequence, we achieve higher accuracy than state-of-the-art deep neural networks (DNNs), while keeping interpretability and explainability. These results stem from our empirical evaluation on a large data set of real estate offers where we compare known similarity functions, their EA-improved counterparts, and DNNs. Surprisingly, DNNs are only on par with standard CBR techniques. However, using EA-learned similarity functions does yield an improved performance.
@inproceedings{angrick2022towards, abstract = {Human lives are increasingly influenced by algorithms, which therefore need to meet higher standards not only in accuracy but also with respect to explainability. This is especially true for high-stakes areas such as real estate valuation. Unfortunately, the methods applied there often exhibit a trade-off between accuracy and explainability. One explainable approach is case-based reasoning (CBR), whereeach decision is supported by specific previous cases. However, such methods can be wanting in accuracy. The unexplainable machine learning approaches are often observed to provide higher accuracy but are not scrutable in their decision-making. In this paper, we apply evolutionary algorithms (EAs) to CBR predictors in order to improve their performance. In particular, we deploy EAs to the similarity functions (used in CBR to find comparable cases), which are fitted to the data set at hand. As a consequence, we achieve higher accuracy than state-of-the-art deep neural networks (DNNs), while keeping interpretability and explainability. These results stem from our empirical evaluation on a large data set of real estate offers where we compare known similarity functions, their EA-improved counterparts, and DNNs. Surprisingly, DNNs are only on par with standard CBR techniques. However, using EA-learned similarity functions does yield an improved performance.}, author = {Angrick, Sebastian and Bals, Ben and Hastrich, Niko and Kleissl, Maximilian and Schmidt, Jonas and Doskoč, Vanja and Katzmann, Maximilian and Molitor, Louise and Friedrich, Tobias}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {louisemolitor vanjadoskoc sebastianangrick benbals nikohastrich tobiasfriedrich gecco maximiliankleissl jonasschmidt maximiliankatzmann year2022}, pages = {1130&ndash;1138}, title = {Towards Explainable Real Estate Valuation via Evolutionary Algorithms}, year = 2022 }

Baguley, Samuel; Friedrich, Tobias; Timo, Kötzing; Li, Xiaoyue; Pappik, Marcus; Zeif, Ziena Analysis of a Gray-Box Operator for Vertex CoverGenetic and Evolutionary Computation Conference (GECCO) 2022: 1363–1371
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Combinatorial optimization problems are a prominent application area of evolutionary algorithms, where the (1+1) EA is one of the most investigated. We extend this algorithm by introducing some problem knowledge with a specialized mutation operator which works under the assumption that the number of 1s of a solution is critical, as frequently happens in combinatorial optimization. This slight modification increases the chance to correct wrongly placed bits while preserving the simplicity and problem independence of the (1+1) EA. As an application of our algorithm we examine the vertex cover problem on certain instances, where we show that it leads to asymptotically better runtimes and even finds with higher probability optimal solutions in comparison with the usual (1+1) EA. Precisely, we compare the performance of both algorithms on paths and on complete bipartite graphs of size \(n\). Regarding the path we prove that, for a particular initial configuration, the (1+1) EA takes in expectation \(\Theta(n^4)\) iterations while the modification reduces this to \(\Theta(n^3)\), and present experimental evidence that such a configuration is reached. Concerning the complete bipartite graph our modification finds the optimum in polynomial time with probability \(1-1/2^{\Omega(n^\xi)}\) for every positive constant \(\xi < 1\), which improves the known probability of \(1-1/\)poly\((n)\) for the (1+1) EA.
@inproceedings{baguley2022analysis, abstract = {Combinatorial optimization problems are a prominent application area of evolutionary algorithms, where the (1+1) EA is one of the most investigated. We extend this algorithm by introducing some problem knowledge with a specialized mutation operator which works under the assumption that the number of 1s of a solution is critical, as frequently happens in combinatorial optimization. This slight modification increases the chance to correct wrongly placed bits while preserving the simplicity and problem independence of the (1+1) EA. As an application of our algorithm we examine the vertex cover problem on certain instances, where we show that it leads to asymptotically better runtimes and even finds with higher probability optimal solutions in comparison with the usual (1+1) EA. Precisely, we compare the performance of both algorithms on paths and on complete bipartite graphs of size \(n\). Regarding the path we prove that, for a particular initial configuration, the (1+1) EA takes in expectation \(\Theta(n^4)\) iterations while the modification reduces this to \(\Theta(n^3)\), and present experimental evidence that such a configuration is reached. Concerning the complete bipartite graph our modification finds the optimum in polynomial time with probability \(1-1/2^{\Omega(n^\xi)}\) for every positive constant \(\xi < 1\), which improves the known probability of \(1-1/\)poly\((n)\) for the (1+1) EA.}, author = {Baguley, Samuel and Friedrich, Tobias and Timo, Kötzing and Li, Xiaoyue and Pappik, Marcus and Zeif, Ziena}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {sys:relevantfor:ae zienazeif marcuspappik samuelbaguley xiaoyueli timokoetzing tobiasfriedrich gecco year2022}, pages = {1363&ndash;1371}, title = {Analysis of a Gray-Box Operator for Vertex Cover}, year = 2022 }

Friedrich, Tobias; Kötzing, Timo; Radhakrishnan, Aishwarya; Schiller, Leon; Schirneck, Martin; Tennigkeit, Georg; Wietheger, Simon Crossover for Cardinality Constrained OptimizationGenetic and Evolutionary Computation Conference (GECCO) 2022: 1399–1407
Best Paper Award (Theory Track)
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In order to understand better how and why crossover can benefit optimization, we consider pseudo-Boolean functions with an upper bound \(B\) on the number of 1s allowed in the bit string (cardinality constraint). We consider the natural translation of the OneMax test function, a linear function where \(B\) bits have a weight of \(1+\varepsilon\) and the remaining bits have a weight of \(1\). The literature gives a bound of \(\Theta(n^2)\) for the (1+1) EA on this function. Part of the difficulty when optimizing this problem lies in having to improve individuals meeting the cardinality constraint by flipping both a 1 and a 0. The experimental literature proposes balanced operators, preserving the number of 1s, as a remedy. We show that a balanced mutation operator optimizes the problem in \(O(n \log n)\) if \(n-B = O(1)\). However, if \(n-B = \Theta(n)\), we show a bound of \(\Omega(n^2)\), just as classic bit flip mutation. Crossover and a simple island model gives \(O(n^2 / \log n)\) (uniform crossover) and \(O(n\sqrt{n})\) (3-ary majority vote crossover). For balanced uniform crossover with Hamming distance maximization for diversity we show a bound of \(O(n \log n)\). As an additional contribution we analyze and discuss different balanced crossover operators from the literature.
@inproceedings{friedrich2022crossover, abstract = {In order to understand better how and why crossover can benefit optimization, we consider pseudo-Boolean functions with an upper bound \(B\) on the number of 1s allowed in the bit string (cardinality constraint). We consider the natural translation of the OneMax test function, a linear function where \(B\) bits have a weight of \(1+\varepsilon\) and the remaining bits have a weight of \(1\). The literature gives a bound of \(\Theta(n^2)\) for the (1+1) EA on this function. Part of the difficulty when optimizing this problem lies in having to improve individuals meeting the cardinality constraint by flipping both a 1 and a 0. The experimental literature proposes balanced operators, preserving the number of 1s, as a remedy. We show that a balanced mutation operator optimizes the problem in \(O(n \log n)\) if \(n-B = O(1)\). However, if \(n-B = \Theta(n)\), we show a bound of \(\Omega(n^2)\), just as classic bit flip mutation. Crossover and a simple island model gives \(O(n^2 / \log n)\) (uniform crossover) and \(O(n\sqrt{n})\) (3-ary majority vote crossover). For balanced uniform crossover with Hamming distance maximization for diversity we show a bound of \(O(n \log n)\). As an additional contribution we analyze and discuss different balanced crossover operators from the literature.}, author = {Friedrich, Tobias and Kötzing, Timo and Radhakrishnan, Aishwarya and Schiller, Leon and Schirneck, Martin and Tennigkeit, Georg and Wietheger, Simon}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {aishwaryaradhakrishnan timokoetzing simonwietheger tobiasfriedrich gecco leonschiller year2022 georgtennigkeit martinschirneck}, note = {Best Paper Award (Theory Track)}, pages = {1399&ndash;1407}, title = {Crossover for Cardinality Constrained Optimization}, year = 2022 }

Wood, Andrew; Hershcovitch, Moshik; Ennmouri, Ilias; Zong, Weiyu; Chennuri, Saurav; Cohen, Sarel; Sundararaman, Swaminathan; Waddington, Daniel; Chin, Peter Towards Fast Crash-Consistent Cluster CheckpointingHigh Performance Extreme Computing Conference (HPEC) 2022
[ Abstract ] [ BibTeX ] [ Download ]
 
Machine Learning models are expensive to train: they require expensive high-compute hardware and have long training times. Therefore, models are extra sensitive to program faults or unexpected system crashes, which can erase hours if not days worth of work. While there are plenty of strategies designed to mitigate the risk of unexpected system downtime, the most popular strategy in machine learning is called checkpointing: periodically saving the state of the model to persistent storage. Checkpointing is an effective strategy, however, it requires carefully balancing two operations: how often a checkpoint is made (the checkpointing schedule), and the cost of creating a checkpoint itself. In this paper, we leverage Python Memory Manager (PyMM), which provides Python support for Persistent Memory and emerging Persistent Memory technology (Optane DC) to accelerate the checkpointing operation while maintaining crash consistency. We first show that when checkpointing models, PyMM with persistent memory can save from minutes to days of checkpointing runtime. We then further optimize the checkpointing operation with PyMM and demonstrate our approach with the KMeans and Gaussian Mixture Model algorithms on two real-world datasets: MNIST and MusicNet. Through evaluation, we show that these two algorithms achieve a checkpointing speedup of a factor between 10 and 75x for KMeans and over 3x for GMM against the current state-of-the-art checkpointing approaches. We also verify that our solution recovers from crashes, while traditional approaches cannot.
@inproceedings{wood2022towards, abstract = {Machine Learning models are expensive to train: they require expensive high-compute hardware and have long training times. Therefore, models are extra sensitive to program faults or unexpected system crashes, which can erase hours if not days worth of work. While there are plenty of strategies designed to mitigate the risk of unexpected system downtime, the most popular strategy in machine learning is called checkpointing: periodically saving the state of the model to persistent storage. Checkpointing is an effective strategy, however, it requires carefully balancing two operations: how often a checkpoint is made (the checkpointing schedule), and the cost of creating a checkpoint itself. In this paper, we leverage Python Memory Manager (PyMM), which provides Python support for Persistent Memory and emerging Persistent Memory technology (Optane DC) to accelerate the checkpointing operation while maintaining crash consistency. We first show that when checkpointing models, PyMM with persistent memory can save from minutes to days of checkpointing runtime. We then further optimize the checkpointing operation with PyMM and demonstrate our approach with the KMeans and Gaussian Mixture Model algorithms on two real-world datasets: MNIST and MusicNet. Through evaluation, we show that these two algorithms achieve a checkpointing speedup of a factor between 10 and 75x for KMeans and over 3x for GMM against the current state-of-the-art checkpointing approaches. We also verify that our solution recovers from crashes, while traditional approaches cannot.}, author = {Wood, Andrew and Hershcovitch, Moshik and Ennmouri, Ilias and Zong, Weiyu and Chennuri, Saurav and Cohen, Sarel and Sundararaman, Swaminathan and Waddington, Daniel and Chin, Peter}, booktitle = {High Performance Extreme Computing Conference (HPEC)}, keywords = {sarelcohen hpec year2022}, title = {Towards Fast Crash-Consistent Cluster Checkpointing}, year = 2022 }

Friedrich, Tobias; Gawendowicz, Hans; Lenzner, Pascal; Melnichenko, Anna Social Distancing Network CreationInternational Colloquium on Automata, Languages and Programming (ICALP) 2022: 62:1–62:21
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
During a pandemic people have to find a trade-off between meeting others and staying safely at home. While meeting others is pleasant, it also increases the risk of infection. We consider this dilemma by introducing a game-theoretic network creation model in which selfish agents can form bilateral connections. They benefit from network neighbors, but at the same time, they want to maximize their distance to all other agents. This models the inherent conflict that social distancing rules impose on the behavior of selfish agents in a social network. Besides addressing this familiar issue, our model can be seen as the inverse to the well-studied Network Creation Game by Fabrikant et al.~[PODC 2003] where agents aim at being as central as possible in the created network. Thus, our work is in-line with studies that compare minimization problems with their maximization versions. We look at two variants of network creation governed by social distancing. In the first variant, there are no restrictions on the connections being formed. We characterize optimal and equilibrium networks, and we derive asymptotically tight bounds on the Price of Anarchy and Price of Stability. The second variant is the model's generalization that allows restrictions on the connections that can be formed. As our main result, we prove that Swap-Maximal Routing-Cost Spanning Trees, an efficiently computable weaker variant of Maximum Routing-Cost Spanning Trees, actually resemble equilibria for a significant range of the parameter space. Moreover, we give almost tight bounds on the Price of Anarchy and Price of Stability. These results imply that, compared the well-studied inverse models, under social distancing the agents' selfish behavior has a significantly stronger impact on the quality of the equilibria, i.e., allowing socially much worse stable states.
@inproceedings{friedrich2022social, abstract = {During a pandemic people have to find a trade-off between meeting others and staying safely at home. While meeting others is pleasant, it also increases the risk of infection. We consider this dilemma by introducing a game-theoretic network creation model in which selfish agents can form bilateral connections. They benefit from network neighbors, but at the same time, they want to maximize their distance to all other agents. This models the inherent conflict that social distancing rules impose on the behavior of selfish agents in a social network. Besides addressing this familiar issue, our model can be seen as the inverse to the well-studied Network Creation Game by Fabrikant et al.&nbsp;[PODC 2003] where agents aim at being as central as possible in the created network. Thus, our work is in-line with studies that compare minimization problems with their maximization versions. We look at two variants of network creation governed by social distancing. In the first variant, there are no restrictions on the connections being formed. We characterize optimal and equilibrium networks, and we derive asymptotically tight bounds on the Price of Anarchy and Price of Stability. The second variant is the model's generalization that allows restrictions on the connections that can be formed. As our main result, we prove that Swap-Maximal Routing-Cost Spanning Trees, an efficiently computable weaker variant of Maximum Routing-Cost Spanning Trees, actually resemble equilibria for a significant range of the parameter space. Moreover, we give almost tight bounds on the Price of Anarchy and Price of Stability. These results imply that, compared the well-studied inverse models, under social distancing the agents' selfish behavior has a significantly stronger impact on the quality of the equilibria, i.e., allowing socially much worse stable states.}, author = {Friedrich, Tobias and Gawendowicz, Hans and Lenzner, Pascal and Melnichenko, Anna}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {hansgawendowicz tobiasfriedrich icalp annamelnichenko year2022 pascallenzner}, pages = {62:1&ndash;62:21}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{{ü}}r Informatik}, title = {Social Distancing Network Creation}, volume = {LIPIcs:229}, year = 2022 }

Bilò, Davide; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Schirneck, Martin Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs DistancesInternational Colloquium on Automata, Languages and Programming (ICALP) 2022: 68:1–68:19
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We construct data structures for extremal and pairwise distances in directed graphs in the presence of transient edge failures. Henzinger et al. (ITCS 2017) initiated the study of fault-tolerant (sensitivity) oracles for the diameter and vertex eccentricities. We extend this with a special focus on space efficiency. We present several new data structures, among them the first fault-tolerant eccentricity oracle for dual failures in subcubic space. We further prove lower bounds that show limits to approximation vs. space and diameter vs. space trade-offs for fault-tolerant oracles. They highlight key differences between data structures for undirected and directed graphs. Initially, our oracles are randomized leaning on a sampling technique frequently used in sensitivity analysis. Building on the work of Alon, Chechik, and Cohen (ICALP 2019) as well as Karthik and Parter (SODA 2021), we develop a hierarchical framework to derandomize fault-tolerant data structures. We first apply it to our own diameter/eccentricity oracles and then show its usefulness by derandomizing algorithms from the literature: the distance sensitivity oracle of Ren (JCSS 2022) and the Single-Source Replacement Path algorithm of Chechik and Magen (ICALP 2020).
@inproceedings{bilo2022deterministic, abstract = {We construct data structures for extremal and pairwise distances in directed graphs in the presence of transient edge failures. Henzinger et al. (ITCS 2017) initiated the study of fault-tolerant (sensitivity) oracles for the diameter and vertex eccentricities. We extend this with a special focus on space efficiency. We present several new data structures, among them the first fault-tolerant eccentricity oracle for dual failures in subcubic space. We further prove lower bounds that show limits to approximation vs. space and diameter vs. space trade-offs for fault-tolerant oracles. They highlight key differences between data structures for undirected and directed graphs. Initially, our oracles are randomized leaning on a sampling technique frequently used in sensitivity analysis. Building on the work of Alon, Chechik, and Cohen (ICALP 2019) as well as Karthik and Parter (SODA 2021), we develop a hierarchical framework to derandomize fault-tolerant data structures. We first apply it to our own diameter/eccentricity oracles and then show its usefulness by derandomizing algorithms from the literature: the distance sensitivity oracle of Ren (JCSS 2022) and the Single-Source Replacement Path algorithm of Chechik and Magen (ICALP 2020).}, author = {Bilò, Davide and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Schirneck, Martin}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {sarelcohen davidebilo tobiasfriedrich icalp keertichoudhary year2022 martinschirneck}, pages = {68:1-68:19}, title = {Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances}, year = 2022 }

Böther, Maximilian; Kißig, Otto; Taraz, Martin; Cohen, Sarel; Seidel, Karen; Friedrich, Tobias What’s Wrong with Deep Learning in Tree Search for Combinatorial OptimizationInternational Conference on Learning Representations (ICLR) 2022
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Combinatorial optimization lies at the core of many real-world problems. Especially since the rise of graph neural networks (GNNs), the deep learning community has been developing solvers that derive solutions to NP-hard problems by learning the problem-specific solution structure. However, reproducing the results of these publications proves to be difficult. We make three contributions. First, we present an open-source benchmark suite for the NP-hard Maximum Independent Set problem, in both its weighted and unweighted variants. The suite offers a unified interface to various state-of-the-art traditional and machine learning-based solvers. Second, using our benchmark suite, we conduct an in-depth analysis of the popular guided tree search algorithm by Li et al. [NeurIPS 2018], testing various configurations on small and large synthetic and real-world graphs. By re-implementing their algorithm with a focus on code quality and extensibility, we show that the graph convolution network used in the tree search does not learn a meaningful representation of the solution structure, and can in fact be replaced by random values. Instead, the tree search relies on algorithmic techniques like graph kernelization to find good solutions. Thus, the results from the original publication are not reproducible. Third, we extend the analysis to compare the tree search implementations to other solvers, showing that the classical algorithmic solvers often are faster, while providing solutions of similar quality. Additionally, we analyze a recent solver based on reinforcement learning and observe that for this solver, the GNN is responsible for the competitive solution quality.
@inproceedings{bother2022whats, abstract = {Combinatorial optimization lies at the core of many real-world problems. Especially since the rise of graph neural networks (GNNs), the deep learning community has been developing solvers that derive solutions to NP-hard problems by learning the problem-specific solution structure. However, reproducing the results of these publications proves to be difficult. We make three contributions. First, we present an open-source benchmark suite for the NP-hard Maximum Independent Set problem, in both its weighted and unweighted variants. The suite offers a unified interface to various state-of-the-art traditional and machine learning-based solvers. Second, using our benchmark suite, we conduct an in-depth analysis of the popular guided tree search algorithm by Li et al. [NeurIPS 2018], testing various configurations on small and large synthetic and real-world graphs. By re-implementing their algorithm with a focus on code quality and extensibility, we show that the graph convolution network used in the tree search does not learn a meaningful representation of the solution structure, and can in fact be replaced by random values. Instead, the tree search relies on algorithmic techniques like graph kernelization to find good solutions. Thus, the results from the original publication are not reproducible. Third, we extend the analysis to compare the tree search implementations to other solvers, showing that the classical algorithmic solvers often are faster, while providing solutions of similar quality. Additionally, we analyze a recent solver based on reinforcement learning and observe that for this solver, the GNN is responsible for the competitive solution quality.}, author = {Böther, Maximilian and Kißig, Otto and Taraz, Martin and Cohen, Sarel and Seidel, Karen and Friedrich, Tobias}, booktitle = {International Conference on Learning Representations (ICLR)}, keywords = {maximilianboether sarelcohen ottokissig tobiasfriedrich martintaraz year2022 iclr karenseidel}, title = {What’s Wrong with Deep Learning in Tree Search for Combinatorial Optimization}, year = 2022 }

Bilò, Davide; Bilò, Vittorio; Lenzner, Pascal; Molitor, Louise Tolerance is Necessary for Stability: Single-Peaked Swap Schelling GamesInternational Joint Conference on Artificial Intelligence (IJCAI) 2022: 81–87
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Residential segregation in metropolitan areas is a phenomenon that can be observed all over the world. Recently, this was investigated via game-theoretic models. There, selfish agents of two types are equipped with a monotone utility function that ensures higher utility if an agent has more same-type neighbors. The agents strategically choose their location on a given graph that serves as residential area to maximize their utility. However, sociological polls suggest that real-world agents are actually favoring mixed-type neighborhoods, and hence should be modeled via non-monotone utility functions. To address this, we study Swap Schelling Games with single-peaked utility functions. Our main finding is that tolerance, i.e., agents favoring fifty-fifty neighborhoods or being in the minority, is necessary for equilibrium existence on almost regular or bipartite graphs. Regarding the quality of equilibria, we derive (almost) tight bounds on the Price of Anarchy and the Price of Stability. In particular, we show that the latter is constant on bipartite and almost regular graphs.
@inproceedings{bilo2022tolerance, abstract = {Residential segregation in metropolitan areas is a phenomenon that can be observed all over the world. Recently, this was investigated via game-theoretic models. There, selfish agents of two types are equipped with a monotone utility function that ensures higher utility if an agent has more same-type neighbors. The agents strategically choose their location on a given graph that serves as residential area to maximize their utility. However, sociological polls suggest that real-world agents are actually favoring mixed-type neighborhoods, and hence should be modeled via non-monotone utility functions. To address this, we study Swap Schelling Games with single-peaked utility functions. Our main finding is that tolerance, i.e., agents favoring fifty-fifty neighborhoods or being in the minority, is necessary for equilibrium existence on almost regular or bipartite graphs. Regarding the quality of equilibria, we derive (almost) tight bounds on the Price of Anarchy and the Price of Stability. In particular, we show that the latter is constant on bipartite and almost regular graphs.}, author = {Bilò, Davide and Bilò, Vittorio and Lenzner, Pascal and Molitor, Louise}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {ijcai louisemolitor year2022 pascallenzner}, pages = {81&ndash;87}, publisher = {ijcai.org}, title = {Tolerance is Necessary for Stability: Single-Peaked Swap Schelling Games}, year = 2022 }

Bullinger, Martin; Lenzner, Pascal; Melnichenko, Anna Network Creation with Homophilic AgentsInternational Joint Conference on Artificial Intelligence (IJCAI) 2022: 151–157
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Network Creation Games are an important framework for understanding the formation of real-world networks such as social networks. These games usually assume a set of indistinguishable agents strategically buying edges at a uniform price leading to a network among them. However, in real life, agents are heterogeneous and their relationships often display a bias towards similar agents, say of the same ethnic group. This homophilic behavior on the agent level can then lead to the emergent global phenomenon of social segregation. We initiate the study of Network Creation Games with multiple types of homophilic agents and non-uniform edge cost. Specifically, we introduce and compare two models, focusing on the perception of same-type and different-type neighboring agents, respectively. Despite their different initial conditions, both our theoretical and experimental analysis show that the resulting equilibrium networks are almost identical in the two models, indicating a robust structure of social networks under homophily. Moreover, we investigate the segregation strength of the formed networks and thereby offer new insights on understanding segregation.
@inproceedings{bullinger2022network, abstract = {Network Creation Games are an important framework for understanding the formation of real-world networks such as social networks. These games usually assume a set of indistinguishable agents strategically buying edges at a uniform price leading to a network among them. However, in real life, agents are heterogeneous and their relationships often display a bias towards similar agents, say of the same ethnic group. This homophilic behavior on the agent level can then lead to the emergent global phenomenon of social segregation. We initiate the study of Network Creation Games with multiple types of homophilic agents and non-uniform edge cost. Specifically, we introduce and compare two models, focusing on the perception of same-type and different-type neighboring agents, respectively. Despite their different initial conditions, both our theoretical and experimental analysis show that the resulting equilibrium networks are almost identical in the two models, indicating a robust structure of social networks under homophily. Moreover, we investigate the segregation strength of the formed networks and thereby offer new insights on understanding segregation.}, author = {Bullinger, Martin and Lenzner, Pascal and Melnichenko, Anna}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {ijcai annamelnichenko year2022 pascallenzner}, pages = {151&ndash;157}, publisher = {ijcai.org}, title = {Network Creation with Homophilic Agents}, year = 2022 }

Bilò, Davide; Casel, Katrin; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Lagodzinski, J.A. Gregor; Schirneck, Martin; Wietheger, Simon Fixed-Parameter Sensitivity OraclesInnovations in Theoretical Computer Science (ITCS) 2022: 23:1–23:18
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We combine ideas from distance sensitivity oracles (DSOs) and fixed-parameter tractability (FPT) to design sensitivity oracles for FPT graph problems. An oracle with sensitivity \(f\) for an FPT problem \(\Pi\) on a graph \(G\) with parameter \(k\) preprocesses \(G\) in time \(O(g(f,k) poly(n))\). When queried with a set \(F\) of at most \(f\) edges of \(G\), the oracle reports the answer to the \(\Pi\)-with the same parameter \(k\)-on the graph \(G-F\), i.e., \(G\) deprived of \(F\). The oracle should answer queries in a time that is significantly faster than merely running the best-known FPT algorithm on \(G-F\) from scratch. We design sensitivity oracles for the \(k\)-Path and the \(k\)-Vertex Cover problem. Our first oracle for \(k\)-Path has size \(O(k^{f+1})\) size and query time \(O(f \min\{f, \log (f) + k\})\). We use a technique inspired by the work of Weimann and Yuster [FOCS 2010, TALG 2013] on distance sensitivity problems to reduce the space to \(O\big(\big(\frac{f+k}{f}\big)^f \big(\frac{f+k}{k}\big)^k fk \cdot \log n\big)\) at the expense of increasing the query time to \(O\big(\big(\frac{f+k}{f}\big)^f \big(\frac{f+k}{k}\big)^k f \min\{f,k\} \cdot \log n \big)\). Both oracles can be modified to handle vertex-failures, but we need to replace \(k\) with \(2k\) in all the claimed bounds. Regarding \(k\)-Vertex Cover, we design three oracles offering different trade-offs between the size and the query time. The first oracle takes \(O(3^{f+k})\) space and has \(O(2^f)\) query time, the second one has a size of \(O(2^{f+k^2+k})\) and a query time of \(O(f{+}k^2)\); finally, the third one takes \(O(fk+k^2)\) space and can be queried in time \(O(1.2738^k + fk^2)\). All our oracles are computable in time (at most) proportional to their size and the time needed to detect a \(k\)-path or \(k\)-vertex cover, respectively. We also provide an interesting connection between \(k\)-Vertex Cover and the fault-tolerant shortest path problem, by giving a DSO of size \(O(poly(f,k) \cdot n)\) with query time in \(O(poly(f,k))\), where \(k\) is the size of a vertex cover. Following our line of research connecting fault-tolerant FPT and shortest paths problems, we introduce parameterization to the computation of distance preservers. Given a graph with a fixed source \(s\) and parameters \(f\),\(k\), we study the problem of constructing polynomial-sized oracles that reports efficiently, for any target vertex \(v\) and set \(F\) of at most \(f\) edge failures, whether the distance from \(s\) to \(v\) increases at most by an additive term of \(k\) in \(G-F\). The oracle size is \(O(2^k k^2 \cdot n)\), while the time needed to answer a query is \(O(2^k f^\omega k^\omega)\), where \(\omega<2.373\) is the matrix multiplication exponent. The second problem we study is about the construction of bounded-stretch fault-tolerant preservers. We construct a subgraph with \(O(2^{fk+f+k} k \cdot n)\) edges that preserves those \(s\)-\(v\)-distances that do not increase by more than \(k\) upon failure of \(F\). This improves significantly over the \( \tilde{O} (f n^{2-\frac{1}{2^f}}) \) bound in the unparameterized case by Bodwin et al. [ICALP 2017].
@inproceedings{bilo2022fixedparameter, abstract = {We combine ideas from distance sensitivity oracles (DSOs) and fixed-parameter tractability (FPT) to design sensitivity oracles for FPT graph problems. An oracle with sensitivity \(f\) for an FPT problem \(\Pi\) on a graph \(G\) with parameter \(k\) preprocesses \(G\) in time \(O(g(f,k) poly(n))\). When queried with a set \(F\) of at most \(f\) edges of \(G\), the oracle reports the answer to the \(\Pi\)-with the same parameter \(k\)-on the graph \(G-F\), i.e., \(G\) deprived of \(F\). The oracle should answer queries in a time that is significantly faster than merely running the best-known FPT algorithm on \(G-F\) from scratch. We design sensitivity oracles for the \(k\)-Path and the \(k\)-Vertex Cover problem. Our first oracle for \(k\)-Path has size \(O(k^{f+1})\) size and query time \(O(f \min\{f, \log (f) + k\})\). We use a technique inspired by the work of Weimann and Yuster [FOCS 2010, TALG 2013] on distance sensitivity problems to reduce the space to \(O\big(\big(\frac{f+k}{f}\big)^f \big(\frac{f+k}{k}\big)^k fk \cdot \log n\big)\) at the expense of increasing the query time to \(O\big(\big(\frac{f+k}{f}\big)^f \big(\frac{f+k}{k}\big)^k f \min\{f,k\} \cdot \log n \big)\). Both oracles can be modified to handle vertex-failures, but we need to replace \(k\) with \(2k\) in all the claimed bounds. Regarding \(k\)-Vertex Cover, we design three oracles offering different trade-offs between the size and the query time. The first oracle takes \(O(3^{f+k})\) space and has \(O(2^f)\) query time, the second one has a size of \(O(2^{f+k^2+k})\) and a query time of \(O(f{+}k^2)\); finally, the third one takes \(O(fk+k^2)\) space and can be queried in time \(O(1.2738^k + fk^2)\). All our oracles are computable in time (at most) proportional to their size and the time needed to detect a \(k\)-path or \(k\)-vertex cover, respectively. We also provide an interesting connection between \(k\)-Vertex Cover and the fault-tolerant shortest path problem, by giving a DSO of size \(O(poly(f,k) \cdot n)\) with query time in \(O(poly(f,k))\), where \(k\) is the size of a vertex cover. Following our line of research connecting fault-tolerant FPT and shortest paths problems, we introduce parameterization to the computation of distance preservers. Given a graph with a fixed source \(s\) and parameters \(f\),\(k\), we study the problem of constructing polynomial-sized oracles that reports efficiently, for any target vertex \(v\) and set \(F\) of at most \(f\) edge failures, whether the distance from \(s\) to \(v\) increases at most by an additive term of \(k\) in \(G-F\). The oracle size is \(O(2^k k^2 \cdot n)\), while the time needed to answer a query is \(O(2^k f^\omega k^\omega)\), where \(\omega<2.373\) is the matrix multiplication exponent. The second problem we study is about the construction of bounded-stretch fault-tolerant preservers. We construct a subgraph with \(O(2^{fk+f+k} k \cdot n)\) edges that preserves those \(s\)-\(v\)-distances that do not increase by more than \(k\) upon failure of \(F\). This improves significantly over the \( \tilde{O} (f n^{2-\frac{1}{2^f}}) \) bound in the unparameterized case by Bodwin et al. [ICALP 2017].}, author = {Bilò, Davide and Casel, Katrin and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Lagodzinski, J.A. Gregor and Schirneck, Martin and Wietheger, Simon}, booktitle = {Innovations in Theoretical Computer Science (ITCS)}, keywords = {sarelcohen gregorlagodzinski davidebilo katrincasel simonwietheger tobiasfriedrich itcs keertichoudhary year2022 martinschirneck}, pages = {23:1-23:18}, title = {Fixed-Parameter Sensitivity Oracles}, year = 2022 }

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Rajabi, Amirhossein Escaping Local Optima With Local Search: A Theory-Driven DiscussionParallel Problem Solving from Nature (PPSN) 2022: 442–455
Best Paper Award and Best Poster Award
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Local search is the most basic strategy in optimization settings when no specific problem knowledge is employed. While this strategy finds good solutions for certain optimization problems, it generally suffers from getting stuck in local optima. This stagnation can be avoided if local search is modified. Depending on the optimization landscape, different modifications vary in their success. We discuss several features of optimization landscapes and give analyses as examples for how they affect the performance of modifications of local search. We consider modifying random local search by restarting it and by considering larger search radii. The landscape features we analyze include the number of local optima, the distance between different optima, as well as the local landscape around a local optimum. For each feature, we show which modifications of local search handle them well and which do not.
@inproceedings{friedrich2022escaping, abstract = {Local search is the most basic strategy in optimization settings when no specific problem knowledge is employed. While this strategy finds good solutions for certain optimization problems, it generally suffers from getting stuck in local optima. This stagnation can be avoided if local search is modified. Depending on the optimization landscape, different modifications vary in their success. We discuss several features of optimization landscapes and give analyses as examples for how they affect the performance of modifications of local search. We consider modifying random local search by restarting it and by considering larger search radii. The landscape features we analyze include the number of local optima, the distance between different optima, as well as the local landscape around a local optimum. For each feature, we show which modifications of local search handle them well and which do not.}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Rajabi, Amirhossein}, booktitle = {Parallel Problem Solving from Nature (PPSN)}, keywords = {martinskrejca timokoetzing tobiasfriedrich amirhosseinrajabi year2022 ppsn}, note = {Best Paper Award and Best Poster Award}, pages = {442-455}, title = {Escaping Local Optima With Local Search: A Theory-Driven Discussion}, year = 2022 }

Friedrich, Tobias; Kötzing, Timo; Neumann, Frank; Radhakrishnan, Aishwarya Theoretical Study of Optimizing Rugge Landscapes with the cGAParallel Problem Solving From Nature (PPSN) 2022: 586–599
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Estimation of distribution algorithms (EDAs) provide a distribution-based approach for optimization which adapts its probability distribution during the run of the algorithm. We contribute to the theoretical understanding of EDAs and point out that their distribution approach makes them more suitable to deal with rugged fitness landscapes than classical local search algorithms. Concretely, we make the OneMax function rugged by adding noise to each fitness value. The cGA can nevertheless find solutions with \(n (1 - \epsilon )\) many 1s, even for high variance of noise. In contrast to this, RLS and the (1+1) EA, with high probability, only find solutions with \(n(1/2 + o(1)) \) many 1s, even for noise with small variance.
@inproceedings{friedrich2022theoretical, abstract = {Estimation of distribution algorithms (EDAs) provide a distribution-based approach for optimization which adapts its probability distribution during the run of the algorithm. We contribute to the theoretical understanding of EDAs and point out that their distribution approach makes them more suitable to deal with rugged fitness landscapes than classical local search algorithms. Concretely, we make the OneMax function rugged by adding noise to each fitness value. The cGA can nevertheless find solutions with \(n (1 - \epsilon )\) many 1s, even for high variance of noise. In contrast to this, RLS and the (1+1) EA, with high probability, only find solutions with \(n(1/2 + o(1)) \) many 1s, even for noise with small variance.}, author = {Friedrich, Tobias and Kötzing, Timo and Neumann, Frank and Radhakrishnan, Aishwarya}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, keywords = {aishwaryaradhakrishnan timokoetzing tobiasfriedrich frankneumann year2022 ppsn}, pages = {586–599}, title = {Theoretical Study of Optimizing Rugge Landscapes with the cGA}, year = 2022 }

Bläsius, Thomas; Fischbeck, Philipp; Gottesbüren, Lars; Hamann, Michael; Heuer, Tobias; Spinner, Jonas; Weyand, Christopher; Wilhelm, Marcus A Branch-and-Bound Algorithm for Cluster EditingSymposium on Experimental Algorithms (SEA) 2022: 13:1–13:19
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The editing problem asks to transform a given graph into a disjoint union of cliques by inserting and deleting as few edges as possible. We describe and evaluate an exact branch-and-bound algorithm for cluster editing. For this, we introduce new reduction rules and adapt existing ones. Moreover, we generalize a known packing technique to obtain lower bounds and experimentally show that it contributes significantly to the performance of the solver. Our experiments further evaluate the effectiveness of the different reduction rules and examine the effects of structural properties of the input graph on solver performance. Our solver won the exact track of the 2021 PACE challenge.
@inproceedings{blasius2022branchandbound, abstract = {The editing problem asks to transform a given graph into a disjoint union of cliques by inserting and deleting as few edges as possible. We describe and evaluate an exact branch-and-bound algorithm for cluster editing. For this, we introduce new reduction rules and adapt existing ones. Moreover, we generalize a known packing technique to obtain lower bounds and experimentally show that it contributes significantly to the performance of the solver. Our experiments further evaluate the effectiveness of the different reduction rules and examine the effects of structural properties of the input graph on solver performance. Our solver won the exact track of the 2021 PACE challenge.}, author = {Bläsius, Thomas and Fischbeck, Philipp and Gottesbüren, Lars and Hamann, Michael and Heuer, Tobias and Spinner, Jonas and Weyand, Christopher and Wilhelm, Marcus}, booktitle = {Symposium on Experimental Algorithms (SEA)}, keywords = {philippfischbeck larsgottesbueren thomasblaesius michaelhamann tobiasheuer christopherweyand year2022 marcuswilhelm jonasspinner sea}, pages = {13:1&ndash;13:19}, title = {A Branch-and-Bound Algorithm for Cluster Editing}, year = 2022 }

Cohen, Sarel; Fischbeck, Philipp; Friedrich, Tobias; Krejca, Martin S.; Sauerwald, Thomas Accelerated Information Dissemination on Networks with Local and Global EdgesStructural Information and Communication Complexity (SIROCCO) 2022: 79–97
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Bootstrap percolation is a classical model for the spread of information in a network. In the round-based version, nodes of an undirected graph become active once at least \(r\) neighbors were active in the previous round. We propose the \emph{perturbed} percolation process: a superposition of two percolation processes on the same node set. One process acts on a local graph with activation threshold~\(1\), the other acts on a global graph with threshold \(r\)~-- representing local and global edges, respectively. We consider grid-like local graphs and expanders as global graphs on~\(n\) nodes. For the extreme case \(r = 1\), all nodes are active after \(O(\log n)\) rounds, while the process spreads only polynomially fast for the other extreme case \(r \geq n\). For a range of suitable values of~\(r\), we prove that the process exhibits both phases of the above extremes: It starts with a polynomial growth and eventually transitions from at most \(cn\) to~\(n\) active nodes, for some constant \(c \in (0, 1)\), in \(O(\log n)\) rounds. We observe this behavior also empirically, considering additional global-graph models.
@inproceedings{cohen2022accelerated, abstract = {Bootstrap percolation is a classical model for the spread of information in a network. In the round-based version, nodes of an undirected graph become active once at least \(r\) neighbors were active in the previous round. We propose the \emph{perturbed} percolation process: a superposition of two percolation processes on the same node set. One process acts on a local graph with activation threshold&nbsp;\(1\), the other acts on a global graph with threshold \(r\)&nbsp;&ndash; representing local and global edges, respectively. We consider grid-like local graphs and expanders as global graphs on&nbsp;\(n\) nodes. For the extreme case \(r = 1\), all nodes are active after \(O(\log n)\) rounds, while the process spreads only polynomially fast for the other extreme case \(r \geq n\). For a range of suitable values of&nbsp;\(r\), we prove that the process exhibits both phases of the above extremes: It starts with a polynomial growth and eventually transitions from at most \(cn\) to&nbsp;\(n\) active nodes, for some constant \(c \in (0, 1)\), in \(O(\log n)\) rounds. We observe this behavior also empirically, considering additional global-graph models.}, author = {Cohen, Sarel and Fischbeck, Philipp and Friedrich, Tobias and Krejca, Martin S. and Sauerwald, Thomas}, booktitle = {Structural Information and Communication Complexity (SIROCCO)}, keywords = {sarelcohen philippfischbeck martinskrejca sirocco tobiasfriedrich year2022 thomassauerwald}, pages = {79&ndash;97}, title = {Accelerated Information Dissemination on Networks with Local and Global Edges}, year = 2022 }

Fomin, Fedor V.; Golovach, Petr A.; Sagunov, Danil; Simonov, Kirill Algorithmic Extensions of Dirac’s TheoremSymposium on Discrete Algorithms (SODA) 2022: 406–416
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is a randomized algorithm, that given a colored \(n\)-vertex undirected graph, vertices \(s\) and \(t\), and an integer \(k\), finds an \((s,t)\)-path containing at least \(k\) different colors in time \(2^k n^{\mathcal{O}(1)}\). This is the first FPT algorithm for this problem, and it generalizes the algorithm of Bj{ö}rklund, Husfeldt, and Taslaman [SODA 2012] on finding a path through \(k\) specified vertices. It also implies the first \(2^k n^{\mathcal{O}(1)}\) time algorithm for finding an \(s,t)\)-path of length at least \(k\). Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an \(n\)-vertex undirected graph \(G\), a matroid \(M\) whose elements correspond to the vertices of \(G\) and which is represented over a finite field of order \(q\), a positive integer weight function on the vertices of \(G\), two sets of vertices \(S,T \subseteq V(G)\), and integers \(p,k,w\), and the task is to find \(p\) vertex-disjoint paths from \(S\) to \(T\) so that the union of the vertices of these paths contains an independent set of \(M\) of cardinality \(k\) and weight \(w\), while minimizing the sum of the lengths of the paths. We give a \(2^{p+\mathcal{O}(k^2 \log (q+k))} n^{\mathcal{O}(1)} w\) time randomized algorithm for this problem.
@inproceedings{fomin2022algorithmic, abstract = {We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is a randomized algorithm, that given a colored \(n\)-vertex undirected graph, vertices \(s\) and \(t\), and an integer \(k\), finds an \((s,t)\)-path containing at least \(k\) different colors in time \(2^k n^{\mathcal{O}(1)}\). This is the first FPT algorithm for this problem, and it generalizes the algorithm of Bj{ö}rklund, Husfeldt, and Taslaman [SODA 2012] on finding a path through \(k\) specified vertices. It also implies the first \(2^k n^{\mathcal{O}(1)}\) time algorithm for finding an \(s,t)\)-path of length at least \(k\). Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an \(n\)-vertex undirected graph \(G\), a matroid \(M\) whose elements correspond to the vertices of \(G\) and which is represented over a finite field of order \(q\), a positive integer weight function on the vertices of \(G\), two sets of vertices \(S,T \subseteq V(G)\), and integers \(p,k,w\), and the task is to find \(p\) vertex-disjoint paths from \(S\) to \(T\) so that the union of the vertices of these paths contains an independent set of \(M\) of cardinality \(k\) and weight \(w\), while minimizing the sum of the lengths of the paths. We give a \(2^{p+\mathcal{O}(k^2 \log (q+k))} n^{\mathcal{O}(1)} w\) time randomized algorithm for this problem.}, author = {Fomin, Fedor V. and Golovach, Petr A. and Sagunov, Danil and Simonov, Kirill}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {sys:relevantfor:ae kirillsimonov soda year2022}, pages = {406-416}, title = {Algorithmic Extensions of Dirac's Theorem}, year = 2022 }

Bazgan, Cristina; Casel, Katrin; Cazals, Pierre Dense Graph Partitioning on sparse and dense graphs.Scandinavian Workshop Algorithm Theory (SWAT) 2022
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We consider the problem of partitioning a graph into a non-fixed number of non-overlapping subgraphs of maximum density. The density of a partition is the sum of the densities of the subgraphs, where the density of a subgraph is its average degree, that is, the ratio of its number of edges and its number of vertices. This problem, called Dense Graph Partition, is known to be NP-hard on general graphs and polynomial-time solvable on trees, and polynomial-time 2-approximable. In this paper we study the restriction of Dense Graph Partition to particular sparse and dense graph classes. In particular, we prove that it is NP-hard on dense bipartite graphs as well as on cubic graphs. On dense graphs on \(n\) vertices, it is polynomial-time solvable on graphs with minimum degree \(n-3\) and NP-hard on \((n-4)\)-regular graphs. We prove that it is polynomial-time 4/3-approximable on cubic graphs and admits an efficient polynomial-time approximation scheme on graphs of minimum degree \(n-t\) for any constant \(t\geq 4\).
@inproceedings{bazgan2022dense, abstract = {We consider the problem of partitioning a graph into a non-fixed number of non-overlapping subgraphs of maximum density. The density of a partition is the sum of the densities of the subgraphs, where the density of a subgraph is its average degree, that is, the ratio of its number of edges and its number of vertices. This problem, called Dense Graph Partition, is known to be NP-hard on general graphs and polynomial-time solvable on trees, and polynomial-time 2-approximable. In this paper we study the restriction of Dense Graph Partition to particular sparse and dense graph classes. In particular, we prove that it is NP-hard on dense bipartite graphs as well as on cubic graphs. On dense graphs on \(n\) vertices, it is polynomial-time solvable on graphs with minimum degree \(n-3\) and NP-hard on \((n-4)\)-regular graphs. We prove that it is polynomial-time 4/3-approximable on cubic graphs and admits an efficient polynomial-time approximation scheme on graphs of minimum degree \(n-t\) for any constant \(t\geq 4\).}, author = {Bazgan, Cristina and Casel, Katrin and Cazals, Pierre}, booktitle = {Scandinavian Workshop Algorithm Theory (SWAT)}, keywords = {swat katrincasel year2022}, title = {Dense Graph Partitioning on sparse and dense graphs.}, year = 2022 }

2022

Hacker, Philipp; Naumann, Felix; Friedrich, Tobias; Grundmann, Stefan; Lehmann, Anja AI Compliance - Challenges of Bridging Data Science and LawACM Journal of Data and Information Quality 2022
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
This vision paper outlines the main building blocks of what we term AI Compliance, an effort to bridge two complementary research areas: computer science and the law. Such research has the goal to model, measure, and affect the quality of AI artifacts, such as data, models and applications, to then facilitate adherence to legal standards.
@article{hacker2022compliance, abstract = {This vision paper outlines the main building blocks of what we term AI Compliance, an effort to bridge two complementary research areas: computer science and the law. Such research has the goal to model, measure, and affect the quality of AI artifacts, such as data, models and applications, to then facilitate adherence to legal standards.}, author = {Hacker, Philipp and Naumann, Felix and Friedrich, Tobias and Grundmann, Stefan and Lehmann, Anja}, journal = {ACM Journal of Data and Information Quality}, keywords = {myown tobiasfriedrich}, title = {AI Compliance - Challenges of Bridging Data Science and Law}, year = 2022 }

Bläsius, Thomas; Freiberger, Cedric; Friedrich, Tobias; Katzmann, Maximilian; Montenegro-Retana, Felix; Thieffry, Marianne Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic GeometryACM Transactions on Algorithms 2022: 1–32
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
A standard approach to accelerating shortest path algorithms on networks is the bidirectional search, which explores the graph from the start and the destination, simultaneously. In practice this strategy performs particularly well on scale-free real-world networks. Such networks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry. To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is \(\tilde{O}(n\)\(^{2 - 1/ \alpha}+\)\(n^{1/(2\alpha)}\)\(+ \delta_{\max})\) with high probability, where \(\alpha\)\(\in\)\((0.5, 1)\) controls the power-law exponent of the degree distribution, and \(\delta_{\max}\) is the maximum degree. This bound is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.
@article{blasius2022efficient, abstract = {A standard approach to accelerating shortest path algorithms on networks is the bidirectional search, which explores the graph from the start and the destination, simultaneously. In practice this strategy performs particularly well on scale-free real-world networks. Such networks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry. To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is \(\tilde{O}(n\)\(^{2 - 1/ \alpha}+\)\(n^{1/(2\alpha)}\)\(+ \delta_{\max})\) with high probability, where \(\alpha\)\(\in\)\((0.5, 1)\) controls the power-law exponent of the degree distribution, and \(\delta_{\max}\) is the maximum degree. This bound is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.}, author = {Bläsius, Thomas and Freiberger, Cedric and Friedrich, Tobias and Katzmann, Maximilian and Montenegro-Retana, Felix and Thieffry, Marianne}, journal = {ACM Transactions on Algorithms}, keywords = {sys:relevantfor:ae thomasblaesius tobiasfriedrich mariannethieffry cedricfreiberger maximiliankatzmann year2022 felixmontenegroretana}, pages = {1-32}, title = {Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry}, year = 2022 }

Bilò, Davide; Bilò, Vittorio; Lenzner, Pascal; Molitor, Louise Topological Influence and Locality in Swap Schelling GamesAutonomous Agents and Multi-Agent Systems (AGNT) 2022: 47
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Residential segregation is a wide-spread phenomenon that can be observed in almost every major city. In these urban areas residents with different racial or socioeconomic background tend to form homogeneous clusters. Schelling's famous agent-based model for residential segregation explains how such clusters can form even if all agents are tolerant, i.e., if they agree to live in mixed neighborhoods. For segregation to occur, all it needs is a slight bias towards agents preferring similar neighbors. Very recently, Schelling's model has been investigated from a game-theoretic point of view with selfish agents that strategically select their residential location. In these games, agents can improve on their current location by performing a location swap with another agent who is willing to swap. We significantly deepen these investigations by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy and on the dynamic properties of the resulting strategic multi-agent system. Moreover, as a new conceptual contribution, we also consider the influence of locality, i.e., if the location swaps are restricted to swaps of neighboring agents. We give improved almost tight bounds on the Price of Anarchy for arbitrary underlying graphs and we present (almost) tight bounds for regular graphs, paths and cycles. Moreover, we give almost tight bounds for grids, which are commonly used in empirical studies. For grids we also show that locality has a severe impact on the game dynamics.
@article{bilo2022topological, abstract = {Residential segregation is a wide-spread phenomenon that can be observed in almost every major city. In these urban areas residents with different racial or socioeconomic background tend to form homogeneous clusters. Schelling's famous agent-based model for residential segregation explains how such clusters can form even if all agents are tolerant, i.e., if they agree to live in mixed neighborhoods. For segregation to occur, all it needs is a slight bias towards agents preferring similar neighbors. Very recently, Schelling's model has been investigated from a game-theoretic point of view with selfish agents that strategically select their residential location. In these games, agents can improve on their current location by performing a location swap with another agent who is willing to swap. We significantly deepen these investigations by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy and on the dynamic properties of the resulting strategic multi-agent system. Moreover, as a new conceptual contribution, we also consider the influence of locality, i.e., if the location swaps are restricted to swaps of neighboring agents. We give improved almost tight bounds on the Price of Anarchy for arbitrary underlying graphs and we present (almost) tight bounds for regular graphs, paths and cycles. Moreover, we give almost tight bounds for grids, which are commonly used in empirical studies. For grids we also show that locality has a severe impact on the game dynamics.}, author = {Bilò, Davide and Bilò, Vittorio and Lenzner, Pascal and Molitor, Louise}, journal = {Autonomous Agents and Multi-Agent Systems (AGNT)}, keywords = {louisemolitor agnt year2022 pascallenzner}, number = 2, pages = 47, title = {Topological Influence and Locality in Swap Schelling Games}, volume = 36, year = 2022 }

Casel, Katrin; Fischbeck, Philipp; Friedrich, Tobias; Göbel, Andreas; Lagodzinski, J. A. Gregor Zeros and approximations of Holant polynomials on the complex planeComputational Complexity 2022: 11
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We present fully polynomial time approximation schemesfor a broad class of Holant problems with complex edge weights, which we call Holant polynomials. We transform these problems into partition functions of abstract combinatorial structures known as polymers in statistical physics. Our method involves establishing zero-free regions for the partition functions of polymer models and using the mostsignificant terms of the cluster expansion to approximate them. Results of our technique include new approximation and sampling algorithms for a diverse class of Holant polynomials in the low-temperature regime (i.e. small external field) and approximation algorithms for general Holant problems with small signature weights. Additionally, we give randomised approximation and sampling algorithms with faster running times for more restrictive classes. Finally, we improve the known zero-free regions for a perfect matching polynomial.
@article{casel2022zeros, abstract = {We present fully polynomial time approximation schemesfor a broad class of Holant problems with complex edge weights, which we call Holant polynomials. We transform these problems into partition functions of abstract combinatorial structures known as polymers in statistical physics. Our method involves establishing zero-free regions for the partition functions of polymer models and using the mostsignificant terms of the cluster expansion to approximate them. Results of our technique include new approximation and sampling algorithms for a diverse class of Holant polynomials in the low-temperature regime (i.e. small external field) and approximation algorithms for general Holant problems with small signature weights. Additionally, we give randomised approximation and sampling algorithms with faster running times for more restrictive classes. Finally, we improve the known zero-free regions for a perfect matching polynomial.}, author = {Casel, Katrin and Fischbeck, Philipp and Friedrich, Tobias and Göbel, Andreas and Lagodzinski, J. A. Gregor}, journal = {Computational Complexity}, keywords = {gregorlagodzinski philippfischbeck katrincasel andreasgoebel tobiasfriedrich year2022 cc}, number = 2, pages = 11, title = {Zeros and approximations of Holant polynomials on the complex plane}, volume = 31, year = 2022 }

Casel, Katrin; Fernau, Henning; Grigoriev, Alexander; Schmid, Markus L.; Whitesides, Sue Combinatorial Properties and Recognition of Unit Square Visibility GraphsDiscrete & Computational Geometry 2022
[ Abstract ] [ BibTeX ] [ Download ]
 
Unit square visibility graphs (USV) are described by axis-parallel visibility between unit squares placed in the plane. If the squares are required to be placed on integer grid coordinates, then USV become unit square grid visibility graphs (USGV), an alternative characterisation of the well-known rectilinear graphs. We extend known combinatorial results for USGV and we show that, in the weak case (i.e., visibilities do not necessarily translate into edges of the represented combinatorial graph), the area minimisation variant of their recognition problem is NP-hard. We also provide combinatorial insights with respect to USV, and as our main result, we prove their recognition problem to be \($\mathcal{NP}$\)-hard, which settles an open question.
@article{casel2022combinatorial, abstract = {Unit square visibility graphs (USV) are described by axis-parallel visibility between unit squares placed in the plane. If the squares are required to be placed on integer grid coordinates, then USV become unit square grid visibility graphs (USGV), an alternative characterisation of the well-known rectilinear graphs. We extend known combinatorial results for USGV and we show that, in the weak case (i.e., visibilities do not necessarily translate into edges of the represented combinatorial graph), the area minimisation variant of their recognition problem is NP-hard. We also provide combinatorial insights with respect to USV, and as our main result, we prove their recognition problem to be $\mathcal{NP}$-hard, which settles an open question.}, author = {Casel, Katrin and Fernau, Henning and Grigoriev, Alexander and Schmid, Markus L. and Whitesides, Sue}, journal = {Discrete \& Computational Geometry}, keywords = {katrincasel dcg year2022}, title = {Combinatorial Properties and Recognition of Unit Square Visibility Graphs}, year = 2022 }

Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, Martin Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data ProfilingJournal of Computer and System Sciences 2022: 192–213
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The transversal hypergraph problem asks to enumerate the minimal hitting sets of a hypergraph. If the solutions have bounded size, Eiter and Gottlob [SICOMP’95] gave an algorithm running in output-polynomial time, but whose space requirement also scales with the output. We improve this to polynomial delay and space. Central to our approach is the extension problem, deciding for a set X of vertices whether it is contained in any minimal hitting set. We show that this is one of the first natural problems to be W[3]-complete. We give an algorithm for the extension problem running in time O(m |X|+1 n) and prove a SETH-lower bound showing that this is close to optimal. We apply our enumeration method to the discovery problem of minimal unique column combinations from data profiling. Our empirical evaluation suggests that the algorithm outperforms its worst-case guarantees on hypergraphs stemming from real-world databases.
@article{Blaesius22Efficiently, abstract = {The transversal hypergraph problem asks to enumerate the minimal hitting sets of a hypergraph. If the solutions have bounded size, Eiter and Gottlob [SICOMP’95] gave an algorithm running in output-polynomial time, but whose space requirement also scales with the output. We improve this to polynomial delay and space. Central to our approach is the extension problem, deciding for a set X of vertices whether it is contained in any minimal hitting set. We show that this is one of the first natural problems to be W[3]-complete. We give an algorithm for the extension problem running in time O(m |X|+1 n) and prove a SETH-lower bound showing that this is close to optimal. We apply our enumeration method to the discovery problem of minimal unique column combinations from data profiling. Our empirical evaluation suggests that the algorithm outperforms its worst-case guarantees on hypergraphs stemming from real-world databases.}, author = {Bläsius, Thomas and Friedrich, Tobias and Lischeid, Julius and Meeks, Kitty and Schirneck, Martin}, journal = {Journal of Computer and System Sciences}, keywords = {kittymeeks thomasblaesius juliuslischeid tobiasfriedrich year2022 martinschirneck}, pages = {192-213}, title = {Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling}, volume = 124, year = 2022 }

Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, Marcus A Spectral Independence View on Hard Spheres via Block DynamicsSIAM Journal on Discrete Mathematics 2022: 2282–2322
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
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 < \mathrm{e / 2d\), the runtime of our algorithm is polynomial in the volume of the system. 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 block dynamics, a Markov chain that generalizes the more frequently studied Glauber dynamics by grouping the vertices of the graph into blocks and updating an entire block instead of a single vertex in each step. We prove rapid mixing of block dynamics, based on disjoint cliques as blocks, up to the tree threshold of the univariate hard-core model. This is achieved by adapting the spectral expansion method, which was recently used for bounding the mixing time of Glauber dynamics within the same parameter regime.
@article{friedrich2022spectral, 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 < \mathrm{e} / 2d\), the runtime of our algorithm is polynomial in the volume of the system. 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 block dynamics, a Markov chain that generalizes the more frequently studied Glauber dynamics by grouping the vertices of the graph into blocks and updating an entire block instead of a single vertex in each step. We prove rapid mixing of block dynamics, based on disjoint cliques as blocks, up to the tree threshold of the univariate hard-core model. This is achieved by adapting the spectral expansion method, which was recently used for bounding the mixing time of Glauber dynamics within the same parameter regime.}, author = {Friedrich, Tobias and Göbel, Andreas and Krejca, Martin S. and Pappik, Marcus}, journal = {SIAM Journal on Discrete Mathematics}, keywords = {marcuspappik martinskrejca andreasgoebel tobiasfriedrich year2022}, number = 3, pages = {2282-2322}, title = {A Spectral Independence View on Hard Spheres via Block Dynamics}, volume = 36, year = 2022 }

Bläsius, Thomas; Friedrich, Tobias; Schirneck, Martin The Complexity of Dependency Detection and Discovery in Relational DatabasesTheoretical Computer Science 2022: 79–96
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ 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{blaesius2022complexity, 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 = {Theoretical Computer Science}, keywords = {tcs thomasblaesius tobiasfriedrich year2022 martinschirneck}, pages = {79-96}, title = {The Complexity of Dependency Detection and Discovery in Relational Databases}, volume = 900, year = 2022 }

Bandyapadhyay, Sayan; Fomin, Fedor V.; Golovach, Petr A.; Lochet, William; Purohit, Nidhi; Simonov, Kirill How to Find a Good Explanation for Clustering?Conference on Artificial Intelligence (AAAI) 2022: 3904–3912
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
\(k\)-means and \(k\)-median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependences on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, Dasgupta, Rashtchian, and Frost proposed an elegant model of explainable \(k\)-means and \(k\)-median clustering in ICML 2020. In this model, a decision tree with \(k\) leaves provides a straightforward characterization of the data set into clusters. We study two natural algorithmic questions about explainable clustering. (1) For a given clustering, how to find the ``best explanation'' by using a decision tree with \(k\) leaves? (2) For a given set of points, how to find a decision tree with \(k\) leaves minimizing the \(k\)-means/median objective of the resulting explainable clustering? To address the first question, we introduce a new model of explainable clustering. Our model, inspired by the notion of outliers in robust statistics, is the following. We are seeking a small number of points (outliers) whose removal makes the existing clustering well-explainable. For addressing the second question, we initiate the study of the model of Moshkovitz et al. from the perspective of multivariate complexity. Our rigorous algorithmic analysis sheds some light on the influence of parameters like the input size, dimension of the data, the number of outliers, the number of clusters, and the approximation ratio, on the computational complexity of explainable clustering.
@inproceedings{bandyapadhyay2022explanation, abstract = {\(k\)-means and \(k\)-median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependences on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, Dasgupta, Rashtchian, and Frost proposed an elegant model of explainable \(k\)-means and \(k\)-median clustering in ICML 2020. In this model, a decision tree with \(k\) leaves provides a straightforward characterization of the data set into clusters. We study two natural algorithmic questions about explainable clustering. (1) For a given clustering, how to find the ``best explanation'' by using a decision tree with \(k\) leaves? (2) For a given set of points, how to find a decision tree with \(k\) leaves minimizing the \(k\)-means/median objective of the resulting explainable clustering? To address the first question, we introduce a new model of explainable clustering. Our model, inspired by the notion of outliers in robust statistics, is the following. We are seeking a small number of points (outliers) whose removal makes the existing clustering well-explainable. For addressing the second question, we initiate the study of the model of Moshkovitz et al. from the perspective of multivariate complexity. Our rigorous algorithmic analysis sheds some light on the influence of parameters like the input size, dimension of the data, the number of outliers, the number of clusters, and the approximation ratio, on the computational complexity of explainable clustering.}, author = {Bandyapadhyay, Sayan and Fomin, Fedor V. and Golovach, Petr A. and Lochet, William and Purohit, Nidhi and Simonov, Kirill}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {sys:relevantfor:ae kirillsimonov aaai year2022}, pages = {3904-3912}, title = {How to Find a Good Explanation for Clustering?}, year = 2022 }

Cseh, Ágnes; Peters, Jannik Three-Dimensional Popular Matching with Cyclic PreferencesAutonomous Agents and Multi-Agent Systems (AAMAS) 2022: 77–87
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Two actively researched problem settings in matchings under preferences are popular matchings and the three-dimensional stable matching problem with cyclic preferences. In this paper, we apply the optimality notion of the first topic to the input characteristics of the second one. We investigate the connection between stability, popularity, and their strict variants, strong stability and strong popularity in three-dimensional instances with cyclic preferences. Furthermore, we also derive results on the complexity of these problems when the preferences are derived from master lists.
@inproceedings{cseh2022threedimensional, abstract = {Two actively researched problem settings in matchings under preferences are popular matchings and the three-dimensional stable matching problem with cyclic preferences. In this paper, we apply the optimality notion of the first topic to the input characteristics of the second one. We investigate the connection between stability, popularity, and their strict variants, strong stability and strong popularity in three-dimensional instances with cyclic preferences. Furthermore, we also derive results on the complexity of these problems when the preferences are derived from master lists.}, author = {Cseh, Ágnes and Peters, Jannik}, booktitle = {Autonomous Agents and Multi-Agent Systems (AAMAS)}, keywords = {jannikpeters agnescseh aamas year2022}, pages = {77&ndash;87}, title = {Three-Dimensional Popular Matching with Cyclic Preferences}, year = 2022 }

Berenbrink, Petra; Hoefer, Martin; Kaaser, Dominik; Lenzner, Pascal; Rau, Malin; Schmand, Daniel Asynchronous Opinion Dynamics in Social NetworksAutonomous Agents and Multi-Agent Systems (AAMAS) 2022: 109–117
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Opinion spreading in a society decides the fate of elections, the success of products, and the impact of political or social movements. The model by Hegselmann and Krause is a well-known theoretical model to study such opinion formation processes in social networks. In contrast to many other theoretical models, it does not converge towards a situation where all agents agree on the same opinion. Instead, it assumes that people find an opinion reasonable if and only if it is close to their own. The system converges towards a stable situation where agents sharing the same opinion form a cluster, and agents in different clusters do not influence each other. We focus on the social variant of the Hegselmann-Krause model where agents are connected by a social network and their opinions evolve in an iterative process. When activated, an agent adopts the average of the opinions of its neighbors having a similar opinion. By this, the set of influencing neighbors of an agent may change over time. To the best of our knowledge, social Hegselmann-Krause systems with asynchronous opinion updates have only been studied with the complete graph as social network. We show that such opinion dynamics with random agent activation are guaranteed to converge for any social network. We provide an upper bound of \(\mathcal{O(n |E|^2 (\varepsilon/\delta)^2)\) on the expected number of opinion updates until convergence, where |E| is the number of edges of the social network. For the complete social network we show a bound of \( \mathcal{O(n^3(n^2 + (\varepsilon/\delta)^2)) \) that represents a major improvement over the previously best upper bound of \( \mathcal{O(n^9(\varepsilon/\delta)^2) \). Our bounds are complemented by simulations that indicate asymptotically matching lower bounds.
@inproceedings{berenbrink2022asynchronous, abstract = {Opinion spreading in a society decides the fate of elections, the success of products, and the impact of political or social movements. The model by Hegselmann and Krause is a well-known theoretical model to study such opinion formation processes in social networks. In contrast to many other theoretical models, it does not converge towards a situation where all agents agree on the same opinion. Instead, it assumes that people find an opinion reasonable if and only if it is close to their own. The system converges towards a stable situation where agents sharing the same opinion form a cluster, and agents in different clusters do not influence each other. We focus on the social variant of the Hegselmann-Krause model where agents are connected by a social network and their opinions evolve in an iterative process. When activated, an agent adopts the average of the opinions of its neighbors having a similar opinion. By this, the set of influencing neighbors of an agent may change over time. To the best of our knowledge, social Hegselmann-Krause systems with asynchronous opinion updates have only been studied with the complete graph as social network. We show that such opinion dynamics with random agent activation are guaranteed to converge for any social network. We provide an upper bound of \(\mathcal{O}(n |E|^2 (\varepsilon/\delta)^2)\) on the expected number of opinion updates until convergence, where |E| is the number of edges of the social network. For the complete social network we show a bound of \( \mathcal{O}(n^3(n^2 + (\varepsilon/\delta)^2)) \) that represents a major improvement over the previously best upper bound of \( \mathcal{O}(n^9(\varepsilon/\delta)^2) \). Our bounds are complemented by simulations that indicate asymptotically matching lower bounds.}, author = {Berenbrink, Petra and Hoefer, Martin and Kaaser, Dominik and Lenzner, Pascal and Rau, Malin and Schmand, Daniel}, booktitle = {Autonomous Agents and Multi-Agent Systems (AAMAS)}, keywords = {aamas year2022 pascallenzner}, pages = {109&ndash;117}, title = {Asynchronous Opinion Dynamics in Social Networks}, year = 2022 }

Cseh, Ágnes; Friedrich, Tobias; Peters, Jannik Pareto Optimal and Popular House Allocation with Lower and Upper QuotasAutonomous Agents and Multi-Agent Systems (AAMAS) 2022: 300–308
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In the house allocation problem with lower and upper quotas, we are given a set of applicants and a set of projects. Each applicant has a strictly ordered preference list over the projects, while the projects are equipped with a lower and an upper quota. A feasible matching assigns the applicants to the projects in such a way that a project is either matched to no applicant or to a number of applicants between its lower and upper quota. In this model we study two classic optimality concepts: Pareto optimality and popularity. We show that finding a popular matching is hard even if the maximum lower quota is 2 and that finding a perfect Pareto optimal matching, verifying Pareto optimality, and verifying popularity are all NP-complete even if the maximum lower quota is 3. We complement the last three negative results by showing that the problems become polynomial-time solvable when the maximum lower quota is 2, thereby answering two open questions of Cechlárová and Fleiner. Finally, we also study the parameterized complexity of all four mentioned problems.
@inproceedings{cseh2022pareto, abstract = {In the house allocation problem with lower and upper quotas, we are given a set of applicants and a set of projects. Each applicant has a strictly ordered preference list over the projects, while the projects are equipped with a lower and an upper quota. A feasible matching assigns the applicants to the projects in such a way that a project is either matched to no applicant or to a number of applicants between its lower and upper quota. In this model we study two classic optimality concepts: Pareto optimality and popularity. We show that finding a popular matching is hard even if the maximum lower quota is 2 and that finding a perfect Pareto optimal matching, verifying Pareto optimality, and verifying popularity are all NP-complete even if the maximum lower quota is 3. We complement the last three negative results by showing that the problems become polynomial-time solvable when the maximum lower quota is 2, thereby answering two open questions of Cechlárová and Fleiner. Finally, we also study the parameterized complexity of all four mentioned problems.}, author = {Cseh, Ágnes and Friedrich, Tobias and Peters, Jannik}, booktitle = {Autonomous Agents and Multi-Agent Systems (AAMAS)}, keywords = {jannikpeters agnescseh tobiasfriedrich aamas year2022}, pages = {300&ndash;308}, title = {Pareto Optimal and Popular House Allocation with Lower and Upper Quotas}, year = 2022 }

Bläsius, Thomas; Friedrich, Tobias; Stangl, David; Weyand, Christopher An Efficient Branch-and-Bound Solver for Hitting SetAlgorithm Engineering and Experiments (ALENEX) 2022
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The hitting set problem asks for a collection of sets over a universe \(U\) to find a minimum subset of \(U\) that intersects each of the given sets. It is NP-hard and equivalent to the problem set cover. We give a branch-and-bound algorithm to solve hitting set. Though it requires exponential time in the worst case, it can solve many practical instance from different domains in reasonable time. Our algorithm outperforms a modern ILP solver, the state-of-the-art for hitting set, by at least an order of magnitude on most instances.
@inproceedings{blasius2022efficient, abstract = {The hitting set problem asks for a collection of sets over a universe \(U\) to find a minimum subset of \(U\) that intersects each of the given sets. It is NP-hard and equivalent to the problem set cover. We give a branch-and-bound algorithm to solve hitting set. Though it requires exponential time in the worst case, it can solve many practical instance from different domains in reasonable time. Our algorithm outperforms a modern ILP solver, the state-of-the-art for hitting set, by at least an order of magnitude on most instances.}, author = {Bläsius, Thomas and Friedrich, Tobias and Stangl, David and Weyand, Christopher}, booktitle = {Algorithm Engineering and Experiments (ALENEX)}, keywords = {alenex thomasblaesius tobiasfriedrich christopherweyand davidstangl year2022}, title = {An Efficient Branch-and-Bound Solver for Hitting Set}, year = 2022 }

Friedrich, Tobias; Issac, Davis; Kumar, Nikhil; Mallek, Nadym; Zeif, Ziena A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 GraphsApproximation Algorithms for Combinatorial Optimization Problems (APPROX) 2022: 55:1–55:18
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study the problem of multicommodity flow and multicut in treewidth-2 graphs and prove bounds on the multiflow-multicut gap. In particular, we give a primal-dual algorithm for computing multicommodity flow and multicut in treewidth-2 graphs and prove the following approximate max-flow min-cut theorem: given a treewidth-2 graph, there exists a multicommodity flow of value \(f\) with congestion \(4\), and a multicut of capacity \(c\) such that \(c \leq 20f \) . This implies a multiflow-multicut gap of \(80\) and improves upon the previous best known bounds for such graphs. Our algorithm runs in polynomial time when all the edges have capacity one. Our algorithm is completely combinatorial and builds upon the primal-dual algorithm of Garg, Vazirani and Yannakakis for multicut in trees and the augmenting paths framework of Ford and Fulkerson.
@inproceedings{friedrich2022primaldual, abstract = {We study the problem of multicommodity flow and multicut in treewidth-2 graphs and prove bounds on the multiflow-multicut gap. In particular, we give a primal-dual algorithm for computing multicommodity flow and multicut in treewidth-2 graphs and prove the following approximate max-flow min-cut theorem: given a treewidth-2 graph, there exists a multicommodity flow of value \(f\) with congestion \(4\), and a multicut of capacity \(c\) such that \(c \leq 20f \) . This implies a multiflow-multicut gap of \(80\) and improves upon the previous best known bounds for such graphs. Our algorithm runs in polynomial time when all the edges have capacity one. Our algorithm is completely combinatorial and builds upon the primal-dual algorithm of Garg, Vazirani and Yannakakis for multicut in trees and the augmenting paths framework of Ford and Fulkerson.}, author = {Friedrich, Tobias and Issac, Davis and Kumar, Nikhil and Mallek, Nadym and Zeif, Ziena}, booktitle = {Approximation Algorithms for Combinatorial Optimization Problems (APPROX)}, keywords = {sys:relevantfor:ae zienazeif nikhilkumar davisissac tobiasfriedrich approx nadymmallek year2022}, pages = {55:1&ndash;55:18}, title = {A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs}, year = 2022 }

Doskoč, Vanja; Kötzing, Timo Maps of Restrictions for Behaviourally Correct LearningComputability in Europe (CiE) 2022: 103–114
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In language learning in the limit, we study computable devices (learners) learning formal languages. We consider learning tasks paired with restrictions regarding, for example, the hypotheses made by the learners. We compare such restrictions with each other in order to study their impact and depict the results in overviews, the so-called maps. In~the case of explanatory learning, the literature already provides various maps. On the other hand, in the case of behaviourally correct learning, only partial results are known. In this work, we complete these results and provide full behaviourally correct maps for different types of data presentation. In particular, in all studied settings, we observe that monotone learning implies non-U-shaped learning and that cautiousness, semantic conservativeness and weak monotonicity are equally powerful.
@inproceedings{doskoc2022restrictions, abstract = {In language learning in the limit, we study computable devices (learners) learning formal languages. We consider learning tasks paired with restrictions regarding, for example, the hypotheses made by the learners. We compare such restrictions with each other in order to study their impact and depict the results in overviews, the so-called maps. In&nbsp;the case of explanatory learning, the literature already provides various maps. On the other hand, in the case of behaviourally correct learning, only partial results are known. In this work, we complete these results and provide full behaviourally correct maps for different types of data presentation. In particular, in all studied settings, we observe that monotone learning implies non-U-shaped learning and that cautiousness, semantic conservativeness and weak monotonicity are equally powerful.}, author = {Doskoč, Vanja and Kötzing, Timo}, booktitle = {Computability in Europe (CiE)}, keywords = {vanjadoskoc timokoetzing year2022 cie}, pages = {103-114}, title = {Maps of Restrictions for Behaviourally Correct Learning}, volume = 13359, year = 2022 }

Friedrich, Tobias; Göbel, Andreas; Katzmann, Maximilian; Krejca, Martin S.; Pappik, Marcus Algorithms for hard-constraint point processes via discretizationInternational Computing and Combinatorics Conference (COCOON) 2022
[ Abstract ] [ BibTeX ] [ Download ]
 
We study the algorithmic applications of a natural discretization for the hard-sphere model and the Widom--Rowlinson model in a region of \(d\)-dimensional Euclidean space \(V \subset \mathbf{R}^{d}\). These continuous models are frequently used in statistical physics to describe mixtures of one or multiple particle types subjected to hard-core interactions. For each type, particles are distributed according to a Poisson point process with a type-specific activity parameter, called fugacity. The Gibbs distribution over all possible system states is characterized by the mixture of these point processes conditioned that no two particles are closer than some type-dependent distance threshold. A key part in better understanding the Gibbs distribution is its normalizing constant, called partition function. Our main algorithmic result is the first deterministic approximation algorithm for the partition function of the hard-sphere model and the Widom--Rowlinson model in box-shaped regions of Euclidean space. Our algorithms have quasi-polynomial running time in the volume of the region \(\nu(V)\) if the fugacity is below a certain threshold. For the \(d\)-dimensional hard-sphere model with particles of unit volume, this threshold is \(\mathrm{e}/2^d\). As the number of dimensions \(d\) increases, this bound asymptotically matches the best known results for randomized approximation of the hard-sphere partition function. We prove similar bounds for the Widom--Rowlinson model. To the best of our knowledge, this is the first rigorous algorithmic result for this model.
@inproceedings{friedrich2022algorithms, abstract = {We study the algorithmic applications of a natural discretization for the hard-sphere model and the Widom&ndash;Rowlinson model in a region of \(d\)-dimensional Euclidean space \(V \subset \mathbf{R}^{d}\). These continuous models are frequently used in statistical physics to describe mixtures of one or multiple particle types subjected to hard-core interactions. For each type, particles are distributed according to a Poisson point process with a type-specific activity parameter, called fugacity. The Gibbs distribution over all possible system states is characterized by the mixture of these point processes conditioned that no two particles are closer than some type-dependent distance threshold. A key part in better understanding the Gibbs distribution is its normalizing constant, called partition function. Our main algorithmic result is the first deterministic approximation algorithm for the partition function of the hard-sphere model and the Widom&ndash;Rowlinson model in box-shaped regions of Euclidean space. Our algorithms have quasi-polynomial running time in the volume of the region \(\nu(V)\) if the fugacity is below a certain threshold. For the \(d\)-dimensional hard-sphere model with particles of unit volume, this threshold is \(\mathrm{e}/2^d\). As the number of dimensions \(d\) increases, this bound asymptotically matches the best known results for randomized approximation of the hard-sphere partition function. We prove similar bounds for the Widom&ndash;Rowlinson model. To the best of our knowledge, this is the first rigorous algorithmic result for this model.}, author = {Friedrich, Tobias and Göbel, Andreas and Katzmann, Maximilian and Krejca, Martin S. and Pappik, Marcus}, booktitle = {International Computing and Combinatorics Conference (COCOON)}, keywords = {marcuspappik martinskrejca andreasgoebel tobiasfriedrich cocoon maximiliankatzmann year2022}, title = {Algorithms for hard-constraint point processes via discretization}, year = 2022 }

Hildebrandt, Philipp; Schulze, Maximilian; Cohen, Sarel; Doskoč, Vanja; Saabni, Raid; Friedrich, Tobias Optical Character Recognition Guided Image Super ResolutionSymposium on Document Engineering (DocEng) 2022: 1–4
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Recognizing disturbed text in real-life images is a difficult problem, as information that is missing due to low resolution or out-of-focus text has to be recreated. Combining text super-resolution and optical character recognition deep learning models can be a valuable tool to enlarge and enhance text images for better readability, as well as recognize text automatically afterwards. We achieve improved peak signal-to-noise ratio and text recognition accuracy scores over a state-of-the-art text super-resolution model TBSRN on the real-world low-resolution dataset TextZoom while having a smaller theoretical model size due to the usage of quantization techniques. In addition, we show how different training strategies influence the performance of the resulting model.
@inproceedings{hildebrandt2022optical, abstract = {Recognizing disturbed text in real-life images is a difficult problem, as information that is missing due to low resolution or out-of-focus text has to be recreated. Combining text super-resolution and optical character recognition deep learning models can be a valuable tool to enlarge and enhance text images for better readability, as well as recognize text automatically afterwards. We achieve improved peak signal-to-noise ratio and text recognition accuracy scores over a state-of-the-art text super-resolution model TBSRN on the real-world low-resolution dataset TextZoom while having a smaller theoretical model size due to the usage of quantization techniques. In addition, we show how different training strategies influence the performance of the resulting model.}, author = {Hildebrandt, Philipp and Schulze, Maximilian and Cohen, Sarel and Doskoč, Vanja and Saabni, Raid and Friedrich, Tobias}, booktitle = {Symposium on Document Engineering (DocEng)}, keywords = {sarelcohen vanjadoskoc philipphildebrandt maximilianschulze tobiasfriedrich doceng raidsaabni year2022}, pages = {1-4}, title = {Optical Character Recognition Guided Image Super Resolution}, year = 2022 }

Führlich, Pascal; Cseh, Ágnes; Lenzner, Pascal Improving Ranking Quality and Fairness in Swiss-System Chess TournamentsACM Conference on Economics and Computation (EC) 2022: 1101–1102
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The International Chess Federation (FIDE) imposes a voluminous and complex set of player pairing criteria in Swiss-system chess tournaments and endorses computer programs that are able to calculate the prescribed pairings. The purpose of these formalities is to ensure that players are paired fairly during the tournament and that the final ranking corresponds to the players' true strength order. We contest the official FIDE player pairing routine by presenting alternative pairing rules. These can be enforced by computing maximum weight matchings in a carefully designed graph. We demonstrate by extensive experiments that a tournament format using our mechanism (1) yields fairer pairings in the rounds of the tournament and (2) produces a final ranking that reflects the players' true strengths better than the state-of-the-art FIDE pairing system.
@inproceedings{fuhrlich2022improving, abstract = {The International Chess Federation (FIDE) imposes a voluminous and complex set of player pairing criteria in Swiss-system chess tournaments and endorses computer programs that are able to calculate the prescribed pairings. The purpose of these formalities is to ensure that players are paired fairly during the tournament and that the final ranking corresponds to the players' true strength order. We contest the official FIDE player pairing routine by presenting alternative pairing rules. These can be enforced by computing maximum weight matchings in a carefully designed graph. We demonstrate by extensive experiments that a tournament format using our mechanism (1) yields fairer pairings in the rounds of the tournament and (2) produces a final ranking that reflects the players' true strengths better than the state-of-the-art FIDE pairing system.}, author = {Führlich, Pascal and Cseh, Ágnes and Lenzner, Pascal}, booktitle = {ACM Conference on Economics and Computation (EC)}, keywords = {agnescseh year2022 ec pascallenzner}, pages = {1101 &ndash; 1102}, publisher = {ACM}, title = {Improving Ranking Quality and Fairness in Swiss-System Chess Tournaments}, year = 2022 }

Bläsius, Thomas; Fischbeck, Philipp On the External Validity of Average-Case Analyses of Graph AlgorithmsEuropean Symposium on Algorithms (ESA) 2022: 21:1–21:14
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The number one criticism of average-case analysis is that we do not actually know the probability distribution of real-world inputs. Thus, analyzing an algorithm on some random model has no implications for practical performance. At its core, this criticism doubts the existence of external validity, i.e., it assumes that algorithmic behavior on the somewhat simple and clean models does not translate beyond the models to practical performance real-world input. With this paper, we provide a first step towards studying the question of external validity systematically. To this end, we evaluate the performance of six graph algorithms on a collection of 2751 sparse real-world networks depending on two properties; the heterogeneity (variance in the degree distribution) and locality (tendency of edges to connect vertices that are already close). We compare this with the performance on generated networks with varying locality and heterogeneity. We find that the performance in the idealized setting of network models translates surprisingly well to real-world networks. Moreover, heterogeneity and locality appear to be the core properties impacting the performance of many graph algorithms.
@inproceedings{blasius2022external, abstract = {The number one criticism of average-case analysis is that we do not actually know the probability distribution of real-world inputs. Thus, analyzing an algorithm on some random model has no implications for practical performance. At its core, this criticism doubts the existence of external validity, i.e., it assumes that algorithmic behavior on the somewhat simple and clean models does not translate beyond the models to practical performance real-world input. With this paper, we provide a first step towards studying the question of external validity systematically. To this end, we evaluate the performance of six graph algorithms on a collection of 2751 sparse real-world networks depending on two properties; the heterogeneity (variance in the degree distribution) and locality (tendency of edges to connect vertices that are already close). We compare this with the performance on generated networks with varying locality and heterogeneity. We find that the performance in the idealized setting of network models translates surprisingly well to real-world networks. Moreover, heterogeneity and locality appear to be the core properties impacting the performance of many graph algorithms.}, author = {Bläsius, Thomas and Fischbeck, Philipp}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {philippfischbeck esa thomasblaesius year2022}, pages = {21:1&ndash;21:14}, title = {On the External Validity of Average-Case Analyses of Graph Algorithms}, year = 2022 }

Kumar, Nikhil An Approximate Generalization of the Okamura-Seymour TheoremSymposium on Foundations of Computer Science (FOCS) 2022
[ Abstract ] [ BibTeX ] [ Download ]
 
We consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient for routing demands. We consider the following generalization of this setting and prove an approximate max flow-min cut theorem: for every demand edge, there exists a face containing both its end points. We show that the cut-condition is sufficient for routing \(\Omega(1)\)-fraction of all the demands. To prove this, we give a \(L_1\)-embedding of the planar metric which approximately preserves distance between all pair of points on the same face.
@inproceedings{kumar2022approximate, abstract = {We consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient for routing demands. We consider the following generalization of this setting and prove an approximate max flow-min cut theorem: for every demand edge, there exists a face containing both its end points. We show that the cut-condition is sufficient for routing \(\Omega(1)\)-fraction of all the demands. To prove this, we give a \(L_1\)-embedding of the planar metric which approximately preserves distance between all pair of points on the same face.}, author = {Kumar, Nikhil}, booktitle = {Symposium on Foundations of Computer Science (FOCS)}, keywords = {sys:relevantfor:ae nikhilkumar focs year2022}, title = {An Approximate Generalization of the Okamura-Seymour Theorem}, year = 2022 }

Angrick, Sebastian; Bals, Ben; Hastrich, Niko; Kleissl, Maximilian; Schmidt, Jonas; Doskoč, Vanja; Katzmann, Maximilian; Molitor, Louise; Friedrich, Tobias Towards Explainable Real Estate Valuation via Evolutionary AlgorithmsGenetic and Evolutionary Computation Conference (GECCO) 2022: 1130–1138
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Human lives are increasingly influenced by algorithms, which therefore need to meet higher standards not only in accuracy but also with respect to explainability. This is especially true for high-stakes areas such as real estate valuation. Unfortunately, the methods applied there often exhibit a trade-off between accuracy and explainability. One explainable approach is case-based reasoning (CBR), whereeach decision is supported by specific previous cases. However, such methods can be wanting in accuracy. The unexplainable machine learning approaches are often observed to provide higher accuracy but are not scrutable in their decision-making. In this paper, we apply evolutionary algorithms (EAs) to CBR predictors in order to improve their performance. In particular, we deploy EAs to the similarity functions (used in CBR to find comparable cases), which are fitted to the data set at hand. As a consequence, we achieve higher accuracy than state-of-the-art deep neural networks (DNNs), while keeping interpretability and explainability. These results stem from our empirical evaluation on a large data set of real estate offers where we compare known similarity functions, their EA-improved counterparts, and DNNs. Surprisingly, DNNs are only on par with standard CBR techniques. However, using EA-learned similarity functions does yield an improved performance.
@inproceedings{angrick2022towards, abstract = {Human lives are increasingly influenced by algorithms, which therefore need to meet higher standards not only in accuracy but also with respect to explainability. This is especially true for high-stakes areas such as real estate valuation. Unfortunately, the methods applied there often exhibit a trade-off between accuracy and explainability. One explainable approach is case-based reasoning (CBR), whereeach decision is supported by specific previous cases. However, such methods can be wanting in accuracy. The unexplainable machine learning approaches are often observed to provide higher accuracy but are not scrutable in their decision-making. In this paper, we apply evolutionary algorithms (EAs) to CBR predictors in order to improve their performance. In particular, we deploy EAs to the similarity functions (used in CBR to find comparable cases), which are fitted to the data set at hand. As a consequence, we achieve higher accuracy than state-of-the-art deep neural networks (DNNs), while keeping interpretability and explainability. These results stem from our empirical evaluation on a large data set of real estate offers where we compare known similarity functions, their EA-improved counterparts, and DNNs. Surprisingly, DNNs are only on par with standard CBR techniques. However, using EA-learned similarity functions does yield an improved performance.}, author = {Angrick, Sebastian and Bals, Ben and Hastrich, Niko and Kleissl, Maximilian and Schmidt, Jonas and Doskoč, Vanja and Katzmann, Maximilian and Molitor, Louise and Friedrich, Tobias}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {louisemolitor vanjadoskoc sebastianangrick benbals nikohastrich tobiasfriedrich gecco maximiliankleissl jonasschmidt maximiliankatzmann year2022}, pages = {1130&ndash;1138}, title = {Towards Explainable Real Estate Valuation via Evolutionary Algorithms}, year = 2022 }

Baguley, Samuel; Friedrich, Tobias; Timo, Kötzing; Li, Xiaoyue; Pappik, Marcus; Zeif, Ziena Analysis of a Gray-Box Operator for Vertex CoverGenetic and Evolutionary Computation Conference (GECCO) 2022: 1363–1371
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Combinatorial optimization problems are a prominent application area of evolutionary algorithms, where the (1+1) EA is one of the most investigated. We extend this algorithm by introducing some problem knowledge with a specialized mutation operator which works under the assumption that the number of 1s of a solution is critical, as frequently happens in combinatorial optimization. This slight modification increases the chance to correct wrongly placed bits while preserving the simplicity and problem independence of the (1+1) EA. As an application of our algorithm we examine the vertex cover problem on certain instances, where we show that it leads to asymptotically better runtimes and even finds with higher probability optimal solutions in comparison with the usual (1+1) EA. Precisely, we compare the performance of both algorithms on paths and on complete bipartite graphs of size \(n\). Regarding the path we prove that, for a particular initial configuration, the (1+1) EA takes in expectation \(\Theta(n^4)\) iterations while the modification reduces this to \(\Theta(n^3)\), and present experimental evidence that such a configuration is reached. Concerning the complete bipartite graph our modification finds the optimum in polynomial time with probability \(1-1/2^{\Omega(n^\xi)}\) for every positive constant \(\xi < 1\), which improves the known probability of \(1-1/\)poly\((n)\) for the (1+1) EA.
@inproceedings{baguley2022analysis, abstract = {Combinatorial optimization problems are a prominent application area of evolutionary algorithms, where the (1+1) EA is one of the most investigated. We extend this algorithm by introducing some problem knowledge with a specialized mutation operator which works under the assumption that the number of 1s of a solution is critical, as frequently happens in combinatorial optimization. This slight modification increases the chance to correct wrongly placed bits while preserving the simplicity and problem independence of the (1+1) EA. As an application of our algorithm we examine the vertex cover problem on certain instances, where we show that it leads to asymptotically better runtimes and even finds with higher probability optimal solutions in comparison with the usual (1+1) EA. Precisely, we compare the performance of both algorithms on paths and on complete bipartite graphs of size \(n\). Regarding the path we prove that, for a particular initial configuration, the (1+1) EA takes in expectation \(\Theta(n^4)\) iterations while the modification reduces this to \(\Theta(n^3)\), and present experimental evidence that such a configuration is reached. Concerning the complete bipartite graph our modification finds the optimum in polynomial time with probability \(1-1/2^{\Omega(n^\xi)}\) for every positive constant \(\xi < 1\), which improves the known probability of \(1-1/\)poly\((n)\) for the (1+1) EA.}, author = {Baguley, Samuel and Friedrich, Tobias and Timo, Kötzing and Li, Xiaoyue and Pappik, Marcus and Zeif, Ziena}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {sys:relevantfor:ae zienazeif marcuspappik samuelbaguley xiaoyueli timokoetzing tobiasfriedrich gecco year2022}, pages = {1363&ndash;1371}, title = {Analysis of a Gray-Box Operator for Vertex Cover}, year = 2022 }

Friedrich, Tobias; Kötzing, Timo; Radhakrishnan, Aishwarya; Schiller, Leon; Schirneck, Martin; Tennigkeit, Georg; Wietheger, Simon Crossover for Cardinality Constrained OptimizationGenetic and Evolutionary Computation Conference (GECCO) 2022: 1399–1407
Best Paper Award (Theory Track)
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In order to understand better how and why crossover can benefit optimization, we consider pseudo-Boolean functions with an upper bound \(B\) on the number of 1s allowed in the bit string (cardinality constraint). We consider the natural translation of the OneMax test function, a linear function where \(B\) bits have a weight of \(1+\varepsilon\) and the remaining bits have a weight of \(1\). The literature gives a bound of \(\Theta(n^2)\) for the (1+1) EA on this function. Part of the difficulty when optimizing this problem lies in having to improve individuals meeting the cardinality constraint by flipping both a 1 and a 0. The experimental literature proposes balanced operators, preserving the number of 1s, as a remedy. We show that a balanced mutation operator optimizes the problem in \(O(n \log n)\) if \(n-B = O(1)\). However, if \(n-B = \Theta(n)\), we show a bound of \(\Omega(n^2)\), just as classic bit flip mutation. Crossover and a simple island model gives \(O(n^2 / \log n)\) (uniform crossover) and \(O(n\sqrt{n})\) (3-ary majority vote crossover). For balanced uniform crossover with Hamming distance maximization for diversity we show a bound of \(O(n \log n)\). As an additional contribution we analyze and discuss different balanced crossover operators from the literature.
@inproceedings{friedrich2022crossover, abstract = {In order to understand better how and why crossover can benefit optimization, we consider pseudo-Boolean functions with an upper bound \(B\) on the number of 1s allowed in the bit string (cardinality constraint). We consider the natural translation of the OneMax test function, a linear function where \(B\) bits have a weight of \(1+\varepsilon\) and the remaining bits have a weight of \(1\). The literature gives a bound of \(\Theta(n^2)\) for the (1+1) EA on this function. Part of the difficulty when optimizing this problem lies in having to improve individuals meeting the cardinality constraint by flipping both a 1 and a 0. The experimental literature proposes balanced operators, preserving the number of 1s, as a remedy. We show that a balanced mutation operator optimizes the problem in \(O(n \log n)\) if \(n-B = O(1)\). However, if \(n-B = \Theta(n)\), we show a bound of \(\Omega(n^2)\), just as classic bit flip mutation. Crossover and a simple island model gives \(O(n^2 / \log n)\) (uniform crossover) and \(O(n\sqrt{n})\) (3-ary majority vote crossover). For balanced uniform crossover with Hamming distance maximization for diversity we show a bound of \(O(n \log n)\). As an additional contribution we analyze and discuss different balanced crossover operators from the literature.}, author = {Friedrich, Tobias and Kötzing, Timo and Radhakrishnan, Aishwarya and Schiller, Leon and Schirneck, Martin and Tennigkeit, Georg and Wietheger, Simon}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {aishwaryaradhakrishnan timokoetzing simonwietheger tobiasfriedrich gecco leonschiller year2022 georgtennigkeit martinschirneck}, note = {Best Paper Award (Theory Track)}, pages = {1399&ndash;1407}, title = {Crossover for Cardinality Constrained Optimization}, year = 2022 }

Wood, Andrew; Hershcovitch, Moshik; Ennmouri, Ilias; Zong, Weiyu; Chennuri, Saurav; Cohen, Sarel; Sundararaman, Swaminathan; Waddington, Daniel; Chin, Peter Towards Fast Crash-Consistent Cluster CheckpointingHigh Performance Extreme Computing Conference (HPEC) 2022
[ Abstract ] [ BibTeX ] [ Download ]
 
Machine Learning models are expensive to train: they require expensive high-compute hardware and have long training times. Therefore, models are extra sensitive to program faults or unexpected system crashes, which can erase hours if not days worth of work. While there are plenty of strategies designed to mitigate the risk of unexpected system downtime, the most popular strategy in machine learning is called checkpointing: periodically saving the state of the model to persistent storage. Checkpointing is an effective strategy, however, it requires carefully balancing two operations: how often a checkpoint is made (the checkpointing schedule), and the cost of creating a checkpoint itself. In this paper, we leverage Python Memory Manager (PyMM), which provides Python support for Persistent Memory and emerging Persistent Memory technology (Optane DC) to accelerate the checkpointing operation while maintaining crash consistency. We first show that when checkpointing models, PyMM with persistent memory can save from minutes to days of checkpointing runtime. We then further optimize the checkpointing operation with PyMM and demonstrate our approach with the KMeans and Gaussian Mixture Model algorithms on two real-world datasets: MNIST and MusicNet. Through evaluation, we show that these two algorithms achieve a checkpointing speedup of a factor between 10 and 75x for KMeans and over 3x for GMM against the current state-of-the-art checkpointing approaches. We also verify that our solution recovers from crashes, while traditional approaches cannot.
@inproceedings{wood2022towards, abstract = {Machine Learning models are expensive to train: they require expensive high-compute hardware and have long training times. Therefore, models are extra sensitive to program faults or unexpected system crashes, which can erase hours if not days worth of work. While there are plenty of strategies designed to mitigate the risk of unexpected system downtime, the most popular strategy in machine learning is called checkpointing: periodically saving the state of the model to persistent storage. Checkpointing is an effective strategy, however, it requires carefully balancing two operations: how often a checkpoint is made (the checkpointing schedule), and the cost of creating a checkpoint itself. In this paper, we leverage Python Memory Manager (PyMM), which provides Python support for Persistent Memory and emerging Persistent Memory technology (Optane DC) to accelerate the checkpointing operation while maintaining crash consistency. We first show that when checkpointing models, PyMM with persistent memory can save from minutes to days of checkpointing runtime. We then further optimize the checkpointing operation with PyMM and demonstrate our approach with the KMeans and Gaussian Mixture Model algorithms on two real-world datasets: MNIST and MusicNet. Through evaluation, we show that these two algorithms achieve a checkpointing speedup of a factor between 10 and 75x for KMeans and over 3x for GMM against the current state-of-the-art checkpointing approaches. We also verify that our solution recovers from crashes, while traditional approaches cannot.}, author = {Wood, Andrew and Hershcovitch, Moshik and Ennmouri, Ilias and Zong, Weiyu and Chennuri, Saurav and Cohen, Sarel and Sundararaman, Swaminathan and Waddington, Daniel and Chin, Peter}, booktitle = {High Performance Extreme Computing Conference (HPEC)}, keywords = {sarelcohen hpec year2022}, title = {Towards Fast Crash-Consistent Cluster Checkpointing}, year = 2022 }

Friedrich, Tobias; Gawendowicz, Hans; Lenzner, Pascal; Melnichenko, Anna Social Distancing Network CreationInternational Colloquium on Automata, Languages and Programming (ICALP) 2022: 62:1–62:21
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
During a pandemic people have to find a trade-off between meeting others and staying safely at home. While meeting others is pleasant, it also increases the risk of infection. We consider this dilemma by introducing a game-theoretic network creation model in which selfish agents can form bilateral connections. They benefit from network neighbors, but at the same time, they want to maximize their distance to all other agents. This models the inherent conflict that social distancing rules impose on the behavior of selfish agents in a social network. Besides addressing this familiar issue, our model can be seen as the inverse to the well-studied Network Creation Game by Fabrikant et al.~[PODC 2003] where agents aim at being as central as possible in the created network. Thus, our work is in-line with studies that compare minimization problems with their maximization versions. We look at two variants of network creation governed by social distancing. In the first variant, there are no restrictions on the connections being formed. We characterize optimal and equilibrium networks, and we derive asymptotically tight bounds on the Price of Anarchy and Price of Stability. The second variant is the model's generalization that allows restrictions on the connections that can be formed. As our main result, we prove that Swap-Maximal Routing-Cost Spanning Trees, an efficiently computable weaker variant of Maximum Routing-Cost Spanning Trees, actually resemble equilibria for a significant range of the parameter space. Moreover, we give almost tight bounds on the Price of Anarchy and Price of Stability. These results imply that, compared the well-studied inverse models, under social distancing the agents' selfish behavior has a significantly stronger impact on the quality of the equilibria, i.e., allowing socially much worse stable states.
@inproceedings{friedrich2022social, abstract = {During a pandemic people have to find a trade-off between meeting others and staying safely at home. While meeting others is pleasant, it also increases the risk of infection. We consider this dilemma by introducing a game-theoretic network creation model in which selfish agents can form bilateral connections. They benefit from network neighbors, but at the same time, they want to maximize their distance to all other agents. This models the inherent conflict that social distancing rules impose on the behavior of selfish agents in a social network. Besides addressing this familiar issue, our model can be seen as the inverse to the well-studied Network Creation Game by Fabrikant et al.&nbsp;[PODC 2003] where agents aim at being as central as possible in the created network. Thus, our work is in-line with studies that compare minimization problems with their maximization versions. We look at two variants of network creation governed by social distancing. In the first variant, there are no restrictions on the connections being formed. We characterize optimal and equilibrium networks, and we derive asymptotically tight bounds on the Price of Anarchy and Price of Stability. The second variant is the model's generalization that allows restrictions on the connections that can be formed. As our main result, we prove that Swap-Maximal Routing-Cost Spanning Trees, an efficiently computable weaker variant of Maximum Routing-Cost Spanning Trees, actually resemble equilibria for a significant range of the parameter space. Moreover, we give almost tight bounds on the Price of Anarchy and Price of Stability. These results imply that, compared the well-studied inverse models, under social distancing the agents' selfish behavior has a significantly stronger impact on the quality of the equilibria, i.e., allowing socially much worse stable states.}, author = {Friedrich, Tobias and Gawendowicz, Hans and Lenzner, Pascal and Melnichenko, Anna}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {hansgawendowicz tobiasfriedrich icalp annamelnichenko year2022 pascallenzner}, pages = {62:1&ndash;62:21}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{{ü}}r Informatik}, title = {Social Distancing Network Creation}, volume = {LIPIcs:229}, year = 2022 }

Bilò, Davide; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Schirneck, Martin Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs DistancesInternational Colloquium on Automata, Languages and Programming (ICALP) 2022: 68:1–68:19
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We construct data structures for extremal and pairwise distances in directed graphs in the presence of transient edge failures. Henzinger et al. (ITCS 2017) initiated the study of fault-tolerant (sensitivity) oracles for the diameter and vertex eccentricities. We extend this with a special focus on space efficiency. We present several new data structures, among them the first fault-tolerant eccentricity oracle for dual failures in subcubic space. We further prove lower bounds that show limits to approximation vs. space and diameter vs. space trade-offs for fault-tolerant oracles. They highlight key differences between data structures for undirected and directed graphs. Initially, our oracles are randomized leaning on a sampling technique frequently used in sensitivity analysis. Building on the work of Alon, Chechik, and Cohen (ICALP 2019) as well as Karthik and Parter (SODA 2021), we develop a hierarchical framework to derandomize fault-tolerant data structures. We first apply it to our own diameter/eccentricity oracles and then show its usefulness by derandomizing algorithms from the literature: the distance sensitivity oracle of Ren (JCSS 2022) and the Single-Source Replacement Path algorithm of Chechik and Magen (ICALP 2020).
@inproceedings{bilo2022deterministic, abstract = {We construct data structures for extremal and pairwise distances in directed graphs in the presence of transient edge failures. Henzinger et al. (ITCS 2017) initiated the study of fault-tolerant (sensitivity) oracles for the diameter and vertex eccentricities. We extend this with a special focus on space efficiency. We present several new data structures, among them the first fault-tolerant eccentricity oracle for dual failures in subcubic space. We further prove lower bounds that show limits to approximation vs. space and diameter vs. space trade-offs for fault-tolerant oracles. They highlight key differences between data structures for undirected and directed graphs. Initially, our oracles are randomized leaning on a sampling technique frequently used in sensitivity analysis. Building on the work of Alon, Chechik, and Cohen (ICALP 2019) as well as Karthik and Parter (SODA 2021), we develop a hierarchical framework to derandomize fault-tolerant data structures. We first apply it to our own diameter/eccentricity oracles and then show its usefulness by derandomizing algorithms from the literature: the distance sensitivity oracle of Ren (JCSS 2022) and the Single-Source Replacement Path algorithm of Chechik and Magen (ICALP 2020).}, author = {Bilò, Davide and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Schirneck, Martin}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {sarelcohen davidebilo tobiasfriedrich icalp keertichoudhary year2022 martinschirneck}, pages = {68:1-68:19}, title = {Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances}, year = 2022 }

Böther, Maximilian; Kißig, Otto; Taraz, Martin; Cohen, Sarel; Seidel, Karen; Friedrich, Tobias What’s Wrong with Deep Learning in Tree Search for Combinatorial OptimizationInternational Conference on Learning Representations (ICLR) 2022
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Combinatorial optimization lies at the core of many real-world problems. Especially since the rise of graph neural networks (GNNs), the deep learning community has been developing solvers that derive solutions to NP-hard problems by learning the problem-specific solution structure. However, reproducing the results of these publications proves to be difficult. We make three contributions. First, we present an open-source benchmark suite for the NP-hard Maximum Independent Set problem, in both its weighted and unweighted variants. The suite offers a unified interface to various state-of-the-art traditional and machine learning-based solvers. Second, using our benchmark suite, we conduct an in-depth analysis of the popular guided tree search algorithm by Li et al. [NeurIPS 2018], testing various configurations on small and large synthetic and real-world graphs. By re-implementing their algorithm with a focus on code quality and extensibility, we show that the graph convolution network used in the tree search does not learn a meaningful representation of the solution structure, and can in fact be replaced by random values. Instead, the tree search relies on algorithmic techniques like graph kernelization to find good solutions. Thus, the results from the original publication are not reproducible. Third, we extend the analysis to compare the tree search implementations to other solvers, showing that the classical algorithmic solvers often are faster, while providing solutions of similar quality. Additionally, we analyze a recent solver based on reinforcement learning and observe that for this solver, the GNN is responsible for the competitive solution quality.
@inproceedings{bother2022whats, abstract = {Combinatorial optimization lies at the core of many real-world problems. Especially since the rise of graph neural networks (GNNs), the deep learning community has been developing solvers that derive solutions to NP-hard problems by learning the problem-specific solution structure. However, reproducing the results of these publications proves to be difficult. We make three contributions. First, we present an open-source benchmark suite for the NP-hard Maximum Independent Set problem, in both its weighted and unweighted variants. The suite offers a unified interface to various state-of-the-art traditional and machine learning-based solvers. Second, using our benchmark suite, we conduct an in-depth analysis of the popular guided tree search algorithm by Li et al. [NeurIPS 2018], testing various configurations on small and large synthetic and real-world graphs. By re-implementing their algorithm with a focus on code quality and extensibility, we show that the graph convolution network used in the tree search does not learn a meaningful representation of the solution structure, and can in fact be replaced by random values. Instead, the tree search relies on algorithmic techniques like graph kernelization to find good solutions. Thus, the results from the original publication are not reproducible. Third, we extend the analysis to compare the tree search implementations to other solvers, showing that the classical algorithmic solvers often are faster, while providing solutions of similar quality. Additionally, we analyze a recent solver based on reinforcement learning and observe that for this solver, the GNN is responsible for the competitive solution quality.}, author = {Böther, Maximilian and Kißig, Otto and Taraz, Martin and Cohen, Sarel and Seidel, Karen and Friedrich, Tobias}, booktitle = {International Conference on Learning Representations (ICLR)}, keywords = {maximilianboether sarelcohen ottokissig tobiasfriedrich martintaraz year2022 iclr karenseidel}, title = {What’s Wrong with Deep Learning in Tree Search for Combinatorial Optimization}, year = 2022 }

Bilò, Davide; Bilò, Vittorio; Lenzner, Pascal; Molitor, Louise Tolerance is Necessary for Stability: Single-Peaked Swap Schelling GamesInternational Joint Conference on Artificial Intelligence (IJCAI) 2022: 81–87
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Residential segregation in metropolitan areas is a phenomenon that can be observed all over the world. Recently, this was investigated via game-theoretic models. There, selfish agents of two types are equipped with a monotone utility function that ensures higher utility if an agent has more same-type neighbors. The agents strategically choose their location on a given graph that serves as residential area to maximize their utility. However, sociological polls suggest that real-world agents are actually favoring mixed-type neighborhoods, and hence should be modeled via non-monotone utility functions. To address this, we study Swap Schelling Games with single-peaked utility functions. Our main finding is that tolerance, i.e., agents favoring fifty-fifty neighborhoods or being in the minority, is necessary for equilibrium existence on almost regular or bipartite graphs. Regarding the quality of equilibria, we derive (almost) tight bounds on the Price of Anarchy and the Price of Stability. In particular, we show that the latter is constant on bipartite and almost regular graphs.
@inproceedings{bilo2022tolerance, abstract = {Residential segregation in metropolitan areas is a phenomenon that can be observed all over the world. Recently, this was investigated via game-theoretic models. There, selfish agents of two types are equipped with a monotone utility function that ensures higher utility if an agent has more same-type neighbors. The agents strategically choose their location on a given graph that serves as residential area to maximize their utility. However, sociological polls suggest that real-world agents are actually favoring mixed-type neighborhoods, and hence should be modeled via non-monotone utility functions. To address this, we study Swap Schelling Games with single-peaked utility functions. Our main finding is that tolerance, i.e., agents favoring fifty-fifty neighborhoods or being in the minority, is necessary for equilibrium existence on almost regular or bipartite graphs. Regarding the quality of equilibria, we derive (almost) tight bounds on the Price of Anarchy and the Price of Stability. In particular, we show that the latter is constant on bipartite and almost regular graphs.}, author = {Bilò, Davide and Bilò, Vittorio and Lenzner, Pascal and Molitor, Louise}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {ijcai louisemolitor year2022 pascallenzner}, pages = {81&ndash;87}, publisher = {ijcai.org}, title = {Tolerance is Necessary for Stability: Single-Peaked Swap Schelling Games}, year = 2022 }

Bullinger, Martin; Lenzner, Pascal; Melnichenko, Anna Network Creation with Homophilic AgentsInternational Joint Conference on Artificial Intelligence (IJCAI) 2022: 151–157
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Network Creation Games are an important framework for understanding the formation of real-world networks such as social networks. These games usually assume a set of indistinguishable agents strategically buying edges at a uniform price leading to a network among them. However, in real life, agents are heterogeneous and their relationships often display a bias towards similar agents, say of the same ethnic group. This homophilic behavior on the agent level can then lead to the emergent global phenomenon of social segregation. We initiate the study of Network Creation Games with multiple types of homophilic agents and non-uniform edge cost. Specifically, we introduce and compare two models, focusing on the perception of same-type and different-type neighboring agents, respectively. Despite their different initial conditions, both our theoretical and experimental analysis show that the resulting equilibrium networks are almost identical in the two models, indicating a robust structure of social networks under homophily. Moreover, we investigate the segregation strength of the formed networks and thereby offer new insights on understanding segregation.
@inproceedings{bullinger2022network, abstract = {Network Creation Games are an important framework for understanding the formation of real-world networks such as social networks. These games usually assume a set of indistinguishable agents strategically buying edges at a uniform price leading to a network among them. However, in real life, agents are heterogeneous and their relationships often display a bias towards similar agents, say of the same ethnic group. This homophilic behavior on the agent level can then lead to the emergent global phenomenon of social segregation. We initiate the study of Network Creation Games with multiple types of homophilic agents and non-uniform edge cost. Specifically, we introduce and compare two models, focusing on the perception of same-type and different-type neighboring agents, respectively. Despite their different initial conditions, both our theoretical and experimental analysis show that the resulting equilibrium networks are almost identical in the two models, indicating a robust structure of social networks under homophily. Moreover, we investigate the segregation strength of the formed networks and thereby offer new insights on understanding segregation.}, author = {Bullinger, Martin and Lenzner, Pascal and Melnichenko, Anna}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {ijcai annamelnichenko year2022 pascallenzner}, pages = {151&ndash;157}, publisher = {ijcai.org}, title = {Network Creation with Homophilic Agents}, year = 2022 }

Bilò, Davide; Casel, Katrin; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Lagodzinski, J.A. Gregor; Schirneck, Martin; Wietheger, Simon Fixed-Parameter Sensitivity OraclesInnovations in Theoretical Computer Science (ITCS) 2022: 23:1–23:18
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We combine ideas from distance sensitivity oracles (DSOs) and fixed-parameter tractability (FPT) to design sensitivity oracles for FPT graph problems. An oracle with sensitivity \(f\) for an FPT problem \(\Pi\) on a graph \(G\) with parameter \(k\) preprocesses \(G\) in time \(O(g(f,k) poly(n))\). When queried with a set \(F\) of at most \(f\) edges of \(G\), the oracle reports the answer to the \(\Pi\)-with the same parameter \(k\)-on the graph \(G-F\), i.e., \(G\) deprived of \(F\). The oracle should answer queries in a time that is significantly faster than merely running the best-known FPT algorithm on \(G-F\) from scratch. We design sensitivity oracles for the \(k\)-Path and the \(k\)-Vertex Cover problem. Our first oracle for \(k\)-Path has size \(O(k^{f+1})\) size and query time \(O(f \min\{f, log (f) + k\})\). We use a technique inspired by the work of Weimann and Yuster [FOCS 2010, TALG 2013] on distance sensitivity problems to reduce the space to \(O\big(\big(\frac{f+k}{f}\big)^f \big(\frac{f+k}{k}\big)^k fk \cdot \log n\big)\) at the expense of increasing the query time to \(O\big(\big(\frac{f+k}{f}\big)^f \big(\frac{f+k}{k}\big)^k f \min\{f,k\} \cdot \log n \big)\). Both oracles can be modified to handle vertex-failures, but we need to replace \(k\) with \(2k\) in all the claimed bounds. Regarding \(k\)-Vertex Cover, we design three oracles offering different trade-offs between the size and the query time. The first oracle takes \(O(3^{f+k})\) space and has \(O(2^f)\) query time, the second one has a size of \(O(2^{f+k^2+k})\) and a query time of \(O(f{+}k^2)\); finally, the third one takes \(O(fk+k^2)\) space and can be queried in time \(O(1.2738^k + fk^2)\). All our oracles are computable in time (at most) proportional to their size and the time needed to detect a \(k\)-path or \(k\)-vertex cover, respectively. We also provide an interesting connection between \(k\)-Vertex Cover and the fault-tolerant shortest path problem, by giving a DSO of size \(O(poly(f,k) \cdot n)\) with query time in \(O(poly(f,k))\), where \(k\) is the size of a vertex cover. Following our line of research connecting fault-tolerant FPT and shortest paths problems, we introduce parameterization to the computation of distance preservers. Given a graph with a fixed source \(s\) and parameters \(f\),\(k\), we study the problem of constructing polynomial-sized oracles that reports efficiently, for any target vertex \(v\) and set \(F\) of at most \(f\) edge failures, whether the distance from \(s\) to \(v\) increases at most by an additive term of \(k\) in \(G-F\). The oracle size is \(O(2^k k^2 \cdot n)\), while the time needed to answer a query is \(O(2^k f^\omega k^\omega)\), where \(\omega<2.373\) is the matrix multiplication exponent. The second problem we study is about the construction of bounded-stretch fault-tolerant preservers. We construct a subgraph with \(O(2^{fk+f+k k \cdot n)\) edges that preserves those \(s\)-\(v\)-distances that do not increase by more than \(k\) upon failure of \(F\). This improves significantly over the \( \tilde{O} (f n^{2-\frac{1}{2^f}}) \) bound in the unparameterized case by Bodwin et al. [ICALP 2017].
@inproceedings{bilo2022fixedparameter, abstract = {We combine ideas from distance sensitivity oracles (DSOs) and fixed-parameter tractability (FPT) to design sensitivity oracles for FPT graph problems. An oracle with sensitivity \(f\) for an FPT problem \(\Pi\) on a graph \(G\) with parameter \(k\) preprocesses \(G\) in time \(O(g(f,k) poly(n))\). When queried with a set \(F\) of at most \(f\) edges of \(G\), the oracle reports the answer to the \(\Pi\)-with the same parameter \(k\)-on the graph \(G-F\), i.e., \(G\) deprived of \(F\). The oracle should answer queries in a time that is significantly faster than merely running the best-known FPT algorithm on \(G-F\) from scratch. We design sensitivity oracles for the \(k\)-Path and the \(k\)-Vertex Cover problem. Our first oracle for \(k\)-Path has size \(O(k^{f+1})\) size and query time \(O(f \min\{f, \log (f) + k\})\). We use a technique inspired by the work of Weimann and Yuster [FOCS 2010, TALG 2013] on distance sensitivity problems to reduce the space to \(O\big(\big(\frac{f+k}{f}\big)^f \big(\frac{f+k}{k}\big)^k fk \cdot \log n\big)\) at the expense of increasing the query time to \(O\big(\big(\frac{f+k}{f}\big)^f \big(\frac{f+k}{k}\big)^k f \min\{f,k\} \cdot \log n \big)\). Both oracles can be modified to handle vertex-failures, but we need to replace \(k\) with \(2k\) in all the claimed bounds. Regarding \(k\)-Vertex Cover, we design three oracles offering different trade-offs between the size and the query time. The first oracle takes \(O(3^{f+k})\) space and has \(O(2^f)\) query time, the second one has a size of \(O(2^{f+k^2+k})\) and a query time of \(O(f{+}k^2)\); finally, the third one takes \(O(fk+k^2)\) space and can be queried in time \(O(1.2738^k + fk^2)\). All our oracles are computable in time (at most) proportional to their size and the time needed to detect a \(k\)-path or \(k\)-vertex cover, respectively. We also provide an interesting connection between \(k\)-Vertex Cover and the fault-tolerant shortest path problem, by giving a DSO of size \(O(poly(f,k) \cdot n)\) with query time in \(O(poly(f,k))\), where \(k\) is the size of a vertex cover. Following our line of research connecting fault-tolerant FPT and shortest paths problems, we introduce parameterization to the computation of distance preservers. Given a graph with a fixed source \(s\) and parameters \(f\),\(k\), we study the problem of constructing polynomial-sized oracles that reports efficiently, for any target vertex \(v\) and set \(F\) of at most \(f\) edge failures, whether the distance from \(s\) to \(v\) increases at most by an additive term of \(k\) in \(G-F\). The oracle size is \(O(2^k k^2 \cdot n)\), while the time needed to answer a query is \(O(2^k f^\omega k^\omega)\), where \(\omega<2.373\) is the matrix multiplication exponent. The second problem we study is about the construction of bounded-stretch fault-tolerant preservers. We construct a subgraph with \(O(2^{fk+f+k} k \cdot n)\) edges that preserves those \(s\)-\(v\)-distances that do not increase by more than \(k\) upon failure of \(F\). This improves significantly over the \( \tilde{O} (f n^{2-\frac{1}{2^f}}) \) bound in the unparameterized case by Bodwin et al. [ICALP 2017].}, author = {Bilò, Davide and Casel, Katrin and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Lagodzinski, J.A. Gregor and Schirneck, Martin and Wietheger, Simon}, booktitle = {Innovations in Theoretical Computer Science (ITCS)}, keywords = {sarelcohen gregorlagodzinski davidebilo katrincasel simonwietheger tobiasfriedrich itcs keertichoudhary year2022 martinschirneck}, pages = {23:1-23:18}, title = {Fixed-Parameter Sensitivity Oracles}, year = 2022 }

Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Rajabi, Amirhossein Escaping Local Optima With Local Search: A Theory-Driven DiscussionParallel Problem Solving from Nature (PPSN) 2022: 442–455
Best Paper Award and Best Poster Award
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Local search is the most basic strategy in optimization settings when no specific problem knowledge is employed. While this strategy finds good solutions for certain optimization problems, it generally suffers from getting stuck in local optima. This stagnation can be avoided if local search is modified. Depending on the optimization landscape, different modifications vary in their success. We discuss several features of optimization landscapes and give analyses as examples for how they affect the performance of modifications of local search. We consider modifying random local search by restarting it and by considering larger search radii. The landscape features we analyze include the number of local optima, the distance between different optima, as well as the local landscape around a local optimum. For each feature, we show which modifications of local search handle them well and which do not.
@inproceedings{friedrich2022escaping, abstract = {Local search is the most basic strategy in optimization settings when no specific problem knowledge is employed. While this strategy finds good solutions for certain optimization problems, it generally suffers from getting stuck in local optima. This stagnation can be avoided if local search is modified. Depending on the optimization landscape, different modifications vary in their success. We discuss several features of optimization landscapes and give analyses as examples for how they affect the performance of modifications of local search. We consider modifying random local search by restarting it and by considering larger search radii. The landscape features we analyze include the number of local optima, the distance between different optima, as well as the local landscape around a local optimum. For each feature, we show which modifications of local search handle them well and which do not.}, author = {Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Rajabi, Amirhossein}, booktitle = {Parallel Problem Solving from Nature (PPSN)}, keywords = {martinskrejca timokoetzing tobiasfriedrich amirhosseinrajabi year2022 ppsn}, note = {Best Paper Award and Best Poster Award}, pages = {442-455}, title = {Escaping Local Optima With Local Search: A Theory-Driven Discussion}, year = 2022 }

Friedrich, Tobias; Kötzing, Timo; Neumann, Frank; Radhakrishnan, Aishwarya Theoretical Study of Optimizing Rugge Landscapes with the cGAParallel Problem Solving From Nature (PPSN) 2022: 586–599
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Estimation of distribution algorithms (EDAs) provide a distribution-based approach for optimization which adapts its probability distribution during the run of the algorithm. We contribute to the theoretical understanding of EDAs and point out that their distribution approach makes them more suitable to deal with rugged fitness landscapes than classical local search algorithms. Concretely, we make the OneMax function rugged by adding noise to each fitness value. The cGA can nevertheless find solutions with \(n (1 - \epsilon )\) many 1s, even for high variance of noise. In contrast to this, RLS and the (1+1) EA, with high probability, only find solutions with \(n(1/2 + o(1)) \) many 1s, even for noise with small variance.
@inproceedings{friedrich2022theoretical, abstract = {Estimation of distribution algorithms (EDAs) provide a distribution-based approach for optimization which adapts its probability distribution during the run of the algorithm. We contribute to the theoretical understanding of EDAs and point out that their distribution approach makes them more suitable to deal with rugged fitness landscapes than classical local search algorithms. Concretely, we make the OneMax function rugged by adding noise to each fitness value. The cGA can nevertheless find solutions with \(n (1 - \epsilon )\) many 1s, even for high variance of noise. In contrast to this, RLS and the (1+1) EA, with high probability, only find solutions with \(n(1/2 + o(1)) \) many 1s, even for noise with small variance.}, author = {Friedrich, Tobias and Kötzing, Timo and Neumann, Frank and Radhakrishnan, Aishwarya}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, keywords = {aishwaryaradhakrishnan timokoetzing tobiasfriedrich frankneumann year2022 ppsn}, pages = {586–599}, title = {Theoretical Study of Optimizing Rugge Landscapes with the cGA}, year = 2022 }

Bläsius, Thomas; Fischbeck, Philipp; Gottesbüren, Lars; Hamann, Michael; Heuer, Tobias; Spinner, Jonas; Weyand, Christopher; Wilhelm, Marcus A Branch-and-Bound Algorithm for Cluster EditingSymposium on Experimental Algorithms (SEA) 2022: 13:1–13:19
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The editing problem asks to transform a given graph into a disjoint union of cliques by inserting and deleting as few edges as possible. We describe and evaluate an exact branch-and-bound algorithm for cluster editing. For this, we introduce new reduction rules and adapt existing ones. Moreover, we generalize a known packing technique to obtain lower bounds and experimentally show that it contributes significantly to the performance of the solver. Our experiments further evaluate the effectiveness of the different reduction rules and examine the effects of structural properties of the input graph on solver performance. Our solver won the exact track of the 2021 PACE challenge.
@inproceedings{blasius2022branchandbound, abstract = {The editing problem asks to transform a given graph into a disjoint union of cliques by inserting and deleting as few edges as possible. We describe and evaluate an exact branch-and-bound algorithm for cluster editing. For this, we introduce new reduction rules and adapt existing ones. Moreover, we generalize a known packing technique to obtain lower bounds and experimentally show that it contributes significantly to the performance of the solver. Our experiments further evaluate the effectiveness of the different reduction rules and examine the effects of structural properties of the input graph on solver performance. Our solver won the exact track of the 2021 PACE challenge.}, author = {Bläsius, Thomas and Fischbeck, Philipp and Gottesbüren, Lars and Hamann, Michael and Heuer, Tobias and Spinner, Jonas and Weyand, Christopher and Wilhelm, Marcus}, booktitle = {Symposium on Experimental Algorithms (SEA)}, keywords = {philippfischbeck larsgottesbueren thomasblaesius michaelhamann tobiasheuer christopherweyand year2022 marcuswilhelm jonasspinner sea}, pages = {13:1&ndash;13:19}, title = {A Branch-and-Bound Algorithm for Cluster Editing}, year = 2022 }

Cohen, Sarel; Fischbeck, Philipp; Friedrich, Tobias; Krejca, Martin S.; Sauerwald, Thomas Accelerated Information Dissemination on Networks with Local and Global EdgesStructural Information and Communication Complexity (SIROCCO) 2022: 79–97
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Bootstrap percolation is a classical model for the spread of information in a network. In the round-based version, nodes of an undirected graph become active once at least \(r\) neighbors were active in the previous round. We propose the \emph{perturbed percolation process: a superposition of two percolation processes on the same node set. One process acts on a local graph with activation threshold~\(1\), the other acts on a global graph with threshold \(r\)~-- representing local and global edges, respectively. We consider grid-like local graphs and expanders as global graphs on~\(n\) nodes. For the extreme case \(r = 1\), all nodes are active after \(O(\log n)\) rounds, while the process spreads only polynomially fast for the other extreme case \(r \geq n\). For a range of suitable values of~\(r\), we prove that the process exhibits both phases of the above extremes: It starts with a polynomial growth and eventually transitions from at most \(cn\) to~\(n\) active nodes, for some constant \(c in (0, 1)\), in \(O(\log n)\) rounds. We observe this behavior also empirically, considering additional global-graph models.
@inproceedings{cohen2022accelerated, abstract = {Bootstrap percolation is a classical model for the spread of information in a network. In the round-based version, nodes of an undirected graph become active once at least \(r\) neighbors were active in the previous round. We propose the \emph{perturbed} percolation process: a superposition of two percolation processes on the same node set. One process acts on a local graph with activation threshold&nbsp;\(1\), the other acts on a global graph with threshold \(r\)&nbsp;&ndash; representing local and global edges, respectively. We consider grid-like local graphs and expanders as global graphs on&nbsp;\(n\) nodes. For the extreme case \(r = 1\), all nodes are active after \(O(\log n)\) rounds, while the process spreads only polynomially fast for the other extreme case \(r \geq n\). For a range of suitable values of&nbsp;\(r\), we prove that the process exhibits both phases of the above extremes: It starts with a polynomial growth and eventually transitions from at most \(cn\) to&nbsp;\(n\) active nodes, for some constant \(c \in (0, 1)\), in \(O(\log n)\) rounds. We observe this behavior also empirically, considering additional global-graph models.}, author = {Cohen, Sarel and Fischbeck, Philipp and Friedrich, Tobias and Krejca, Martin S. and Sauerwald, Thomas}, booktitle = {Structural Information and Communication Complexity (SIROCCO)}, keywords = {sarelcohen philippfischbeck martinskrejca sirocco tobiasfriedrich year2022 thomassauerwald}, pages = {79&ndash;97}, title = {Accelerated Information Dissemination on Networks with Local and Global Edges}, year = 2022 }

Fomin, Fedor V.; Golovach, Petr A.; Sagunov, Danil; Simonov, Kirill Algorithmic Extensions of Dirac’s TheoremSymposium on Discrete Algorithms (SODA) 2022: 406–416
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is a randomized algorithm, that given a colored \(n\)-vertex undirected graph, vertices \(s\) and \(t\), and an integer \(k\), finds an \((s,t)\)-path containing at least \(k\) different colors in time \(2^k n^\mathcal{O(1)}\). This is the first FPT algorithm for this problem, and it generalizes the algorithm of Björklund, Husfeldt, and Taslaman [SODA 2012] on finding a path through \(k\) specified vertices. It also implies the first \(2^k n^\mathcal{O(1)}\) time algorithm for finding an \(s,t)\)-path of length at least \(k\). Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an \(n\)-vertex undirected graph \(G\), a matroid \(M\) whose elements correspond to the vertices of \(G\) and which is represented over a finite field of order \(q\), a positive integer weight function on the vertices of \(G\), two sets of vertices \(S,T subseteq V(G)\), and integers \(p,k,w\), and the task is to find \(p\) vertex-disjoint paths from \(S\) to \(T\) so that the union of the vertices of these paths contains an independent set of \(M\) of cardinality \(k\) and weight \(w\), while minimizing the sum of the lengths of the paths. We give a \(2^{p+\mathcal{O(k^2 log (q+k)) n^\mathcal{O(1) w\) time randomized algorithm for this problem.
@inproceedings{fomin2022algorithmic, abstract = {We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is a randomized algorithm, that given a colored \(n\)-vertex undirected graph, vertices \(s\) and \(t\), and an integer \(k\), finds an \((s,t)\)-path containing at least \(k\) different colors in time \(2^k n^{\mathcal{O}(1)}\). This is the first FPT algorithm for this problem, and it generalizes the algorithm of Bj{ö}rklund, Husfeldt, and Taslaman [SODA 2012] on finding a path through \(k\) specified vertices. It also implies the first \(2^k n^{\mathcal{O}(1)}\) time algorithm for finding an \(s,t)\)-path of length at least \(k\). Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an \(n\)-vertex undirected graph \(G\), a matroid \(M\) whose elements correspond to the vertices of \(G\) and which is represented over a finite field of order \(q\), a positive integer weight function on the vertices of \(G\), two sets of vertices \(S,T \subseteq V(G)\), and integers \(p,k,w\), and the task is to find \(p\) vertex-disjoint paths from \(S\) to \(T\) so that the union of the vertices of these paths contains an independent set of \(M\) of cardinality \(k\) and weight \(w\), while minimizing the sum of the lengths of the paths. We give a \(2^{p+\mathcal{O}(k^2 \log (q+k))} n^{\mathcal{O}(1)} w\) time randomized algorithm for this problem.}, author = {Fomin, Fedor V. and Golovach, Petr A. and Sagunov, Danil and Simonov, Kirill}, booktitle = {Symposium on Discrete Algorithms (SODA)}, keywords = {sys:relevantfor:ae kirillsimonov soda year2022}, pages = {406-416}, title = {Algorithmic Extensions of Dirac's Theorem}, year = 2022 }

Bazgan, Cristina; Casel, Katrin; Cazals, Pierre Dense Graph Partitioning on sparse and dense graphs.Scandinavian Workshop Algorithm Theory (SWAT) 2022
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We consider the problem of partitioning a graph into a non-fixed number of non-overlapping subgraphs of maximum density. The density of a partition is the sum of the densities of the subgraphs, where the density of a subgraph is its average degree, that is, the ratio of its number of edges and its number of vertices. This problem, called Dense Graph Partition, is known to be NP-hard on general graphs and polynomial-time solvable on trees, and polynomial-time 2-approximable. In this paper we study the restriction of Dense Graph Partition to particular sparse and dense graph classes. In particular, we prove that it is NP-hard on dense bipartite graphs as well as on cubic graphs. On dense graphs on \(n\) vertices, it is polynomial-time solvable on graphs with minimum degree \(n-3\) and NP-hard on \((n-4)\)-regular graphs. We prove that it is polynomial-time 4/3-approximable on cubic graphs and admits an efficient polynomial-time approximation scheme on graphs of minimum degree \(n-t\) for any constant \(t\geq 4\).
@inproceedings{bazgan2022dense, abstract = {We consider the problem of partitioning a graph into a non-fixed number of non-overlapping subgraphs of maximum density. The density of a partition is the sum of the densities of the subgraphs, where the density of a subgraph is its average degree, that is, the ratio of its number of edges and its number of vertices. This problem, called Dense Graph Partition, is known to be NP-hard on general graphs and polynomial-time solvable on trees, and polynomial-time 2-approximable. In this paper we study the restriction of Dense Graph Partition to particular sparse and dense graph classes. In particular, we prove that it is NP-hard on dense bipartite graphs as well as on cubic graphs. On dense graphs on \(n\) vertices, it is polynomial-time solvable on graphs with minimum degree \(n-3\) and NP-hard on \((n-4)\)-regular graphs. We prove that it is polynomial-time 4/3-approximable on cubic graphs and admits an efficient polynomial-time approximation scheme on graphs of minimum degree \(n-t\) for any constant \(t\geq 4\).}, author = {Bazgan, Cristina and Casel, Katrin and Cazals, Pierre}, booktitle = {Scandinavian Workshop Algorithm Theory (SWAT)}, keywords = {swat katrincasel year2022}, title = {Dense Graph Partitioning on sparse and dense graphs.}, year = 2022 }