2020 [ nach oben ]

• 
  Doskoč, Vanja; Friedrich, Tobias; Göbel, Andreas; Neumann, Aneta; Neumann, Frank; Quinzan, FrancescoNon-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings. European Conference on Artificial Intelligence (ECAI) 2020
  [ Abstract ] [ BibTeX ] [ 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}, 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, RalfGreedy Maximization of Functions with Bounded Curvature Under Partition Matroid Constraints. Conference 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, KarenCounting Homomorphisms to Trees Modulo a Prime. Mathematical 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~$\#_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$.}, 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, MarkusHeavy-tailed Mutation Operators in Single-Objective Combinatorial Optimization. Parallel 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, ArisOn the connection between interval size functions and path counting. Computational 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, DavidAmplifiers for the Moran Process. Journal 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, AndreasCounting, Modular Counting and Graph Homomorphisms. Doctoral 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, DavidCounting Homomorphisms to Square-Free Graphs, Modulo 2. 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 = {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, DavidAmplifiers for the Moran Process. International 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, TomoyukiCounting List Matrix Partitions of Graphs. SIAM 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, DavidCounting Homomorphisms to Square-Free Graphs, Modulo 2. International 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, DavidThe complexity of counting homomorphisms to cactus graphs modulo 2. 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 = {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, TomoyukiCounting List Matrix Partitions of Graphs. Conference 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, DavidCounting Homomorphisms to Cactus Graphs Modulo 2. Symposium 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, ArisOn the Connection between Interval Size Functions and Path Counting. Theory 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 }