2017 [ to top ]

• 
  Galanis, Andreas; Göbel, Andreas; Goldberg, Leslie Ann; Lapinskas, John; Richerby, David Amplifiers for the Moran Process. Journal of the ACM 2017: 5:1-5:90
  [ Abstract ] [ BibTeX ] [ URL ] [DOI]
   
  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}, number = 1, pages = {5:1-5:90}, title = {Amplifiers for the Moran Process}, volume = 64, year = 2017 }
• 
  Göbel, Andreas Counting, Modular Counting and Graph Homomorphisms. 2017
  [ BibTeX ] [ Download ]
   
  @phdthesis{gobel2017counting, author = {Göbel, Andreas}, title = {Counting, Modular Counting and Graph Homomorphisms}, year = 2017 }
• 
  Bampas, Evangelos; Göbel, Andreas-Nikolas; Pagourtzis, Aris; Tentes, Aris On the connection between interval size functions and path counting. Computational Complexity 2017: 421-467
  [ BibTeX ] [ URL ] [DOI]
   
  @article{DBLP:journals/cc/BampasGPT17, author = {Bampas, Evangelos and Göbel, Andreas-Nikolas and Pagourtzis, Aris and Tentes, Aris}, journal = {Computational Complexity}, number = 2, pages = {421-467}, title = {On the connection between interval size functions and path counting}, volume = 26, year = 2017 }

2016 [ to top ]

• 
  Galanis, Andreas; Göbel, Andreas; Goldberg, Leslie-Ann; Lapinskas, John; Richerby, David Amplifiers 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)}, pages = {62:1-62:13}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {LIPIcs}, title = {Amplifiers for the Moran Process}, volume = 55, year = 2016 }
• 
  Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David Counting Homomorphisms to Square-Free Graphs, Modulo 2. Transactions on Computation Theory 2016: 12:1-12:29
  [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  @article{DBLP:journals/toct/0001GR16, author = {Göbel, Andreas and Goldberg, Leslie Ann and Richerby, David}, journal = {Transactions on Computation Theory}, number = 3, pages = {12:1-12:29}, title = {Counting Homomorphisms to Square-Free Graphs, Modulo 2}, volume = 8, year = 2016 }

2015 [ to top ]

• 
  Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David Counting 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)}, crossref = {DBLP:conf/icalp/2015-1}, pages = {642-653}, title = {Counting Homomorphisms to Square-Free Graphs, Modulo 2}, year = 2015 }
• 
  Göbel, Andreas; Goldberg, Leslie Ann; McQuillan, Colin; Richerby, David; Yamakami, Tomoyuki Counting List Matrix Partitions of Graphs. SIAM Journal on Computing 2015: 1089-1118
  [ Abstract ] [ BibTeX ] [ URL ] [DOI] [ Download ]
   
  Given a symmetric \(Dtimes 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 \(Dtimes 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}, number = 4, pages = {1089-1118}, title = {Counting List Matrix Partitions of Graphs}, volume = 44, year = 2015 }

2014 [ to top ]

• 
  Göbel, Andreas; Goldberg, Leslie Ann; McQuillan, Colin; Richerby, David; Yamakami, Tomoyuki Counting 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)}, crossref = {DBLP:conf/coco/2014}, 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 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)}, crossref = {DBLP:conf/stacs/2014}, pages = {350-361}, title = {Counting Homomorphisms to Cactus Graphs Modulo 2}, year = 2014 }
• 
  Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David The 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}, number = 4, pages = {17:1-17:29}, title = {The complexity of counting homomorphisms to cactus graphs modulo 2}, volume = 6, year = 2014 }

2009 [ to top ]

• 
  Bampas, Evangelos; Göbel, Andreas-Nikolas; Pagourtzis, Aris; Tentes, Aris On 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)}, crossref = {DBLP:conf/tamc/2009}, pages = {108-117}, title = {On the Connection between Interval Size Functions and Path Counting}, year = 2009 }