Sampling of chordal graphs and various types of acyclic orientations over chordal graphs plays a central role in several AI applications such as causal structure learning. For a given undirected graph, an acyclic orientation is an assignment of directions to all of its edges which makes the resulting directed graph cycle-free. Sampling is often closely related to the corresponding counting problem. Counting of acyclic orientations of a given chordal graph can be done in polynomial time, but the previously known techniques do not seem to lead to a corresponding (efficient) sampler. In this work, we propose a dynamic programming framework which yields a counter and a uniform sampler, both of which run in (essentially) linear time. An interesting feature of our sampler is that it is a stand-alone algorithm that, unlike other DP-based samplers, does not need any preprocessing which determines the corresponding counts.
more »
« less
Counting and Sampling Orientations on Chordal Graphs
We study counting problems for several types of orientations of chordal graphs: source-sink-free orientations, sink-free orientations, acyclic orientations, and bipolar orientations, and, for the latter two, we also present linear-time uniform samplers. Counting sink-free, acyclic, or bipolar orientations are known to be #P-complete for general graphs,
motivating our study on a restricted, yet well-studied, graph class. Our
main focus is source-sink-free orientations, a natural restricted version of
sink-free orientations related to strong orientations, which we introduce
in this work. These orientations are intriguing, since despite their similarity,
currently known FPRAS and sampling techniques (such as Markov
chains or sink-popping) that apply to sink-free orientations do not seem
to apply to source-sink-free orientations. We present fast polynomialtime
algorithms counting these orientations on chordal graphs. Our approach
combines dynamic programming with inclusion-exclusion (going
two levels deep for source-sink-free orientations and one level for sinkfree
orientations) throughout the computation. Dynamic programming
counting algorithms can be typically used to produce a uniformly random
sample. However, due to the negative terms of the inclusion-exclusion,
the typical approach to obtain a polynomial-time sampling algorithm
does not apply in our case. Obtaining such an almost uniform sampling
algorithm for source-sink-free orientations in chordal graphs remains an
open problem.
Little is known about counting or sampling of acyclic or bipolar orientations,
even on restricted graph classes. We design efficient (linear-time)
exact uniform sampling algorithms for these orientations on chordal
graphs. These algorithms are a byproduct of our counting algorithms,
but unlike in other works that provide dynamic-programming-based samplers,
we produce a random orientation without computing the corresponding
count, which leads to a faster running time than the counting
algorithm (since it avoids manipulation of large integers).
more »
« less
- NSF-PAR ID:
- 10355288
- Date Published:
- Journal Name:
- International Conference and Workshops on Algorithms and Computation (WALCOM)
- Volume:
- 13174
- Page Range / eLocation ID:
- 352-364
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Sampling Partial Acyclic Orientations in Chordal Graphs by the Lovasz Local Lemma (Student Abstract)null (Ed.)Sampling of various types of acyclic orientations of chordal graphs plays a central role in several AI applications. In this work we investigate the use of the recently proposed general partial rejection sampling technique of Guo, Jerrum, and Liu, based on the Lovasz Local Lemma, for sampling partial acyclic orientations. For a given undirected graph, an acyclic orientation is an assignment of directions to all of its edges so that there is no directed cycle. In partial orientations some edges are allowed to be undirected. We show how the technique can be used to sample partial acyclic orientations of chordal graphs fast and with a clearly specified underlying distribution. This is in contrast to other samplers of various acyclic orientations with running times exponentially dependent on the maximum degree of the graph.more » « less
-
Counting and uniformly sampling motifs in a graph are fundamental algorithmic tasks with numerous applications across multiple fields. Since these problems are computationally expensive, recent efforts have focused on devising sublinear-time algorithms for these problems. We consider the model where the algorithm gets a constant size motif H and query access to a graph G, where the allowed queries are degree, neighbor, and pair queries, as well as uniform edge sample queries. In the sampling task, the algorithm is required to output a uniformly distributed copy of H in G (if one exists), and in the counting task it is required to output a good estimate to the number of copies of H in G. Previous algorithms for the uniform sampling task were based on a decomposition of H into a collection of odd cycles and stars, denoted D∗(H) = {Ok1 , ...,Okq , Sp1 , ..., Spℓ19 }. These algorithms were shown to be optimal for the case where H is a clique or an odd-length cycle, but no other lower bounds were known. We present a new algorithm for sampling arbitrary motifs which, up to poly(log n) factors, for any motif H whose decomposition contains at least two components or at least one star, is always preferable. The main ingredient leading to this improvement is an improved uniform algorithm for sampling stars, which might be of independent interest, as it allows to sample vertices according to the p-th moment of the degree distribution. We further show how to use our sampling algorithm to get an approximate counting algorithm, with essentially the same complexity. Finally, we prove that this algorithm is decomposition-optimal for decompositions that contain at least one odd cycle. That is, we prove that for any decomposition D that contains at least one odd cycle, there exists a motif HD 30 with decomposition D, and a family of graphs G, so that in order to output a uniform copy of H in a uniformly chosen graph in G, the number of required queries matches our upper bound. These are the first lower bounds for motifs H with a nontrivial decomposition, i.e., motifs that have more than a single component in their decomposition.more » « less
-
We consider the problem of orchestrating the execution of workflow applications structured as Directed Acyclic Graphs (DAGs) on parallel computing platforms that are subject to fail-stop failures. The objective is to minimize expected overall execution time, or makespan. A solution to this problem consists of a schedule of the workflow tasks on the available processors and of a decision of which application data to checkpoint to stable storage, so as to mitigate the impact of processor failures. For general DAGs this problem is hopelessly intractable. In fact, given a solution, computing its expected makespan is still a difficult problem. To address this challenge, we consider a restricted class of graphs, Minimal Series-Parallel Graphs (M-SPGS). It turns out that many real-world workflow applications are naturally structured as M-SPGS. For this class of graphs, we propose a recursive list-scheduling algorithm that exploits the M-SPG structure to assign sub-graphs to individual processors, and uses dynamic programming to decide which tasks in these sub-gaphs should be checkpointed. Furthermore, it is possible to efficiently compute the expected makespan for the solution produced by this algorithm, using a first-order approximation of task weights and existing evaluation algorithms for 2-state probabilistic DAGs. We assess the performance of our algorithm for production workflow configurations, comparing it to (i) an approach in which all application data is checkpointed, which corresponds to the standard way in which most production workflows are executed today; and (ii) an approach in which no application data is checkpointed. Our results demonstrate that our algorithm strikes a good compromise between these two approaches, leading to lower checkpointing overhead than the former and to better resilience to failure than the latter.more » « less
-
We show variants of spectral sparsification routines can preserve the total spanning tree counts of graphs, which by Kirchhoff's matrix-tree theorem, is equivalent to determinant of a graph Laplacian minor, or equivalently, of any SDDM matrix. Our analyses utilizes this combinatorial connection to bridge between statistical leverage scores / effective resistances and the analysis of random graphs by [Janson, Combinatorics, Probability and Computing `94]. This leads to a routine that in quadratic time, sparsifies a graph down to about $n^{1.5}$ edges in ways that preserve both the determinant and the distribution of spanning trees (provided the sparsified graph is viewed as a random object). Extending this algorithm to work with Schur complements and approximate Choleksy factorizations leads to algorithms for counting and sampling spanning trees which are nearly optimal for dense graphs. We give an algorithm that computes a $(1 \pm \delta)$ approximation to the determinant of any SDDM matrix with constant probability in about $n^2 \delta^{-2}$ time. This is the first routine for graphs that outperforms general-purpose routines for computing determinants of arbitrary matrices. We also give an algorithm that generates in about $n^2 \delta^{-2}$ time a spanning tree of a weighted undirected graph from a distribution with total variation distance of $\delta$ from the $w$-uniform distribution .more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1007/978-3-030-96731-4_29
