TY - JOUR A1 - Casel, Katrin A1 - Fischbeck, Philipp A1 - Friedrich, Tobias A1 - Göbel, Andreas A1 - Lagodzinski, J. A. Gregor T1 - Zeros and approximations of Holant polynomials on the complex plane JF - Computational complexity : CC N2 - We present fully polynomial time approximation schemes for 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 most significant 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. KW - Holant problems KW - approximate counting KW - partition functions KW - graph KW - polynomials Y1 - 2022 U6 - https://doi.org/10.1007/s00037-022-00226-5 SN - 1016-3328 SN - 1420-8954 VL - 31 IS - 2 PB - Springer CY - Basel ER - TY - JOUR A1 - Göbel, Andreas A1 - Lagodzinski, Gregor J. A. A1 - Seidel, Karen T1 - Counting homomorphisms to trees modulo a prime JF - ACM transactions on computation theory : TOCT / Association for Computing Machinery N2 - 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) HOMSTOH, 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 #pHOMSTOH is either polynomial time computable or #P-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 #pHOMSTOH 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 modulo 2 case but also for the modular counting functions of all primes p. KW - Graph homomorphisms KW - modular counting KW - complexity dichotomy Y1 - 2021 U6 - https://doi.org/10.1145/3460958 SN - 1942-3454 SN - 1942-3462 VL - 13 IS - 3 SP - 1 EP - 33 PB - Association for Computing Machinery CY - New York ER - TY - JOUR A1 - Quinzan, Francesco A1 - Göbel, Andreas A1 - Wagner, Markus A1 - Friedrich, Tobias T1 - Evolutionary algorithms and submodular functions BT - benefits of heavy-tailed mutations JF - Natural computing : an innovative journal bridging biosciences and computer sciences ; an international journal N2 - A core operator of evolutionary algorithms (EAs) is the mutation. Recently, much attention has been devoted to the study of mutation operators with dynamic and non-uniform mutation rates. Following up on this area 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 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. We also consider the problem of maximizing a symmetric submodular function under a single matroid constraint and show that the (1 + 1) EA using our operator finds a (1/3)-approximation within polynomial time. This performance matches that of combinatorial local search algorithms specifically designed to solve these problems and outperforms them with constant probability. Finally, we evaluate the performance of the (1 + 1) EA using our operator experimentally by considering two applications: (a) the maximum directed cut problem on real-world graphs of different origins, with up to 6.6 million vertices and 56 million edges and (b) the symmetric mutual information problem using a four month period air pollution data set. In comparison with uniform mutation and a recently proposed dynamic scheme, our operator comes out on top on these instances. KW - Evolutionary algorithms KW - Mutation operators KW - Submodular functions KW - Matroids Y1 - 2021 U6 - https://doi.org/10.1007/s11047-021-09841-7 SN - 1572-9796 VL - 20 IS - 3 SP - 561 EP - 575 PB - Springer Science + Business Media B.V. CY - Dordrecht ER -