164 research outputs found
Counting Constraint Satisfaction Problems
No full textThis chapter surveys counting Constraint Satisfaction Problems (counting CSPs, or #CSPs) and their computational complexity. It aims to provide an introduction to the main concepts and techniques, and present a representative selection of results and open problems. It does not cover holants, which are the subject of a separate chapter
Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling
No full textWe present a perfect simulation of the hard disks model via the partial rejection sampling method. Provided the density of disks is not too high, the method produces exact samples in O(log n) rounds, where n is the expected number of disks. The method extends easily to the hard spheres model in d>2 dimensions. In order to apply the partial rejection method to this continuous setting, we provide an alternative perspective of its correctness and run-time analysis that is valid for general state spaces
A complexity trichotomy for approximately counting list H-colourings
No full textWe examine the computational complexity of approximately counting the list H-colourings of a graph. We discover a natural graph-theoretic trichotomy based on the structure of the graph H. If H is an irreflexive bipartite graph or a reflexive complete graph then counting list H-colourings is trivially in polynomial time. Otherwise, if H is an irreflexive bipartite permutation graph or a reflexive proper interval graph then approximately counting list H-colourings is equivalent to #BIS, the problem of approximately counting independent sets in a bipartite graph. This is a well-studied problem which is believed to be of intermediate complexity – it is believed that it does not have an FPRAS, but that it is not as difficult as approximating the most difficult counting problems in #P. For every other graph H, approximately counting list H-colourings is complete for #P with respect to approximation-preserving reductions (so there is no FPRAS unless NP = RP). Two pleasing features of the trichotomy are (i) it has a natural formulation in terms of hereditary graph classes, and (ii) the proof is largely self-contained and does not require any universal algebra (unlike similar dichotomies in the weighted case). We are able to extend the hardness results to the bounded-degree setting, showing that all hardness results apply to input graphs with maximum degree at most 6
08201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms
No full textFrom 11.05.08 to 16.05.08, the Dagstuhl Seminar 08201
``Design and Analysis of Randomized and Approximation Algorithms''
was held in the International Conference and Research Center (IBFI),
Schloss Dagstuhl.
During the seminar, several participants presented their current
research work, and ongoing work and open problems were discussed.
Abstracts of the presentations which were given during the seminar as well as
abstracts of seminar results and ideas are put together in this paper.
The first section describes the seminar topics and goals in general.
Links to extended abstracts or full paper are provided, if available
10481 Executive Summary – Computational Counting
No full textFrom November 28 to December 3 2010, the Dagstuhl seminar 10481
``Computational Counting'' was held in Schloss Dagstuhl – Leibnitz Center
for Informatics. 36 researchers from all over the world, with interests and
expertise in different aspects of computational counting, actively
participated in the meeting
05201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms
No full textFrom 15.05.05 to 20.05.05, the Dagstuhl Seminar 05201 ``Design and Analysis of Randomized and Approximation Algorithms'' was held
in the International Conference and Research Center (IBFI),
Schloss Dagstuhl.
During the seminar, several participants presented their current
research, and ongoing work and open problems were discussed. Abstracts of
the presentations given during the seminar as well as abstracts of
seminar results and ideas are put together in this paper. The first section
describes the seminar topics and goals in general.
Links to extended abstracts or full papers are provided, if available
10481 Abstracts Collection – Computational Counting
No full textFrom November 28 to December 3 2010, the Dagstuhl Seminar 10481 ``Computational Counting'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics.
During the seminar, several participants presented their current
research, and ongoing work and open problems were discussed. Abstracts of
the presentations given during the seminar as well as abstracts of
seminar results and ideas are put together in this paper. The first section
describes the seminar topics and goals in general.
Links to extended abstracts or full papers are provided, if available
A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
No full textWe give a fully polynomial-time randomized approximation scheme (FPRAS) for the all-terminal network reliability problem, which is to determine the probability that, in a undirected graph, assuming each edge fails independently, the remaining graph is still connected. Our main contribution is to confirm a conjecture by Gorodezky and Pak (Random Struct. Algorithms, 2014), that the expected running time of the "cluster-popping" algorithm in bi-directed graphs is bounded by a polynomial in the size of the input
Computational Counting (Dagstuhl Seminar 17341)
No full textThis report documents the program and the outcomes of Dagstuhl Seminar 17341 "Computational Counting". The seminar was held from 20th to 25th August 2017, at Schloss Dagstuhl -- Leibnitz Center for Informatics.
A total of 43 researchers from all over the world, with interests and expertise in different aspects of computational counting, actively participated in the meeting
- …
