2024 [ nach oben ]

Friedrich, Tobias; Göbel, Andres; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus Analysis of the survival time of the SIRS process via expansionElectronic Journal of Probability 2024: 1–29
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study the SIRS process---a continuous-time Markov chain modeling the spread of infections on graphs. In this model, vertices are either susceptible, infected, or recovered. Each infected vertex becomes recovered at rate 1 and infects each of its susceptible neighbors independently at rate~\(\lambda\), and each recovered vertex becomes susceptible at a rate~\(\varrho\), which we assume to be independent of the graph size. A central quantity of the SIRS process is the time until no vertex is infected, known as the survival time. Surprisingly though, to the best of our knowledge, all known rigorous theoretical results that exist so far immediately carry over from the related SIS model and do not completely explain the behavior of the SIRS process. We address this imbalance by conducting theoretical analyses of the SIRS process via the expansion properties of the underlying graph. Our first result shows that the expected survival time of the SIRS process on stars is at most polynomial in the graph size for any value of~\(\lambda\). This behavior is fundamentally different from the SIS process, where the expected survival time is exponential already for small infection rates. This raises the question of which graph properties result in an exponential survival time. Our main result is an exponential lower bound of the expected survival time of the SIRS process on expander graphs. Specifically, we show that on expander graphs \(G\) with \(n\) vertices, degree close to \(d\), and sufficiently small spectral expansion, the SIRS process has expected survival time at least exponential in \(n\) when \(\lambda \geq c/d\) for a constant \(c > 1\). Previous results on the SIS process show that this bound is almost tight. Additionally, our result holds even if \(G\) is a subgraph. Notably, our result implies an almost-tight threshold for Erdos-Renyi-graphs and a regime of exponential survival time for complex network models. The proof of our main result draws inspiration from Lyapunov functions used in mean-field theory to devise a two-dimensional potential function and from applying a negative-drift theorem to show that the expected survival time is exponential.
@article{friedrich2024analysis, abstract = {We study the SIRS process—a continuous-time Markov chain modeling the spread of infections on graphs. In this model, vertices are either susceptible, infected, or recovered. Each infected vertex becomes recovered at rate 1 and infects each of its susceptible neighbors independently at rate \(\lambda\), and each recovered vertex becomes susceptible at a rate \(\varrho\), which we assume to be independent of the graph size. A central quantity of the SIRS process is the time until no vertex is infected, known as the survival time. Surprisingly though, to the best of our knowledge, all known rigorous theoretical results that exist so far immediately carry over from the related SIS model and do not completely explain the behavior of the SIRS process. We address this imbalance by conducting theoretical analyses of the SIRS process via the expansion properties of the underlying graph. Our first result shows that the expected survival time of the SIRS process on stars is at most polynomial in the graph size for any value of \(\lambda\). This behavior is fundamentally different from the SIS process, where the expected survival time is exponential already for small infection rates. This raises the question of which graph properties result in an exponential survival time. Our main result is an exponential lower bound of the expected survival time of the SIRS process on expander graphs. Specifically, we show that on expander graphs \(G\) with \(n\) vertices, degree close to \(d\), and sufficiently small spectral expansion, the SIRS process has expected survival time at least exponential in \(n\) when \(\lambda \geq c/d\) for a constant \(c > 1\). Previous results on the SIS process show that this bound is almost tight. Additionally, our result holds even if \(G\) is a subgraph. Notably, our result implies an almost-tight threshold for Erdos-Renyi-graphs and a regime of exponential survival time for complex network models. The proof of our main result draws inspiration from Lyapunov functions used in mean-field theory to devise a two-dimensional potential function and from applying a negative-drift theorem to show that the expected survival time is exponential.}, author = {Friedrich, Tobias and Göbel, Andres and Klodt, Nicolas and Krejca, Martin S. and Pappik, Marcus}, journal = {Electronic Journal of Probability}, keywords = {andreasgoebel ejp marcuspappik martinskrejca nicolasklodt tobiasfriedrich year2024}, pages = {1-29}, title = {Analysis of the survival time of the SIRS process via expansion}, volume = 29, year = 2024 }

Friedrich, Tobias; Göbel, Andreas; Katzmann, Maximilian; Schiller, Leon Cliques in High-Dimensional Geometric Inhomogeneous Random GraphsSIAM Journal on Discrete Mathematics 2024: 1943–2000
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
A recent trend in the context of graph theory is to bring theoretical analyses closer to empirical observations, by focusing the studies on random graph models that are used to represent practical instances. There, it was observed that geometric inhomogeneous random graphs (GIRGs) yield good representations of complex real-world networks, by expressing edge probabilities as a function that depends on (heterogeneous) vertex weights and distances in some underlying geometric space that the vertices are distributed in. While most of the parameters of the model are understood well, it was unclear how the dimensionality of the ground space affects the structure of the graphs. In this paper, we complement existing research into the dimension of geometric random graph models and the ongoing study of determining the dimensionality of real-world networks, by studying how the structure of GIRGs changes as the number of dimensions increases. We prove that, in the limit, GIRGs approach non-geometric inhomogeneous random graphs and present insights on how quickly the decay of the geometry impacts important graph structures. In particular, we study the expected number of cliques of a given size as well as the clique number and characterize phase transitions at which their behavior changes fundamentally. Finally, our insights help in better understanding previous results about the impact of the dimensionality on geometric random graphs.
@article{friedrich2024cliques, abstract = {A recent trend in the context of graph theory is to bring theoretical analyses closer to empirical observations, by focusing the studies on random graph models that are used to represent practical instances. There, it was observed that geometric inhomogeneous random graphs (GIRGs) yield good representations of complex real-world networks, by expressing edge probabilities as a function that depends on (heterogeneous) vertex weights and distances in some underlying geometric space that the vertices are distributed in. While most of the parameters of the model are understood well, it was unclear how the dimensionality of the ground space affects the structure of the graphs. In this paper, we complement existing research into the dimension of geometric random graph models and the ongoing study of determining the dimensionality of real-world networks, by studying how the structure of GIRGs changes as the number of dimensions increases. We prove that, in the limit, GIRGs approach non-geometric inhomogeneous random graphs and present insights on how quickly the decay of the geometry impacts important graph structures. In particular, we study the expected number of cliques of a given size as well as the clique number and characterize phase transitions at which their behavior changes fundamentally. Finally, our insights help in better understanding previous results about the impact of the dimensionality on geometric random graphs.}, author = {Friedrich, Tobias and Göbel, Andreas and Katzmann, Maximilian and Schiller, Leon}, journal = {SIAM Journal on Discrete Mathematics}, keywords = {SIMDA andreasgoebel tobiasfriedrich year2024}, number = 2, pages = {1943-2000}, title = {Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs}, volume = 38, year = 2024 }

Friedrich, Tobias; Göbel, Andreas; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus The Irrelevance of Influencers: Information Diffusion with Re-Activation and Immunity Lasts Exponentially Long on Social Network ModelsAnnual AAAI Conference on Artificial Intelligence 2024
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Information diffusion models on networks are at the forefront of AI research. The dynamics of such models typically follow stochastic models from epidemiology, used to model not only infections but various phenomena, including the behavior of computer viruses and viral marketing campaigns. A core question in this setting is how to efficiently detect the most influential vertices in the host graph such that the infection survives the longest. In processes that incorporate re-infection of the vertices, such as the SIS process, theoretical studies identify parameter thresholds where the survival time of the process rapidly transitions from logarithmic to super-polynomial. These results contradict the intuition that the starting configuration is relevant, since the process will always either die out fast or survive almost indefinitely. A shortcoming of these results is that models incorporating short-term immunity (or creative advertisement fatigue) have not been subjected to such a theoretical analysis so far. We reduce this gap in the literature by studying the SIRS process, a more realistic model, which besides re-infection additionally incorporates short-term immunity. On complex network models, we identify parameter regimes for which the process survives exponentially long, and we get a tight threshold for random graphs. Underlying these results is our main technical contribution, showing a threshold behavior for the survival time of the SIRS process on graphs with large expander subgraphs, such as social network models.
@inproceedings{friedrich2024irrelevance, abstract = {Information diffusion models on networks are at the forefront of AI research. The dynamics of such models typically follow stochastic models from epidemiology, used to model not only infections but various phenomena, including the behavior of computer viruses and viral marketing campaigns. A core question in this setting is how to efficiently detect the most influential vertices in the host graph such that the infection survives the longest. In processes that incorporate re-infection of the vertices, such as the SIS process, theoretical studies identify parameter thresholds where the survival time of the process rapidly transitions from logarithmic to super-polynomial. These results contradict the intuition that the starting configuration is relevant, since the process will always either die out fast or survive almost indefinitely. A shortcoming of these results is that models incorporating short-term immunity (or creative advertisement fatigue) have not been subjected to such a theoretical analysis so far. We reduce this gap in the literature by studying the SIRS process, a more realistic model, which besides re-infection additionally incorporates short-term immunity. On complex network models, we identify parameter regimes for which the process survives exponentially long, and we get a tight threshold for random graphs. Underlying these results is our main technical contribution, showing a threshold behavior for the survival time of the SIRS process on graphs with large expander subgraphs, such as social network models.}, author = {Friedrich, Tobias and Göbel, Andreas and Klodt, Nicolas and Krejca, Martin S. and Pappik, Marcus}, booktitle = {Annual AAAI Conference on Artificial Intelligence}, keywords = {aaai andreasgoebel marcuspappik martinskrejca nicolasklodt tobiasfriedrich year2024}, title = {The Irrelevance of Influencers: Information Diffusion with Re-Activation and Immunity Lasts Exponentially Long on Social Network Models}, year = 2024 }

Friedrich, Tobias; Göbel, Andreas; Katzmann, Maximilian; Schiller, Leon Real-World Networks Are Low-Dimensional: Theoretical and Practical AssessmentInternational Joint Conference on Artificial Intelligence (IJCAI) 2024
[ Abstract ] [ BibTeX ] [ Download ]
 
Recent empirical evidence suggests that real-world networks have very low underlying dimensionality. We provide a theoretical explanation for this phenomenon as well as develop a linear-time algorithm for detecting the underlying dimensionality of such networks. Our theoretical analysis considers geometric inhomogeneous random graphs (GIRGs), a geometric random graph model, which captures a variety of properties observed in real-world networks. These properties include a heterogeneous degree distribution and non-vanishing clustering coefficient, which is the probability that two random neighbors of a vertex are adjacent. Our first result shows that the clustering coefficient of GIRGs scales inverse exponentially with respect to the number of dimensions d, when the latter is at most logarithmic in n, the number of vertices. Hence, for a GIRG to behave like many real-world networks and have a non-vanishing clustering coefficient, it must come from a geometric space of o(log n) dimensions. Our analysis on GIRGs allows us to obtain a linear-time algorithm for determining the dimensionality of a network. Our algorithm bridges the gap between theory and practice, as it comes with a rigorous proof of correctness and yields results comparable to prior empirical approaches, as indicated by our experiments on real-world instances. The efficiency of our algorithm makes it applicable to very large data-sets. We conclude that very low dimensionalities (from 1 to 10) are needed to explain properties of real-world networks.
@inproceedings{friedrich2024realworld, abstract = {Recent empirical evidence suggests that real-world networks have very low underlying dimensionality. We provide a theoretical explanation for this phenomenon as well as develop a linear-time algorithm for detecting the underlying dimensionality of such networks. Our theoretical analysis considers geometric inhomogeneous random graphs (GIRGs), a geometric random graph model, which captures a variety of properties observed in real-world networks. These properties include a heterogeneous degree distribution and non-vanishing clustering coefficient, which is the probability that two random neighbors of a vertex are adjacent. Our first result shows that the clustering coefficient of GIRGs scales inverse exponentially with respect to the number of dimensions d, when the latter is at most logarithmic in n, the number of vertices. Hence, for a GIRG to behave like many real-world networks and have a non-vanishing clustering coefficient, it must come from a geometric space of o(log n) dimensions. Our analysis on GIRGs allows us to obtain a linear-time algorithm for determining the dimensionality of a network. Our algorithm bridges the gap between theory and practice, as it comes with a rigorous proof of correctness and yields results comparable to prior empirical approaches, as indicated by our experiments on real-world instances. The efficiency of our algorithm makes it applicable to very large data-sets. We conclude that very low dimensionalities (from 1 to 10) are needed to explain properties of real-world networks.}, author = {Friedrich, Tobias and Göbel, Andreas and Katzmann, Maximilian and Schiller, Leon}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {andreasgoebel ijcai tobiasfriedrich year2024}, title = {Real-World Networks Are Low-Dimensional: Theoretical and Practical Assessment}, year = 2024 }

Göbel, Andreas; Goldberg, Leslie Ann; Roth, Marc The Weisfeiler-Leman Dimension of Conjunctive QueriesSymposium on Principles of Database Systems (PODS) 2024
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The Weisfeiler-Leman (WL) dimension of a graph parameter f is the minimum k such that, if G1 and G2 are indistinguishable by the k-dimensional WL-algorithm then f(G1)=f(G2). The WL-dimension of f is ∞ if no such k exists. We study the WL-dimension of graph parameters characterised by the number of answers from a fixed conjunctive query to the graph. Given a conjunctive query φ, we quantify the WL-dimension of the function that maps every graph G to the number of answers of φ in G. The works of Dvorák (J. Graph Theory 2010), Dell, Grohe, and Rattan (ICALP 2018), and Neuen (ArXiv 2023) have answered this question for full conjunctive queries, which are conjunctive queries without existentially quantified variables. For such queries φ, the WL-dimension is equal to the treewidth of the Gaifman graph of φ. In this work, we give a characterisation that applies to all conjunctive qureies. Given any conjunctive query φ, we prove that its WL-dimension is equal to the semantic extension width sew(φ), a novel width measure that can be thought of as a combination of the treewidth of φ and its quantified star size, an invariant introduced by Durand and Mengel (ICDT 2013) describing how the existentially quantified variables of φ are connected with the free variables. Using the recently established equivalence between the WL-algorithm and higher-order Graph Neural Networks (GNNs) due to Morris et al. (AAAI 2019), we obtain as a consequence that the function counting answers to a conjunctive query φ cannot be computed by GNNs of order smaller than sew(φ).
@inproceedings{gobel2024weisfeilerleman, abstract = {The Weisfeiler-Leman (WL) dimension of a graph parameter f is the minimum k such that, if G1 and G2 are indistinguishable by the k-dimensional WL-algorithm then f(G1)=f(G2). The WL-dimension of f is ∞ if no such k exists. We study the WL-dimension of graph parameters characterised by the number of answers from a fixed conjunctive query to the graph. Given a conjunctive query φ, we quantify the WL-dimension of the function that maps every graph G to the number of answers of φ in G. The works of Dvorák (J. Graph Theory 2010), Dell, Grohe, and Rattan (ICALP 2018), and Neuen (ArXiv 2023) have answered this question for full conjunctive queries, which are conjunctive queries without existentially quantified variables. For such queries φ, the WL-dimension is equal to the treewidth of the Gaifman graph of φ. In this work, we give a characterisation that applies to all conjunctive qureies. Given any conjunctive query φ, we prove that its WL-dimension is equal to the semantic extension width sew(φ), a novel width measure that can be thought of as a combination of the treewidth of φ and its quantified star size, an invariant introduced by Durand and Mengel (ICDT 2013) describing how the existentially quantified variables of φ are connected with the free variables. Using the recently established equivalence between the WL-algorithm and higher-order Graph Neural Networks (GNNs) due to Morris et al. (AAAI 2019), we obtain as a consequence that the function counting answers to a conjunctive query φ cannot be computed by GNNs of order smaller than sew(φ).}, author = {Göbel, Andreas and Goldberg, Leslie Ann and Roth, Marc}, booktitle = {Symposium on Principles of Database Systems (PODS)}, keywords = {sys:relevantfor:ae andreasgoebel pods year2024}, title = {The Weisfeiler-Leman Dimension of Conjunctive Queries}, year = 2024 }

Friedrich, Tobias; Göbel, Andreas; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus From Market Saturation to Social Reinforcement: Understanding the Impact of Non-Linearity in Information Diffusion ModelsThe 23rd International Conference on Autonomous Agents and Multi-Agent Systems 2024
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Diffusion of information in networks is at the core of many problems in AI. Common examples include the spread of ideas and rumors as well as marketing campaigns. Typically, information diffuses at a non-linear rate, for example, if markets become saturated or if users of social networks reinforce each other's opinions. Despite these characteristics, this area has seen little research, compared to the vast amount of results for linear models, which exhibit less complex dynamics. Especially, when considering the possibility of re-infection, no fully rigorous guarantees exist so far. We address this shortcoming by studying a very general non-linear diffusion model that captures saturation as well as reinforcement. More precisely, we consider a variant of the SIS model in which vertices get infected at a rate that scales polynomially in the number of their infected neighbors, weighted by an infection coefficient \(\lambda\). We give the first fully rigorous results for thresholds of \(\lambda\) at which the expected survival time becomes super-polynomial. For cliques we show that when the infection rate scales sub-linearly, the threshold only shifts by a poly-logarithmic factor, compared to the standard SIS model. In contrast, super-linear scaling changes the process considerably and shifts the threshold by a polynomial term. For stars, sub-linear and super-linear scaling behave similar and both shift the threshold by a polynomial factor. Our bounds are almost tight, as they are only apart by at most a poly-logarithmic factor from the lower thresholds, at which the expected survival time is logarithmic.
@inproceedings{friedrich2024market, abstract = {Diffusion of information in networks is at the core of many problems in AI. Common examples include the spread of ideas and rumors as well as marketing campaigns. Typically, information diffuses at a non-linear rate, for example, if markets become saturated or if users of social networks reinforce each other's opinions. Despite these characteristics, this area has seen little research, compared to the vast amount of results for linear models, which exhibit less complex dynamics. Especially, when considering the possibility of re-infection, no fully rigorous guarantees exist so far. We address this shortcoming by studying a very general non-linear diffusion model that captures saturation as well as reinforcement. More precisely, we consider a variant of the SIS model in which vertices get infected at a rate that scales polynomially in the number of their infected neighbors, weighted by an infection coefficient \(\lambda\). We give the first fully rigorous results for thresholds of \(\lambda\) at which the expected survival time becomes super-polynomial. For cliques we show that when the infection rate scales sub-linearly, the threshold only shifts by a poly-logarithmic factor, compared to the standard SIS model. In contrast, super-linear scaling changes the process considerably and shifts the threshold by a polynomial term. For stars, sub-linear and super-linear scaling behave similar and both shift the threshold by a polynomial factor. Our bounds are almost tight, as they are only apart by at most a poly-logarithmic factor from the lower thresholds, at which the expected survival time is logarithmic.}, author = {Friedrich, Tobias and Göbel, Andreas and Klodt, Nicolas and Krejca, Martin S. and Pappik, Marcus}, booktitle = {The 23rd International Conference on Autonomous Agents and Multi-Agent Systems}, keywords = {aamas andreasgoebel marcuspappik martinskrejca nicolasklodt tobiasfriedrich year2024}, title = {From Market Saturation to Social Reinforcement: Understanding the Impact of Non-Linearity in Information Diffusion Models}, year = 2024 }

2023 [ nach oben ]

Friedrich, Tobias; Göbel, Andreas; Krejca, Martin S.; Pappik, Marcus Polymer Dynamics via Cliques: New Conditions for ApproximationsTheoretical Computer Science 2023: 230–252
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Abstract polymer models are systems of weighted objects, called polymers, equipped with an incompatibility relation. An important quantity associated with such models is the partition function, which is the weighted sum over all sets of compatible polymers. Various approximation problems reduce to approximating the partition function of a polymer model. Central to the existence of such approximation algorithms are weight conditions of the respective polymer model. Such conditions are derived either via complex analysis or via probabilistic arguments. We follow the latter path and establish a new condition—the clique dynamics condition—, which is less restrictive than the ones in the literature. We introduce a new Markov chain where the clique dynamics condition implies rapid mixing by utilizing cliques of incompatible polymers that naturally arise from the translation of algorithmic problems into polymer models. This leads to improved parameter ranges for several approximation algorithms, such as a factor of at least \(2^{1/\alpha}\) for the hard-core model on bipartite \(\alpha\)-expanders.
@article{friedrich2023polymer, abstract = {Abstract polymer models are systems of weighted objects, called polymers, equipped with an incompatibility relation. An important quantity associated with such models is the partition function, which is the weighted sum over all sets of compatible polymers. Various approximation problems reduce to approximating the partition function of a polymer model. Central to the existence of such approximation algorithms are weight conditions of the respective polymer model. Such conditions are derived either via complex analysis or via probabilistic arguments. We follow the latter path and establish a new condition—the clique dynamics condition—, which is less restrictive than the ones in the literature. We introduce a new Markov chain where the clique dynamics condition implies rapid mixing by utilizing cliques of incompatible polymers that naturally arise from the translation of algorithmic problems into polymer models. This leads to improved parameter ranges for several approximation algorithms, such as a factor of at least \(2^{1/\alpha}\) for the hard-core model on bipartite \(\alpha\)-expanders.}, author = {Friedrich, Tobias and Göbel, Andreas and Krejca, Martin S. and Pappik, Marcus}, journal = {Theoretical Computer Science}, keywords = {andreasgoebel marcuspappik martinskrejca tcs tobiasfriedrich year2023}, pages = {230-252}, title = {Polymer Dynamics via Cliques: New Conditions for Approximations}, volume = 942, year = 2023 }

Friedrich, Tobias; Göbel, Andreas; Katzmann, Maximilian; Schiller, Leon Cliques in High-Dimensional Geometric Inhomogeneous Random GraphsInternational Colloquium on Automata, Languages and Programming (ICALP) 2023: 62:1–62:13
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
A recent trend in the context of graph theory is to bring theoretical analyses closer to empirical observations, by focusing the studies on random graph models that are used to represent practical instances. There, it was observed that geometric inhomogeneous random graphs (GIRGs) yield good representations of complex real-world networks, by expressing edge probabilities as a function that depends on (heterogeneous) vertex weights and distances in some underlying geometric space that the vertices are distributed in. While most of the parameters of the model are understood well, it was unclear how the dimensionality of the ground space affects the structure of the graphs. In this paper, we complement existing research into the dimension of geometric random graph models and the ongoing study of determining the dimensionality of real-world networks, by studying how the structure of GIRGs changes as the number of dimensions increases. We prove that, in the limit, GIRGs approach non-geometric inhomogeneous random graphs and present insights on how quickly the decay of the geometry impacts important graph structures. In particular, we study the expected number of cliques of a given size as well as the clique number and characterize phase transitions at which their behavior changes fundamentally. Finally, our insights help in better understanding previous results about the impact of the dimensionality on geometric random graphs.
@inproceedings{friedrich2023cliques, abstract = {A recent trend in the context of graph theory is to bring theoretical analyses closer to empirical observations, by focusing the studies on random graph models that are used to represent practical instances. There, it was observed that geometric inhomogeneous random graphs (GIRGs) yield good representations of complex real-world networks, by expressing edge probabilities as a function that depends on (heterogeneous) vertex weights and distances in some underlying geometric space that the vertices are distributed in. While most of the parameters of the model are understood well, it was unclear how the dimensionality of the ground space affects the structure of the graphs. In this paper, we complement existing research into the dimension of geometric random graph models and the ongoing study of determining the dimensionality of real-world networks, by studying how the structure of GIRGs changes as the number of dimensions increases. We prove that, in the limit, GIRGs approach non-geometric inhomogeneous random graphs and present insights on how quickly the decay of the geometry impacts important graph structures. In particular, we study the expected number of cliques of a given size as well as the clique number and characterize phase transitions at which their behavior changes fundamentally. Finally, our insights help in better understanding previous results about the impact of the dimensionality on geometric random graphs.}, author = {Friedrich, Tobias and Göbel, Andreas and Katzmann, Maximilian and Schiller, Leon}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {sys:relevantfor:ae andreasgoebel icalp leonschiller maximiliankatzmann tobiasfriedrich year2023}, pages = {62:1–62:13}, title = {Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs}, year = 2023 }

Anand, Konrad; Göbel, Andreas; Pappik, Marcus; Perkins, Will Perfect Sampling for Hard Spheres from Strong Spatial MixingInternational Conference on Randomization and Computation (Random) 2023: 38:1–38:18
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We provide a perfect sampling algorithm for the hard-sphere model on subsets of ℝd with expected running time linear in the volume under the assumption of strong spatial mixing. A large number of perfect and approximate sampling algorithms have been devised to sample from the hard-sphere model, and our perfect sampling algorithm is efficient for a range of parameters for which only efficient approximate samplers were previously known and is faster than these known approximate approaches. Our methods also extend to the more general setting of Gibbs point processes interacting via finite-range, repulsive potentials.
@inproceedings{anand2023perfect, abstract = {We provide a perfect sampling algorithm for the hard-sphere model on subsets of ℝd with expected running time linear in the volume under the assumption of strong spatial mixing. A large number of perfect and approximate sampling algorithms have been devised to sample from the hard-sphere model, and our perfect sampling algorithm is efficient for a range of parameters for which only efficient approximate samplers were previously known and is faster than these known approximate approaches. Our methods also extend to the more general setting of Gibbs point processes interacting via finite-range, repulsive potentials.}, author = {Anand, Konrad and Göbel, Andreas and Pappik, Marcus and Perkins, Will}, booktitle = {International Conference on Randomization and Computation (Random)}, keywords = {sys:relevantfor:ae andreasgoebel marcuspappik random tobiasfriedrich year2023}, pages = {38:1–38:18}, title = {Perfect Sampling for Hard Spheres from Strong Spatial Mixing}, year = 2023 }

2022 [ nach oben ]

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 = {andreasgoebel cc gregorlagodzinski katrincasel philippfischbeck tobiasfriedrich year2022}, number = 2, pages = 11, title = {Zeros and approximations of Holant polynomials on the complex plane}, volume = 31, 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 = {andreasgoebel marcuspappik martinskrejca tobiasfriedrich year2022}, number = 3, pages = {2282-2322}, title = {A Spectral Independence View on Hard Spheres via Block Dynamics}, volume = 36, 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: 242–254
[ Abstract ] [ BibTeX ] [ DOI ] [ 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 = {andreasgoebel cocoon marcuspappik martinskrejca maximiliankatzmann tobiasfriedrich year2022}, pages = {242–254}, title = {Algorithms for hard-constraint point processes via discretization}, year = 2022 }

2021 [ nach oben ]

Göbel, Andreas; Lagodzinski, J. A. Gregor; Seidel, Karen Counting Homomorphisms to Trees Modulo a PrimeACM Transactions on Computation Theory 2021
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Many important graph theoretic notions can be encoded as counting graph homomorphism problems, such as partition functions in statistical physics, in particular independent sets and colourings. In this article we study the complexity of~\($\#_p\textsc{HomsTo}H$\), the problem of counting graph homomorphisms from an input graph to a graph \($H$\) modulo a prime number~\($p$\). Dyer and Greenhill proved a dichotomy stating that the tractability of non-modular counting graph homomorphisms depends on the structure of the target graph. Many intractable cases in non-modular counting become tractable in modular counting due to the common phenomenon of cancellation. In subsequent studies on counting modulo~\($2$\), however, the influence of the structure of~\($H$\) on the tractability was shown to persist, which yields similar dichotomies. Our main result states that for every tree~\($H$\) and every prime~\($p$\) the problem \($\#_p\textsc{HomsTo}H$\) is either polynomial time computable or \($\#_p\mathsf{P}$\)-complete. This relates to the conjecture of Faben and Jerrum stating that this dichotomy holds for every graph \($H$\) when counting modulo~2. In contrast to previous results on modular counting, the tractable cases of \($\#_p\textsc{HomsTo}H$\) are essentially the same for all values of the modulo when \($H$\) is a tree. To prove this result, we study the structural properties of a homomorphism. As an important interim result, our study yields a dichotomy for the problem of counting weighted independent sets in a bipartite graph modulo some prime~\($p$\). These results are the first suggesting that such dichotomies hold not only for the one-bit functions of the modulo~2 case but also for the modular counting functions of all primes~\($p$\).
@article{gobel2021counting, abstract = {Many important graph theoretic notions can be encoded as counting graph homomorphism problems, such as partition functions in statistical physics, in particular independent sets and colourings. In this article we study the complexity of&nbsp;$\#_p\textsc{HomsTo}H$, the problem of counting graph homomorphisms from an input graph to a graph $H$ modulo a prime number&nbsp;$p$. Dyer and Greenhill proved a dichotomy stating that the tractability of non-modular counting graph homomorphisms depends on the structure of the target graph. Many intractable cases in non-modular counting become tractable in modular counting due to the common phenomenon of cancellation. In subsequent studies on counting modulo&nbsp;$2$, however, the influence of the structure of&nbsp;$H$ on the tractability was shown to persist, which yields similar dichotomies. Our main result states that for every tree&nbsp;$H$ and every prime&nbsp;$p$ the problem $\#_p\textsc{HomsTo}H$ is either polynomial time computable or $\#_p\mathsf{P}$-complete. This relates to the conjecture of Faben and Jerrum stating that this dichotomy holds for every graph $H$ when counting modulo&nbsp;2. In contrast to previous results on modular counting, the tractable cases of $\#_p\textsc{HomsTo}H$ are essentially the same for all values of the modulo when $H$ is a tree. To prove this result, we study the structural properties of a homomorphism. As an important interim result, our study yields a dichotomy for the problem of counting weighted independent sets in a bipartite graph modulo some prime&nbsp;$p$. These results are the first suggesting that such dichotomies hold not only for the one-bit functions of the modulo&nbsp;2 case but also for the modular counting functions of all primes&nbsp;$p$.}, author = {Göbel, Andreas and Lagodzinski, J. A. Gregor and Seidel, Karen}, editor = {O'Donnell, Ryan}, journal = {ACM Transactions on Computation Theory}, keywords = {andreasgoebel gregorlagodzinski karenseidel toct year2021}, month = {sep}, number = 3, title = {Counting Homomorphisms to Trees Modulo a Prime}, volume = 13, year = 2021 }

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

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

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

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

2020 [ nach oben ]

Doskoč, Vanja; Friedrich, Tobias; Göbel, Andreas; Neumann, Aneta; Neumann, Frank; Quinzan, Francesco Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic SettingsEuropean Conference on Artificial Intelligence (ECAI) 2020: 435–442
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We study the problem of maximizing a non-monotone submodular function under multiple knapsack constraints. We propose a simple discrete greedy algorithm to approach this problem, and prove that it yields strong approximation guarantees for functions with bounded curvature. In contrast to other heuristics, this does not require problem relaxation to continuous domains and it maintains a constant-factor approximation guarantee in the problem size. In the case of a single knapsack, our analysis suggests that the standard greedy can be used in non-monotone settings. Additionally, we study this problem in a dynamic setting, in which knapsacks change during the optimization process. We modify our greedy algorithm to avoid a complete restart at each constraint update. This modification retains the approximation guarantees of the static case. We evaluate our results experimentally on a video summarization and sensor placement task. We show that our proposed algorithm competes with the state-of-the-art in static settings. Furthermore, we show that in dynamic settings with tight computational time budget, our modified greedy yields significant improvements over starting the greedy from scratch, in terms of the solution quality achieved.
@inproceedings{doskoc2020nonmonotone, abstract = {We study the problem of maximizing a non-monotone submodular function under multiple knapsack constraints. We propose a simple discrete greedy algorithm to approach this problem, and prove that it yields strong approximation guarantees for functions with bounded curvature. In contrast to other heuristics, this does not require problem relaxation to continuous domains and it maintains a constant-factor approximation guarantee in the problem size. In the case of a single knapsack, our analysis suggests that the standard greedy can be used in non-monotone settings. Additionally, we study this problem in a dynamic setting, in which knapsacks change during the optimization process. We modify our greedy algorithm to avoid a complete restart at each constraint update. This modification retains the approximation guarantees of the static case. We evaluate our results experimentally on a video summarization and sensor placement task. We show that our proposed algorithm competes with the state-of-the-art in static settings. Furthermore, we show that in dynamic settings with tight computational time budget, our modified greedy yields significant improvements over starting the greedy from scratch, in terms of the solution quality achieved.}, author = {Doskoč, Vanja and Friedrich, Tobias and Göbel, Andreas and Neumann, Aneta and Neumann, Frank and Quinzan, Francesco}, booktitle = {European Conference on Artificial Intelligence (ECAI)}, keywords = {andreasgoebel anetaneumann ecai francescoquinzan frankneumann tobiasfriedrich vanjadoskoc year2020}, pages = {435-442}, publisher = {{IOS} Press}, title = {Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings}, year = 2020 }

2019 [ nach oben ]

Friedrich, Tobias; Göbel, Andreas; Neumann, Frank; Quinzan, Francesco; Rothenberger, Ralf Greedy Maximization of Functions with Bounded Curvature Under Partition Matroid ConstraintsConference on Artificial Intelligence (AAAI) 2019: 2272–2279
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We investigate the performance of a deterministic GREEDY algorithm for the problem of maximizing functions under a partition matroid constraint. We consider non-monotone submodular functions and monotone subadditive functions. Even though constrained maximization problems of monotone submodular functions have been extensively studied, little is known about greedy maximization of non-monotone submodular functions or monotone subadditive functions. We give approximation guarantees for GREEDY on these problems, in terms of the curvature. We find that this simple heuristic yields a strong approximation guarantee on a broad class of functions. We discuss the applicability of our results to three real-world problems: Maximizing the determinant function of a positive semidefinite matrix, and related problems such as the maximum entropy sampling problem, the constrained maximum cut problem on directed graphs, and combinatorial auction games. We conclude that GREEDY is well-suited to approach these problems. Overall, we present evidence to support the idea that, when dealing with constrained maximization problems with bounded curvature, one needs not search for (approximate) monotonicity to get good approximate solutions.
@inproceedings{AAAI19a, abstract = {We investigate the performance of a deterministic GREEDY algorithm for the problem of maximizing functions under a partition matroid constraint. We consider non-monotone submodular functions and monotone subadditive functions. Even though constrained maximization problems of monotone submodular functions have been extensively studied, little is known about greedy maximization of non-monotone submodular functions or monotone subadditive functions. We give approximation guarantees for GREEDY on these problems, in terms of the curvature. We find that this simple heuristic yields a strong approximation guarantee on a broad class of functions. We discuss the applicability of our results to three real-world problems: Maximizing the determinant function of a positive semidefinite matrix, and related problems such as the maximum entropy sampling problem, the constrained maximum cut problem on directed graphs, and combinatorial auction games. We conclude that GREEDY is well-suited to approach these problems. Overall, we present evidence to support the idea that, when dealing with constrained maximization problems with bounded curvature, one needs not search for (approximate) monotonicity to get good approximate solutions.}, author = {Friedrich, Tobias and Göbel, Andreas and Neumann, Frank and Quinzan, Francesco and Rothenberger, Ralf}, booktitle = {Conference on Artificial Intelligence (AAAI)}, keywords = {aaai andreasgoebel francescoquinzan frankneumann ralfrothenberger tobiasfriedrich year2019}, pages = {2272-2279}, title = {Greedy Maximization of Functions with Bounded Curvature Under Partition Matroid Constraints}, year = 2019 }

2018 [ nach oben ]

Göbel, Andreas; Lagodzinski, J. A. Gregor; Seidel, Karen Counting Homomorphisms to Trees Modulo a PrimeMathematical Foundations of Computer Science (MFCS) 2018: 49:1–49:13
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Many important graph theoretic notions can be encoded as counting graph homomorphism problems, such as partition functions in statistical physics, in particular independent sets and colourings. In this article we study the complexity of~\($\#_p\textsc{HomsTo}H$\), the problem of counting graph homomorphisms from an input graph to a graph \($H$\) modulo a prime number~\($p$\). Dyer and Greenhill proved a dichotomy stating that the tractability of non-modular counting graph homomorphisms depends on the structure of the target graph. Many intractable cases in non-modular counting become tractable in modular counting due to the common phenomenon of cancellation. In subsequent studies on counting modulo~\($2$\), however, the influence of the structure of~\($H$\) on the tractability was shown to persist, which yields similar dichotomies. Our main result states that for every tree~\($H$\) and every prime~\($p$\) the problem \($\#_p\textsc{HomsTo}H$\) is either polynomial time computable or \($\#_p\mathsf{P}$\)-complete. This relates to the conjecture of Faben and Jerrum stating that this dichotomy holds for every graph \($H$\) when counting modulo~2. In contrast to previous results on modular counting, the tractable cases of \($\#_p\textsc{HomsTo}H$\) are essentially the same for all values of the modulo when \($H$\) is a tree. To prove this result, we study the structural properties of a homomorphism. As an important interim result, our study yields a dichotomy for the problem of counting weighted independent sets in a bipartite graph modulo some prime~\($p$\). These results are the first suggesting that such dichotomies hold not only for the one-bit functions of the modulo~2 case but also for the modular counting functions of all primes~\($p$\).
@inproceedings{gobel2018counting, abstract = {Many important graph theoretic notions can be encoded as counting graph homomorphism problems, such as partition functions in statistical physics, in particular independent sets and colourings. In this article we study the complexity of&nbsp;$\#_p\textsc{HomsTo}H$, the problem of counting graph homomorphisms from an input graph to a graph $H$ modulo a prime number&nbsp;$p$. Dyer and Greenhill proved a dichotomy stating that the tractability of non-modular counting graph homomorphisms depends on the structure of the target graph. Many intractable cases in non-modular counting become tractable in modular counting due to the common phenomenon of cancellation. In subsequent studies on counting modulo&nbsp;$2$, however, the influence of the structure of&nbsp;$H$ on the tractability was shown to persist, which yields similar dichotomies. Our main result states that for every tree&nbsp;$H$ and every prime&nbsp;$p$ the problem $\#_p\textsc{HomsTo}H$ is either polynomial time computable or $\#_p\mathsf{P}$-complete. This relates to the conjecture of Faben and Jerrum stating that this dichotomy holds for every graph $H$ when counting modulo&nbsp;2. In contrast to previous results on modular counting, the tractable cases of $\#_p\textsc{HomsTo}H$ are essentially the same for all values of the modulo when $H$ is a tree. To prove this result, we study the structural properties of a homomorphism. As an important interim result, our study yields a dichotomy for the problem of counting weighted independent sets in a bipartite graph modulo some prime&nbsp;$p$. These results are the first suggesting that such dichotomies hold not only for the one-bit functions of the modulo&nbsp;2 case but also for the modular counting functions of all primes&nbsp;$p$.}, author = {Göbel, Andreas and Lagodzinski, J. A. Gregor and Seidel, Karen}, booktitle = {Mathematical Foundations of Computer Science (MFCS)}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, keywords = {andreasgoebel gregorlagodzinski karenseidel mfcs year2018}, pages = {49:1-49:13}, publisher = {Leibniz International Proceedings in Informatics (LIPIcs)}, title = {Counting Homomorphisms to Trees Modulo a Prime}, volume = 117, year = 2018 }

Friedrich, Tobias; Göbel, Andreas; Quinzan, Francesco; Wagner, Markus Heavy-tailed Mutation Operators in Single-Objective Combinatorial OptimizationParallel Problem Solving From Nature (PPSN) 2018: 134–145
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
A core feature of evolutionary algorithms is their mutation operator. Recently, much attention has been devoted to the study of mutation operators with dynamic and non-uniform mutation rates. Following up on this line of work, we propose a new mutation operator and analyze its performance on the (1+1) Evolutionary Algorithm (EA). Our analyses show that this mutation operator competes with pre-existing ones, when used by the (1+1)EA on classes of problems for which results on the other mutation operators are available. We present a jump function for which the performance of the (1+1)EA using any static uniform mutation and any restart strategy can be worse than the performance of the (1+1)EA using our mutation operator with no restarts. We show that the (1+1)EA using our mutation operator finds a (1/3)-approximation ratio on any non-negative submodular function in polynomial time. This performance matches that of combinatorial local search algorithms specifically designed to solve this problem. Finally, we evaluate experimentally the performance of the (1+1)EA using our operator, on real-world graphs of different origins with up to \(\sim\)37,000 vertices and \(\sim\)1.6 million edges. In comparison with uniform mutation and a recently proposed dynamic scheme our operator comes out on top on these instances.
@inproceedings{friedrich2018heavytailed, abstract = {A core feature of evolutionary algorithms is their mutation operator. Recently, much attention has been devoted to the study of mutation operators with dynamic and non-uniform mutation rates. Following up on this line of work, we propose a new mutation operator and analyze its performance on the (1+1) Evolutionary Algorithm (EA). Our analyses show that this mutation operator competes with pre-existing ones, when used by the (1+1)EA on classes of problems for which results on the other mutation operators are available. We present a jump function for which the performance of the (1+1)EA using any static uniform mutation and any restart strategy can be worse than the performance of the (1+1)EA using our mutation operator with no restarts. We show that the (1+1)EA using our mutation operator finds a (1/3)-approximation ratio on any non-negative submodular function in polynomial time. This performance matches that of combinatorial local search algorithms specifically designed to solve this problem. Finally, we evaluate experimentally the performance of the (1+1)EA using our operator, on real-world graphs of different origins with up to \(\sim\)37\,000 vertices and \(\sim\)1.6 million edges. In comparison with uniform mutation and a recently proposed dynamic scheme our operator comes out on top on these instances.}, author = {Friedrich, Tobias and Göbel, Andreas and Quinzan, Francesco and Wagner, Markus}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, keywords = {andreasgoebel francescoquinzan markuswagner ppsn tobiasfriedrich year2018}, pages = {134-145}, title = {Heavy-tailed Mutation Operators in Single-Objective Combinatorial Optimization}, year = 2018 }

2017 [ nach oben ]

Bampas, Evangelos; Göbel, Andreas-Nikolas; Pagourtzis, Aris; Tentes, Aris On the connection between interval size functions and path countingComputational Complexity 2017: 421–467
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We investigate the complexity of hard (\#P-complete) counting problems that have easy decision version. By ‘easy decision,’ we mean that deciding whether the result of counting is nonzero is in P. This property is shared by several well-known problems, such as counting the number of perfect matchings in a given graph or counting the number of satisfying assignments of a given DNF formula. We focus on classes of such hard-to-count easy-to-decide problems which emerged through two seemingly disparate approaches: one taken by Hemaspaandra et al. (SIAM J Comput 36(5):1264–1300, 2007), who defined classes of functions that count the size of intervals of ordered strings, and one followed by Kiayias et al. (Lect Notes Comput Sci 2563:453–463, 2001), who defined the classTotP, consisting of functions that count the total number of paths of NP computations. We provide inclusion and separation relations between TotP and interval size counting classes, by means of new classes that we define in this work. Our results imply that many known #P-complete problems with easy decision are contained in the classes defined by Hemaspaandra et al., but are unlikely to be complete for these classes under reductions under which these classes are downward closed, e.g., parsimonious reductions. This, applied to the #MONSAT problem, partially answers an open question of Hemaspaandra et al. We also define a new class of interval size functions which strictly contains FP and is strictly contained in TotP under reasonable complexity-theoretic assumptions. We show that this new class contains hard counting problems.
@article{DBLP:journals/cc/BampasGPT17, abstract = {We investigate the complexity of hard (\#P-complete) counting problems that have easy decision version. By ‘easy decision,’ we mean that deciding whether the result of counting is nonzero is in P. This property is shared by several well-known problems, such as counting the number of perfect matchings in a given graph or counting the number of satisfying assignments of a given DNF formula. We focus on classes of such hard-to-count easy-to-decide problems which emerged through two seemingly disparate approaches: one taken by Hemaspaandra et al. (SIAM J Comput 36(5):1264–1300, 2007), who defined classes of functions that count the size of intervals of ordered strings, and one followed by Kiayias et al. (Lect Notes Comput Sci 2563:453–463, 2001), who defined the classTotP, consisting of functions that count the total number of paths of NP computations. We provide inclusion and separation relations between TotP and interval size counting classes, by means of new classes that we define in this work. Our results imply that many known \#P-complete problems with easy decision are contained in the classes defined by Hemaspaandra et al., but are unlikely to be complete for these classes under reductions under which these classes are downward closed, e.g., parsimonious reductions. This, applied to the \#MONSAT problem, partially answers an open question of Hemaspaandra et al. We also define a new class of interval size functions which strictly contains FP and is strictly contained in TotP under reasonable complexity-theoretic assumptions. We show that this new class contains hard counting problems.}, author = {Bampas, Evangelos and Göbel, Andreas-Nikolas and Pagourtzis, Aris and Tentes, Aris}, journal = {Computational Complexity}, keywords = {andreasgoebel cc year2017}, number = 2, pages = {421-467}, publisher = {Springer}, title = {On the connection between interval size functions and path counting}, volume = 26, year = 2017 }

Galanis, Andreas; Göbel, Andreas; Goldberg, Leslie Ann; Lapinskas, John; Richerby, David Amplifiers for the Moran ProcessJournal of the ACM 2017: 5:1–5:90
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The Moran process, as studied by Lieberman, Hauert, and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one vertex (chosen uniformly at random) possesses a mutation, with fitness \(r > 1\). All other individuals have fitness 1. During each step of the algorithm, an individual is chosen with probability proportional to its fitness, and its state (mutant or nonmutant) is passed on to an out-neighbour which is chosen uniformly at random. If the underlying graph is strongly connected, then the algorithm will eventually reach fixation, in which all individuals are mutants, or extinction, in which no individuals are mutants. An infinite family of directed graphs is said to be strongly amplifying if, for every \(r > 1\), the extinction probability tends to 0 as the number of vertices increases. A formal definition is provided in the article. Strong amplification is a rather surprising property-it means that in such graphs, the fixation probability of a uniformly placed initial mutant tends to 1 even though the initial mutant only has a fixed selective advantage of \(r > 1\) (independently of \(n\)). The name "strongly amplifying" comes from the fact that this selective advantage is "amplified." Strong amplifiers have received quite a bit of attention, and Lieberman et al. proposed two potentially strongly amplifying families-superstars and metafunnels. Heuristic arguments have been published, arguing that there are infinite families of superstars that are strongly amplifying. The same has been claimed for metafunnels. In this article, we give the first rigorous proof that there is an infinite family of directed graphs that is strongly amplifying. We call the graphs in the family "megastars." When the algorithm is run on an \(n\)-vertex graph in this family, starting with a uniformly chosen mutant, the extinction probability is roughly \(n - 1/2\) (up to logarithmic factors). We prove that all infinite families of superstars and metafunnels have larger extinction probabilities (as a function of \(n\)). Finally, we prove that our analysis of megastars is fairly tight - there is no infinite family of megastars such that the Moran algorithm gives a smaller extinction probability (up to logarithmic factors). Also, we provide a counterexample which clarifies the literature concerning the isothermal theorem of Lieberman et al.
@article{DBLP:journals/jacm/Galanis0GLR17, abstract = {The Moran process, as studied by Lieberman, Hauert, and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one vertex (chosen uniformly at random) possesses a mutation, with fitness \(r > 1\). All other individuals have fitness 1. During each step of the algorithm, an individual is chosen with probability proportional to its fitness, and its state (mutant or nonmutant) is passed on to an out-neighbour which is chosen uniformly at random. If the underlying graph is strongly connected, then the algorithm will eventually reach fixation, in which all individuals are mutants, or extinction, in which no individuals are mutants. An infinite family of directed graphs is said to be strongly amplifying if, for every \(r > 1\), the extinction probability tends to 0 as the number of vertices increases. A formal definition is provided in the article. Strong amplification is a rather surprising property-it means that in such graphs, the fixation probability of a uniformly placed initial mutant tends to 1 even though the initial mutant only has a fixed selective advantage of \(r > 1\) (independently of \(n\)). The name "strongly amplifying" comes from the fact that this selective advantage is "amplified." Strong amplifiers have received quite a bit of attention, and Lieberman et al. proposed two potentially strongly amplifying families-superstars and metafunnels. Heuristic arguments have been published, arguing that there are infinite families of superstars that are strongly amplifying. The same has been claimed for metafunnels. In this article, we give the first rigorous proof that there is an infinite family of directed graphs that is strongly amplifying. We call the graphs in the family "megastars." When the algorithm is run on an \(n\)-vertex graph in this family, starting with a uniformly chosen mutant, the extinction probability is roughly \(n - 1/2\) (up to logarithmic factors). We prove that all infinite families of superstars and metafunnels have larger extinction probabilities (as a function of \(n\)). Finally, we prove that our analysis of megastars is fairly tight - there is no infinite family of megastars such that the Moran algorithm gives a smaller extinction probability (up to logarithmic factors). Also, we provide a counterexample which clarifies the literature concerning the isothermal theorem of Lieberman et al.}, author = {Galanis, Andreas and Göbel, Andreas and Goldberg, Leslie Ann and Lapinskas, John and Richerby, David}, journal = {Journal of the ACM}, keywords = {andreasgoebel jacm year2017}, number = 1, pages = {5:1-5:90}, publisher = {ACM}, title = {Amplifiers for the Moran Process}, volume = 64, year = 2017 }

Göbel, Andreas Counting, Modular Counting and Graph HomomorphismsDoctoral Dissertation, University of Oxford 2017
[ BibTeX ] [ Download ]
 
@phdthesis{gobel2017counting, annote = {Doctoral Dissertation, University of Oxford}, author = {Göbel, Andreas}, keywords = {andreasgoebel theses year2017}, title = {Counting, Modular Counting and Graph Homomorphisms}, year = 2017 }

2016 [ nach oben ]

Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David Counting Homomorphisms to Square-Free Graphs, Modulo 2ACM Transactions on Computation Theory 2016: 12:1–12:29
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study the problem \( \oplus \)HomsToH of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph \(H\). A characteristic feature of modular counting is that cancellations make wider classes of instances tractable than is the case for exact (nonmodular) counting; thus, subtle dichotomy theorems can arise. We show the following dichotomy: for any \(H\) that contains no 4-cycles, \(\oplus\)HomsToH is either in polynomial time or is \(\oplus\)P-complete. This partially confirms a conjecture of Faben and Jerrum that was previously only known to hold for trees and for a restricted class of tree-width-2 graphs called cactus graphs. We confirm the conjecture for a rich class of graphs, including graphs of unbounded tree-width. In particular, we focus on square-free graphs, which are graphs without 4-cycles. These graphs arise frequently in combinatorics, for example, in connection with the strong perfect graph theorem and in certain graph algorithms. Previous dichotomy theorems required the graph to be tree-like so that tree-like decompositions could be exploited in the proof. We prove the conjecture for a much richer class of graphs by adopting a much more general approach.
@article{DBLP:journals/toct/0001GR16, abstract = {We study the problem \( \oplus \)HomsToH of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph \(H\). A characteristic feature of modular counting is that cancellations make wider classes of instances tractable than is the case for exact (nonmodular) counting; thus, subtle dichotomy theorems can arise. We show the following dichotomy: for any \(H\) that contains no 4-cycles, \(\oplus\)HomsToH is either in polynomial time or is \(\oplus\)P-complete. This partially confirms a conjecture of Faben and Jerrum that was previously only known to hold for trees and for a restricted class of tree-width-2 graphs called cactus graphs. We confirm the conjecture for a rich class of graphs, including graphs of unbounded tree-width. In particular, we focus on square-free graphs, which are graphs without 4-cycles. These graphs arise frequently in combinatorics, for example, in connection with the strong perfect graph theorem and in certain graph algorithms. Previous dichotomy theorems required the graph to be tree-like so that tree-like decompositions could be exploited in the proof. We prove the conjecture for a much richer class of graphs by adopting a much more general approach.}, author = {Göbel, Andreas and Goldberg, Leslie Ann and Richerby, David}, journal = {ACM Transactions on Computation Theory}, keywords = {andreasgoebel toct year2016}, number = 3, pages = {12:1-12:29}, title = {Counting Homomorphisms to Square-Free Graphs, Modulo 2}, volume = 8, year = 2016 }

Galanis, Andreas; Göbel, Andreas; Goldberg, Leslie-Ann; Lapinskas, John; Richerby, David Amplifiers for the Moran ProcessInternational Colloquium on Automata, Languages and Programming (ICALP) 2016: 62:1–62:13
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The Moran process, as studied by Lieberman, Hauert and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one vertex (chosen uniformly at random) possesses a mutation, with fitness \(r > 1\). All other individuals have fitness 1. During each step of the algorithm, an individual is chosen with probability proportional to its fitness, and its state (mutant or non-mutant) is passed on to an out-neighbour which is chosen uniformly at random. If the underlying graph is strongly connected then the algorithm will eventually reach fixation, in which all individuals are mutants, or extinction, in which no individuals are mutants. An infinite family of directed graphs is said to be strongly amplifying if, for every \(r > 1\), the extinction probability tends to 0 as the number of vertices increases. Strong amplification is a rather surprising property - it means that in such graphs, the fixation probability of a uniformly-placed initial mutant tends to 1 even though the initial mutant only has a fixed selective advantage of \(r > 1\) (independently of \(n\)). The name "strongly amplifying" comes from the fact that this selective advantage is "amplified". Strong amplifiers have received quite a bit of attention, and Lieberman et al. proposed two potentially strongly-amplifying families - superstars and metafunnels. Heuristic arguments have been published, arguing that there are infinite families of superstars that are strongly amplifying. The same has been claimed for metafunnels. We give the first rigorous proof that there is an infinite family of directed graphs that is strongly amplifying. We call the graphs in the family "megastars". When the algorithm is run on an n-vertex graph in this family, starting with a uniformly-chosen mutant, the extinction probability is roughly \(n^{-1/2}\) (up to logarithmic factors). We prove that all infinite families of superstars and metafunnels have larger extinction probabilities (as a function of \(n\)). Finally, we prove that our analysis of megastars is fairly tight - there is no infinite family of megastars such that the Moran algorithm gives a smaller extinction probability (up to logarithmic factors). Also, we provide a counterexample which clarifies the literature concerning the isothermal theorem of Lieberman et al. A full version [Galanis/Göbel/Goldberg/Lapinskas/Richerby, Preprint] containing detailed proofs is available at http://arxiv.org/abs/1512.05632. Theorem-numbering here matches the full version.
@inproceedings{DBLP:conf/icalp/Galanis0GLR16, abstract = {The Moran process, as studied by Lieberman, Hauert and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one vertex (chosen uniformly at random) possesses a mutation, with fitness \(r > 1\). All other individuals have fitness 1. During each step of the algorithm, an individual is chosen with probability proportional to its fitness, and its state (mutant or non-mutant) is passed on to an out-neighbour which is chosen uniformly at random. If the underlying graph is strongly connected then the algorithm will eventually reach fixation, in which all individuals are mutants, or extinction, in which no individuals are mutants. An infinite family of directed graphs is said to be strongly amplifying if, for every \(r > 1\), the extinction probability tends to 0 as the number of vertices increases. Strong amplification is a rather surprising property - it means that in such graphs, the fixation probability of a uniformly-placed initial mutant tends to 1 even though the initial mutant only has a fixed selective advantage of \(r > 1\) (independently of \(n\)). The name "strongly amplifying" comes from the fact that this selective advantage is "amplified". Strong amplifiers have received quite a bit of attention, and Lieberman et al. proposed two potentially strongly-amplifying families - superstars and metafunnels. Heuristic arguments have been published, arguing that there are infinite families of superstars that are strongly amplifying. The same has been claimed for metafunnels. We give the first rigorous proof that there is an infinite family of directed graphs that is strongly amplifying. We call the graphs in the family "megastars". When the algorithm is run on an n-vertex graph in this family, starting with a uniformly-chosen mutant, the extinction probability is roughly \(n^{-1/2}\) (up to logarithmic factors). We prove that all infinite families of superstars and metafunnels have larger extinction probabilities (as a function of \(n\)). Finally, we prove that our analysis of megastars is fairly tight - there is no infinite family of megastars such that the Moran algorithm gives a smaller extinction probability (up to logarithmic factors). Also, we provide a counterexample which clarifies the literature concerning the isothermal theorem of Lieberman et al. A full version [Galanis/Göbel/Goldberg/Lapinskas/Richerby, Preprint] containing detailed proofs is available at http://arxiv.org/abs/1512.05632. Theorem-numbering here matches the full version.}, author = {Galanis, Andreas and Göbel, Andreas and Goldberg, Leslie-Ann and Lapinskas, John and Richerby, David}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {andreasgoebel icalp year2016}, pages = {62:1-62:13}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {LIPIcs}, title = {Amplifiers for the Moran Process}, volume = 55, year = 2016 }

2015 [ nach oben ]

Göbel, Andreas; Goldberg, Leslie Ann; McQuillan, Colin; Richerby, David; Yamakami, Tomoyuki Counting List Matrix Partitions of GraphsSIAM Journal on Computing 2015: 1089–1118
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Given a symmetric \(D\times D\) matrix \(M\) over \(0,1,*\), a list \(M\)-partition of a graph \(G\) is a partition of the vertices of \(G\) into \(D\) parts which are associated with the rows of \(M\). The part of each vertex is chosen from a given list in such a way that no edge of \(G\) is mapped to a 0 in \(M\) and no nonedge of \(G\) is mapped to a 1 in \(M\). Many important graph-theoretic structures can be represented as list \(M\)-partitions including graph colorings, split graphs, and homogeneous sets and pairs, which arise in the proofs of the weak and strong perfect graph conjectures. Thus, there has been quite a bit of work on determining for which matrices \(M\) computations involving list \(M\)-partitions are tractable. This paper focuses on the problem of counting list \(M\)-partitions, given a graph \(G\) and given a list for each vertex of \(G\). We identify a certain set of "tractable" matrices \(M\). We give an algorithm that counts list \(M\)-partitions in polynomial time for every (fixed) matrix \(M\) in this set. The algorithm relies on data structures such as sparse-dense partitions and subcube decompositions to reduce each problem instance to a sequence of problem instances in which the lists have a certain useful structure that restricts access to portions of \(M\) in which the interactions of 0s and 1s are controlled. We show how to solve the resulting restricted instances by converting them into particular counting constraint satisfaction problems (\({\#CSP}\)s), which we show how to solve using a constraint satisfaction technique known as arc-consistency. For every matrix \(M\) for which our algorithm fails, we show that the problem of counting list \(M\)-partitions is \({\#P}\)-complete. Furthermore, we give an explicit characterization of the dichotomy theorem: counting list \(M\)-partitions is tractable (in \({FP}\)) if the matrix \(M\) has a structure called a derectangularizing sequence. If \(M\) has no derectangularizing sequence, we show that counting list \(M\)-partitions is \({\#P}\)-hard. We show that the metaproblem of determining whether a given matrix has a derectangularizing sequence is \({NP}\)-complete. Finally, we show that list \(M\)-partitions can be used to encode cardinality restrictions in \(M\)-partitions problems, and we use this to give a polynomial-time algorithm for counting homogeneous pairs in graphs.
@article{DBLP:journals/siamcomp/0001GMRY15, abstract = {Given a symmetric \(D\times D\) matrix \(M\) over \(0,1,*\), a list \(M\)-partition of a graph \(G\) is a partition of the vertices of \(G\) into \(D\) parts which are associated with the rows of \(M\). The part of each vertex is chosen from a given list in such a way that no edge of \(G\) is mapped to a 0 in \(M\) and no nonedge of \(G\) is mapped to a 1 in \(M\). Many important graph-theoretic structures can be represented as list \(M\)-partitions including graph colorings, split graphs, and homogeneous sets and pairs, which arise in the proofs of the weak and strong perfect graph conjectures. Thus, there has been quite a bit of work on determining for which matrices \(M\) computations involving list \(M\)-partitions are tractable. This paper focuses on the problem of counting list \(M\)-partitions, given a graph \(G\) and given a list for each vertex of \(G\). We identify a certain set of "tractable" matrices \(M\). We give an algorithm that counts list \(M\)-partitions in polynomial time for every (fixed) matrix \(M\) in this set. The algorithm relies on data structures such as sparse-dense partitions and subcube decompositions to reduce each problem instance to a sequence of problem instances in which the lists have a certain useful structure that restricts access to portions of \(M\) in which the interactions of 0s and 1s are controlled. We show how to solve the resulting restricted instances by converting them into particular counting constraint satisfaction problems (\({\#CSP}\)s), which we show how to solve using a constraint satisfaction technique known as arc-consistency. For every matrix \(M\) for which our algorithm fails, we show that the problem of counting list \(M\)-partitions is \({\#P}\)-complete. Furthermore, we give an explicit characterization of the dichotomy theorem: counting list \(M\)-partitions is tractable (in \({FP}\)) if the matrix \(M\) has a structure called a derectangularizing sequence. If \(M\) has no derectangularizing sequence, we show that counting list \(M\)-partitions is \({\#P}\)-hard. We show that the metaproblem of determining whether a given matrix has a derectangularizing sequence is \({NP}\)-complete. Finally, we show that list \(M\)-partitions can be used to encode cardinality restrictions in \(M\)-partitions problems, and we use this to give a polynomial-time algorithm for counting homogeneous pairs in graphs.}, author = {Göbel, Andreas and Goldberg, Leslie Ann and McQuillan, Colin and Richerby, David and Yamakami, Tomoyuki}, journal = {SIAM Journal on Computing}, keywords = {andreasgoebel siamcomp year2015}, number = 4, pages = {1089-1118}, title = {Counting List Matrix Partitions of Graphs}, volume = 44, year = 2015 }

Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David Counting Homomorphisms to Square-Free Graphs, Modulo 2International Colloquium on Automata, Languages, and Programming (ICALP) 2015: 642–653
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study the problem \( \oplus \)HomsToH of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph \(H\). A characteristic feature of modular counting is that cancellations make wider classes of instances tractable than is the case for exact (nonmodular) counting; thus, subtle dichotomy theorems can arise. We show the following dichotomy: for any \(H\) that contains no 4-cycles, \(\oplus\)HomsToH is either in polynomial time or is \(\oplus\)P-complete. This partially confirms a conjecture of Faben and Jerrum that was previously only known to hold for trees and for a restricted class of tree-width-2 graphs called cactus graphs. We confirm the conjecture for a rich class of graphs, including graphs of unbounded tree-width. In particular, we focus on square-free graphs, which are graphs without 4-cycles. These graphs arise frequently in combinatorics, for example, in connection with the strong perfect graph theorem and in certain graph algorithms. Previous dichotomy theorems required the graph to be tree-like so that tree-like decompositions could be exploited in the proof. We prove the conjecture for a much richer class of graphs by adopting a much more general approach.
@inproceedings{DBLP:conf/icalp/0001GR15, abstract = {We study the problem \( \oplus \)HomsToH of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph \(H\). A characteristic feature of modular counting is that cancellations make wider classes of instances tractable than is the case for exact (nonmodular) counting; thus, subtle dichotomy theorems can arise. We show the following dichotomy: for any \(H\) that contains no 4-cycles, \(\oplus\)HomsToH is either in polynomial time or is \(\oplus\)P-complete. This partially confirms a conjecture of Faben and Jerrum that was previously only known to hold for trees and for a restricted class of tree-width-2 graphs called cactus graphs. We confirm the conjecture for a rich class of graphs, including graphs of unbounded tree-width. In particular, we focus on square-free graphs, which are graphs without 4-cycles. These graphs arise frequently in combinatorics, for example, in connection with the strong perfect graph theorem and in certain graph algorithms. Previous dichotomy theorems required the graph to be tree-like so that tree-like decompositions could be exploited in the proof. We prove the conjecture for a much richer class of graphs by adopting a much more general approach.}, author = {Göbel, Andreas and Goldberg, Leslie Ann and Richerby, David}, booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)}, keywords = {andreasgoebel icalp notaccepted year2015}, pages = {642-653}, title = {Counting Homomorphisms to Square-Free Graphs, Modulo 2}, year = 2015 }

2014 [ nach oben ]

Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David The complexity of counting homomorphisms to cactus graphs modulo 2ACM Transactions on Computation Theory 2014: 17:1–17:29
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
A homomorphism from a graph \(G\) to a graph \(H\) is a function from \(V(G)\) to \(V(H)\) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this article, we study the complexity of counting homomorphisms modulo 2. The complexity of modular counting was introduced by Papadimitriou and Zachos and it has been pioneered by Valiant who famously introduced a problem for which counting modulo 7 is easy but counting modulo 2 is intractable. Modular counting provides a rich setting in which to study the structure of homomorphism problems. In this case, the structure of the graph \(H\) has a big influence on the complexity of the problem. Thus, our approach is graph-theoretic. We give a complete solution for the class of cactus graphs, which are connected graphs in which every edge belongs to at most one cycle. Cactus graphs arise in many applications such as the modelling of wireless sensor networks and the comparison of genomes. We show that, for some cactus graphs \(H\), counting homomorphisms to \(H\) modulo 2 can be done in polynomial time. For every other fixed cactus graph \(H\), the problem is complete in the complexity class \(\oplus P\), which is a wide complexity class to which every problem in the polynomial hierarchy can be reduced (using randomised reductions). Determining which \(H\) lead to tractable problems can be done in polynomial time. Our result builds upon the work of Faben and Jerrum, who gave a dichotomy for the case in which \(H\) is a tree.
@article{DBLP:journals/toct/0001GR14, abstract = {A homomorphism from a graph \(G\) to a graph \(H\) is a function from \(V(G)\) to \(V(H)\) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this article, we study the complexity of counting homomorphisms modulo 2. The complexity of modular counting was introduced by Papadimitriou and Zachos and it has been pioneered by Valiant who famously introduced a problem for which counting modulo 7 is easy but counting modulo 2 is intractable. Modular counting provides a rich setting in which to study the structure of homomorphism problems. In this case, the structure of the graph \(H\) has a big influence on the complexity of the problem. Thus, our approach is graph-theoretic. We give a complete solution for the class of cactus graphs, which are connected graphs in which every edge belongs to at most one cycle. Cactus graphs arise in many applications such as the modelling of wireless sensor networks and the comparison of genomes. We show that, for some cactus graphs \(H\), counting homomorphisms to \(H\) modulo 2 can be done in polynomial time. For every other fixed cactus graph \(H\), the problem is complete in the complexity class \(\oplus P\), which is a wide complexity class to which every problem in the polynomial hierarchy can be reduced (using randomised reductions). Determining which \(H\) lead to tractable problems can be done in polynomial time. Our result builds upon the work of Faben and Jerrum, who gave a dichotomy for the case in which \(H\) is a tree.}, author = {Göbel, Andreas and Goldberg, Leslie Ann and Richerby, David}, journal = {ACM Transactions on Computation Theory}, keywords = {TOCT andreasgoebel year2014}, number = 4, pages = {17:1-17:29}, title = {The complexity of counting homomorphisms to cactus graphs modulo 2}, volume = 6, year = 2014 }

Göbel, Andreas; Goldberg, Leslie Ann; McQuillan, Colin; Richerby, David; Yamakami, Tomoyuki Counting List Matrix Partitions of GraphsConference on Computational Complexity (CCC) 2014: 56–65
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Given a symmetric \(D \times D\) matrix \(M\) over \(0, 1, *}\), a list \(M\)-partition of a graph \(G\) is a partition of the vertices of \(G\) into \(D\) parts which are associated with the rows of \(M\). The part of each vertex is chosen from a given list in such a way that no edge of \(G\) is mapped to a 0 in \(M\) and no non-edge of \(G\) is mapped to a 1 in \(M\). Many important graph-theoretic structures can be represented as list \(M\)-partitions including graph colourings, split graphs and homogeneous sets, which arise in the proofs of the weak and strong perfect graph conjectures. Thus, there has been quite a bit of work on determining for which matrices \(M\) computations involving list \(M\)-partitions are tractable. This paper focuses on the problem of counting list \(M\)-partitions, given a graph \(G\) and given lists for each vertex of \(G\). We give an algorithm that solves this problem in polynomial time for every (fixed) matrix \(M\) for which the problem is tractable. The algorithm relies on data structures such as sparse-dense partitions and sub cube decompositions to reduce each problem instance to a sequence of problem instances in which the lists have a certain useful structure that restricts access to portions of \(M\) in which the interactions of 0s and 1s is controlled. We show how to solve the resulting restricted instances by converting them into particular counting constraint satisfaction problems (\#CSPs) which we show how to solve using a constraint satisfaction technique known as "arc-consistency". For every matrix \(M\) for which our algorithm fails, we show that the problem of counting list \(M\)-partitions is #P-complete. Furthermore, we give an explicit characterisation of the dichotomy theorem - counting list \(M\)-partitions is tractable (in FP) if and only if the matrix \(M\) has a structure called a derectangularising sequence. Finally, we show that the meta-problem of determining whether a given matrix has a derectangularising sequence is NP-complete.
@inproceedings{DBLP:conf/coco/0001GMRY14, abstract = {Given a symmetric \(D \times D\) matrix \(M\) over \({0, 1, *}\), a list \(M\)-partition of a graph \(G\) is a partition of the vertices of \(G\) into \(D\) parts which are associated with the rows of \(M\). The part of each vertex is chosen from a given list in such a way that no edge of \(G\) is mapped to a 0 in \(M\) and no non-edge of \(G\) is mapped to a 1 in \(M\). Many important graph-theoretic structures can be represented as list \(M\)-partitions including graph colourings, split graphs and homogeneous sets, which arise in the proofs of the weak and strong perfect graph conjectures. Thus, there has been quite a bit of work on determining for which matrices \(M\) computations involving list \(M\)-partitions are tractable. This paper focuses on the problem of counting list \(M\)-partitions, given a graph \(G\) and given lists for each vertex of \(G\). We give an algorithm that solves this problem in polynomial time for every (fixed) matrix \(M\) for which the problem is tractable. The algorithm relies on data structures such as sparse-dense partitions and sub cube decompositions to reduce each problem instance to a sequence of problem instances in which the lists have a certain useful structure that restricts access to portions of \(M\) in which the interactions of 0s and 1s is controlled. We show how to solve the resulting restricted instances by converting them into particular counting constraint satisfaction problems (\#CSPs) which we show how to solve using a constraint satisfaction technique known as "arc-consistency". For every matrix \(M\) for which our algorithm fails, we show that the problem of counting list \(M\)-partitions is \#P-complete. Furthermore, we give an explicit characterisation of the dichotomy theorem - counting list \(M\)-partitions is tractable (in FP) if and only if the matrix \(M\) has a structure called a derectangularising sequence. Finally, we show that the meta-problem of determining whether a given matrix has a derectangularising sequence is NP-complete.}, author = {Göbel, Andreas and Goldberg, Leslie Ann and McQuillan, Colin and Richerby, David and Yamakami, Tomoyuki}, booktitle = {Conference on Computational Complexity (CCC)}, keywords = {andreasgoebel ccc year2014}, pages = {56-65}, title = {Counting List Matrix Partitions of Graphs}, year = 2014 }

Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David Counting Homomorphisms to Cactus Graphs Modulo 2Symposium on Theoretical Aspects of Computer Science (STACS) 2014: 350–361
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
A homomorphism from a graph \(G\) to a graph \(H\) is a function from \(V(G)\) to \(V(H)\) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this article, we study the complexity of counting homomorphisms modulo 2. The complexity of modular counting was introduced by Papadimitriou and Zachos and it has been pioneered by Valiant who famously introduced a problem for which counting modulo 7 is easy but counting modulo 2 is intractable. Modular counting provides a rich setting in which to study the structure of homomorphism problems. In this case, the structure of the graph \(H\) has a big influence on the complexity of the problem. Thus, our approach is graph-theoretic. We give a complete solution for the class of cactus graphs, which are connected graphs in which every edge belongs to at most one cycle. Cactus graphs arise in many applications such as the modelling of wireless sensor networks and the comparison of genomes. We show that, for some cactus graphs \(H\), counting homomorphisms to \(H\) modulo 2 can be done in polynomial time. For every other fixed cactus graph \(H\), the problem is complete in the complexity class \(\oplus P\), which is a wide complexity class to which every problem in the polynomial hierarchy can be reduced (using randomised reductions). Determining which \(H\) lead to tractable problems can be done in polynomial time. Our result builds upon the work of Faben and Jerrum, who gave a dichotomy for the case in which \(H\) is a tree.
@inproceedings{DBLP:conf/stacs/0001GR14, abstract = {A homomorphism from a graph \(G\) to a graph \(H\) is a function from \(V(G)\) to \(V(H)\) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this article, we study the complexity of counting homomorphisms modulo 2. The complexity of modular counting was introduced by Papadimitriou and Zachos and it has been pioneered by Valiant who famously introduced a problem for which counting modulo 7 is easy but counting modulo 2 is intractable. Modular counting provides a rich setting in which to study the structure of homomorphism problems. In this case, the structure of the graph \(H\) has a big influence on the complexity of the problem. Thus, our approach is graph-theoretic. We give a complete solution for the class of cactus graphs, which are connected graphs in which every edge belongs to at most one cycle. Cactus graphs arise in many applications such as the modelling of wireless sensor networks and the comparison of genomes. We show that, for some cactus graphs \(H\), counting homomorphisms to \(H\) modulo 2 can be done in polynomial time. For every other fixed cactus graph \(H\), the problem is complete in the complexity class \(\oplus P\), which is a wide complexity class to which every problem in the polynomial hierarchy can be reduced (using randomised reductions). Determining which \(H\) lead to tractable problems can be done in polynomial time. Our result builds upon the work of Faben and Jerrum, who gave a dichotomy for the case in which \(H\) is a tree.}, author = {Göbel, Andreas and Goldberg, Leslie Ann and Richerby, David}, booktitle = {Symposium on Theoretical Aspects of Computer Science (STACS)}, keywords = {andreasgoebel stacs year2014}, pages = {350-361}, title = {Counting Homomorphisms to Cactus Graphs Modulo 2}, year = 2014 }

2009 [ nach oben ]

Bampas, Evangelos; Göbel, Andreas-Nikolas; Pagourtzis, Aris; Tentes, Aris On the Connection between Interval Size Functions and Path CountingTheory and Applications of Models of Computation (TAMC) 2009: 108–117
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We investigate the complexity of hard counting problems that belong to the class #P but have easy decision version; several well-known problems such as #Perfect Matchings, #DNFSat share this property. We focus on classes of such problems which emerged through two disparate approaches: one taken by Hemaspaandra et al. [1] who defined classes of functions that count the size of intervals of ordered strings, and one followed by Kiayias et al. [2] who defined the class TotP, consisting of functions that count the total number of paths of NP computations. We provide inclusion and separation relations between TotP and interval size counting classes, by means of new classes that we define in this work. Our results imply that many known #P-complete problems with easy decision are contained in the classes defined in [1]-but are unlikely to be complete for these classes under certain types of reductions. We also define a new class of interval size functions which strictly contains FP and is strictly contained in TotP under reasonable complexity-theoretic assumptions. We show that this new class contains some hard counting problems.
@inproceedings{DBLP:conf/tamc/BampasGPT09, abstract = {We investigate the complexity of hard counting problems that belong to the class \#P but have easy decision version; several well-known problems such as \#Perfect Matchings, \#DNFSat share this property. We focus on classes of such problems which emerged through two disparate approaches: one taken by Hemaspaandra et al. [1] who defined classes of functions that count the size of intervals of ordered strings, and one followed by Kiayias et al. [2] who defined the class TotP, consisting of functions that count the total number of paths of NP computations. We provide inclusion and separation relations between TotP and interval size counting classes, by means of new classes that we define in this work. Our results imply that many known \#P-complete problems with easy decision are contained in the classes defined in [1]-but are unlikely to be complete for these classes under certain types of reductions. We also define a new class of interval size functions which strictly contains FP and is strictly contained in TotP under reasonable complexity-theoretic assumptions. We show that this new class contains some hard counting problems.}, author = {Bampas, Evangelos and Göbel, Andreas-Nikolas and Pagourtzis, Aris and Tentes, Aris}, booktitle = {Theory and Applications of Models of Computation (TAMC)}, keywords = {andreasgoebel tamc year2009}, pages = {108-117}, title = {On the Connection between Interval Size Functions and Path Counting}, year = 2009 }