Search

We determine the computational complexity of approximately counting and sampling independent sets of a given size in bounded-degree graphs. That is, we identify a critical density α c(Δ ) and provide (i) for α <α c(Δ) randomized polynomial-time algorithms for approximately sampling and counting independent sets of given size at most \alpha n in n-vertex graphs of maximum degree Δ, and (ii) a proof that unless NP = RP, no such algorithms exist for α >α c(Δ ). The critical density is the occupancy fraction of the hard-core model on the complete graph Δ +1 at the uniqueness threshold on the infinite Δ -regular tree, giving α c(Δ ) ~ e/1+ e 1\Δ as Δ →. Our methods apply more generally to antiferromagnetic 2-spin systems and motivate new questions in extremal combinatorics. [ABSTRACT FROM AUTHOR]

Scores based on Shapley values are widely used for providing explanations to classification results over machine learning models. A prime example of this is the influential SHAP-score, a version of the Shapley value that can help explain the result of a learned model on a specific entity by assigning a score to every feature. While in general computing Shapley values is a computationally intractable problem, we prove a strong positive result stating that the SHAP-score can be computed in polynomial time over deterministic and decomposable Boolean circuits under the so-called product distributions on entities. Such circuits are studied in the field of Knowledge Compilation and generalize a wide range of Boolean circuits and binary decision diagrams classes, including binary decision trees, Ordered Binary Decision Diagrams (OBDDs) and Free Binary Decision Diagrams (FBDDs). Our positive result extends even beyond binary classifiers, as it continues to hold if each feature is associated with a finite domain of possible values. We also establish the computational limits of the notion of SHAP-score by observing that, under a mild condition, computing it over a class of Boolean models is always polynomially as hard as the model counting problem for that class. This implies that both determinism and decomposability are essential properties for the circuits that we consider, as removing one or the other renders the problem of computing the SHAP-score intractable (namely, #P-hard). It also implies that computing SHAP-scores is #P-hard even over the class of propositional formulas in DNF. Based on this negative result, we look for the existence of fully-polynomial randomized approximation schemes (FPRAS) for computing SHAP-scores over such class. In stark contrast to the model counting problem for DNF formulas, which admits an FPRAS, we prove that no such FPRAS exists (under widely believed complexity assumptions) for the computation of SHAP-scores. Surprisingly, this negative result holds even for the class of monotone formulas in DNF. These techniques can be further extended to prove another strong negative result: Under widely believed complexity assumptions, there is no polynomial-time algorithm that checks, given a monotone DNF formula φ and features x, y, whether the SHAP-score of x in φ is smaller than the SHAP-score of y in φ. [ABSTRACT FROM AUTHOR]

We present a randomized algorithm for generating standard set-valued tableaux by extending the Green-Nijenhuis-Wilf hook walk algorithm. In the case of asymptotically rank two partitions, we use this algorithm to give a fully polynomial almost uniform sampler (FPAUS) for standard set-valued tableaux. This FPAUS is then used to construct a fully polynomial randomized approximation scheme (FPRAS) for counting the number of standard set-valued tableaux for such shapes. We also construct a FPAUS and FPRAS for standard set-valued tableaux when either the size of the partition or the difference between the maximum value and the size of the partition is fixed. Our methods build on the work of Jerrum-Valiant-Vazirani and provide a framework for constructing FPAUS's and FPRAS's for other counting problems in algebraic combinatorics. [ABSTRACT FROM AUTHOR]

A k -stable c -coloured Candy Crush grid is a weak proper c -colouring of a particular type of k -uniform hypergraph. In this paper we introduce a fully polynomial randomised approximation scheme (FPRAS) which counts the number of k -stable c -coloured Candy Crush grids of a given size (m , n) for certain values of c and k. We implemented this algorithm on Matlab, and found that in a Candy Crush grid with 7 available colours there are approximately 4. 3 × 1 0 61 3-stable colourings. (Note that, typical Candy Crush games are played with 6 colours and our FPRAS is not guaranteed to work in expected polynomial time with k = 3 and c = 6.) We also discuss the applicability of this FPRAS to the problem of counting the number of weak c -colourings of other, more general hypergraphs. [ABSTRACT FROM AUTHOR]

Jerrum, Sinclair, and Vigoda [J. ACM, 51 (2004), pp. 671--697] showed that the permanent of any square matrix can be estimated in polynomial time. This computation can be viewed as approximating the partition function of edge-weighted matchings in a bipartite graph. Equivalently, this may be viewed as approximating the partition function of vertex-weighted independent sets in the line graph of a bipartite graph. Line graphs of bipartite graphs are perfect graphs and are known to be precisely the class of (claw, diamond, odd hole)-free graphs. So how far does the result of Jerrum, Sinclair, and Vigoda extend? We first show that it extends to (claw, odd hole)-free graphs, and then show that it extends to the even larger class of (fork, odd hole)-free graphs. Our techniques are based on graph decompositions, which have been the focus of much recent work in structural graph theory, and on structural results of Chv'atal and Sbihi [J. Combin. Theory Ser. B, 44 (1988)], Maffray and Reed [J. Combin. Theory Ser. B, 75 (1999)], and Lozin and Milaniv c [J. Discrete Algorithms, 6 (2008), pp. 595--604]. [ABSTRACT FROM AUTHOR]

Abstract We study the complexity of computing the partition function of medians for binary strings with Hamming distance using various weight functions. When the weight function is the factorial function, this partition function has application in bioinformatics, counting the most parsimonious scenarios on a star tree under the Single Cut-or-Join model for genome rearrangement. Although this model is computationally simple, we show that it is #P-complete to compute the partition function. Our results are also extended to binary trees as we show that it is #P-complete to calculate the most parsimonious scenarios on an arbitrary binary tree under the Single Cut-or-Join model. These results also apply to substitution models for many biological sequences. [ABSTRACT FROM AUTHOR]

Korn and Pak (2007) [3] conjectured that there exists a fully polynomial randomized approximation scheme (fpras) for approximating the number of ways of tiling a 4 n × 4 m rectangular lattice with T-tetrominoes. Using a flow argument, we prove this conjecture in affirmative by showing that the mixing time of an appropriate Markov chain is polynomial in the area of the lattice. [ABSTRACT FROM AUTHOR]

We consider the time complexity of problems of counting paths and cycles in a graph, respectively. We first show that these two problems are #P-hard. Then, we show an inapproximability result: there is no FPRAS for approximately counting paths and cycles in a graph, respectively unless R P = N P . [ABSTRACT FROM AUTHOR]

Recently, we have found that the concept of P-stability has interesting applications in network privacy. In the context of Online Social Networks it may be used for obtaining a fully polynomial randomized approximation scheme for graph masking and measuring disclosure risk. Also by using the characterization for P-stable sequences from Jerrum, McKay and Sinclair (1992) it is possible to obtain optimal approximations for the problem of k -degree anonymity. In this paper, we present results on P-stability considering the additional restriction that the degree sequence must not intersect the edges of an excluded graph X , improving earlier results on P-stability. As a consequence we extend the P-stable classes of scale-free networks from Torra et al. (2015), obtain an optimal solution for k -anonymity and prove that all the known conditions for P-stability are sufficient for sequences to be graphic. [ABSTRACT FROM AUTHOR]

The Single Cut or Join (SCJ) operation on genomes, generalizing chromosome evolution by fusions and fissions, is the computationally simplest known model of genome rearrangement. While most genome rearrangement problems are already hard when comparing three genomes, it is possible to compute in polynomial time a most parsimonious SCJ scenario for an arbitrary number of genomes related by a binary phylogenetic tree. Here we consider the problems of sampling and counting the most parsimonious SCJ scenarios. We show that both the sampling and counting problems are easy for two genomes, and we relate SCJ scenarios to alternating permutations. However, for an arbitrary number of genomes related by a binary phylogenetic tree, the counting and sampling problems become hard. We prove that if a Fully Polynomial Randomized Approximation Scheme or a Fully Polynomial Almost Uniform Sampler exist for the most parsimonious SCJ scenario, then RP = NP . The proof has a wider scope than genome rearrangements: the same result holds for parsimonious evolutionary scenarios on any set of discrete characters. [ABSTRACT FROM AUTHOR]

The reliability polynomial of a graph counts its connected subgraphs of various sizes. Algorithms based on sequential importance sampling (SIS) have been proposed to estimate a graph's reliability polynomial. We develop an improved SIS algorithm for estimating the reliability polynomial. The new algorithm runs in expected time O( mlog n α( m, n)) at worst and ≈ m in practice, compared to Θ( m) for the previous algorithm. We analyze the error bounds of this algorithm, including comparison to alternative estimation algorithms. In addition to the theoretical analysis, we discuss methods for estimating the variance and describe experimental results on a variety of random graphs. [ABSTRACT FROM AUTHOR]

In many fault detection problems, we want to detect or identify defective items in a sample set by using the minimum number of tests. Group testing is for the scenario where each test is on a subset of items, and tells whether the subset contains at least one defective item or not. Another practically important problem is to estimate the number of defective items in a sample set. In this paper, we present an efficient FPRAS (fully polynomial-time randomized approximation scheme) type group testing procedure to approximate the number of defective items in a sample set. [ABSTRACT FROM AUTHOR]

The Tutte polynomial of a graph G is a two-variable polynomial T( G; x, y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for rationals x and y: given as input a planar graph G, determine T( G; x, y). Vertigan completely mapped the complexity of exactly computing the Tutte polynomial of a planar graph. He showed that the problem can be solved in polynomial time if ( x, y) is on the hyperbola H given by ( x − 1)( y − 1) = q for q = 1 or q = 2 or if ( x, y) is one of the two special points ( x, y) = (−1, −1) or ( x, y) = (1, 1). Otherwise, the problem is #P-hard. In this paper, we consider the problem of approximating T( G; x, y), in the usual sense of 'fully polynomial randomized approximation scheme' or FPRAS. Roughly speaking, an FPRAS is required to produce, in polynomial time and with high probability, an answer that has small relative error. Assuming that NP is different from RP, we show that there is no FPRAS for the Tutte polynomial in a large portion of the ( x, y) plane. In particular, there is no FPRAS if x > 1, y < −1 or if y > 1, x < −1 or if x < 0, y < 0 and q > 5. Also, there is no FPRAS if x < 1, y < 1 and q = 3. For q > 5, our result is intriguing because it shows that there is no FPRAS at ( x, y) = (1 − q/(1 + ε), − ε) for any positive ε but it leaves open the limit point ε = 0, which corresponds to approximately counting q-colorings of a planar graph. [ABSTRACT FROM AUTHOR]

Abstract: The huge number of solutions in genome rearrangement problems calls for algorithms for counting and sampling in the space of solutions, rather than drawing one arbitrary scenario. A closed formula exists for counting the number of scenarios between co-tailed genomes, but no polynomial result has been published so far for arbitrary genomes. We prove here that it admits a Fully Polynomial time Randomized Approximation Scheme. We use an almost uniform sampler and prove that it converges to the uniform distribution in fully polynomial time. The can be used to quickly draw a sample of scenarios from a prescribed distribution and test some hypotheses on genome evolution. [Copyright &y& Elsevier]

The problems of uniformly sampling and approximately counting contingency tables have been widely studied, but efficient solutions are only known in special cases. One appealing approach is the Diaconis and Gangolli Markov chain which updates the entries of a random 2×2 submatrix. This chain is known to be rapidly mixing for cell-bounded tables only when the cell bounds are all 1 and the row and column sums are regular. We demonstrate that the chain can require exponential time to mix in the cell-bounded case, even if we restrict to instances for which the state space is connected. Moreover, we show the chain can be slowly mixing even if we restrict to natural classes of problem instances, including regular instances with cell bounds of either 0 or 1 everywhere, and dense instances where at least a linear number of cells in each row or column have non-zero cell-bounds. [ABSTRACT FROM AUTHOR]

We present a nearly-linear time algorithm for counting and randomly generating simple graphs with a given degree sequence in a certain range. For degree sequence ( d) with maximum degree d= O( m), our algorithm generates almost uniform random graphs with that degree sequence in time O( md) where $m=\frac{1}{2}\sum_{i}d_{i}$ is the number of edges in the graph and τ is any positive constant. The fastest known algorithm for uniform generation of these graphs (McKay and Wormald in J. Algorithms 11(1):52-67, ) has a running time of O( m d). Our method also gives an independent proof of McKay's estimate (McKay in Ars Combinatoria A 19:15-25, ) for the number of such graphs. We also use sequential importance sampling to derive fully Polynomial-time Randomized Approximation Schemes (FPRAS) for counting and uniformly generating random graphs for the same range of d= O( m). Moreover, we show that for d= O( n), our algorithm can generate an asymptotically uniform d-regular graph. Our results improve the previous bound of d= O( n) due to Kim and Vu (Adv. Math. 188:444-469, ) for regular graphs. [ABSTRACT FROM AUTHOR]

In this paper, we propose the first fully polynomial-time randomized approximation scheme (FPRAS) for closed Jackson networks with single servers. Our algorithm is based on the Markov chain Monte Carlo (MCMC) method, and our scheme returns an approximate solution, for which the size of error satisfies a given error rate. We propose two Markov chains: one is for approximate sampling, and the other is for perfect sampling based on the monotone coupling from the past algorithm. [ABSTRACT FROM AUTHOR]

• Develops network reliability approximation with user-specified error and confidence. • Relies on a counting method and increasingly powerful satisfiability (SAT) solvers. • Discusses results of our method relative to several modern competitive techniques. • Showcases our capabilities using ideal networks and power transmission grids. As engineered systems expand, become more interdependent, and operate in real-time, reliability assessment is key to inform investment and decision making. However, network reliability problems are known to be #P-complete, a computational complexity class believed to be intractable, and thus motivate the quest for approximations. Based on their theoretical foundations, reliability evaluation methods can be grouped as: (i) exact or bounds , (ii) guarantee-less sampling , and (iii) probably approximately correct (PAC). Group (i) is well regarded due to its useful byproducts, but it does not scale in practice. Group (ii) scales well and verifies desirable properties, such as the bounded relative error , but it lacks error guarantees. Group (iii) is of great interest when precision and scalability are required. We introduce K -RelNet, an extended counting-based method that delivers PAC guarantees for the K -terminal reliability problem. We also put our developments in context relative to classical and emerging techniques to facilitate dissemination. Then, we test in a fair way the performance of competitive methods using various benchmark systems. We note the range of application of algorithms and suggest a foundation for future computational reliability and resilience engineering, given the need for principled uncertainty quantification across complex networked systems. [ABSTRACT FROM AUTHOR]