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 cyclefree. 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 standalone algorithm that, unlike other DPbased samplers, does not need any preprocessing which determines the corresponding counts.
Counting and Sampling Orientations on Chordal Graphs
We study counting problems for several types of orientations of chordal graphs: sourcesinkfree orientations, sinkfree orientations, acyclic orientations, and bipolar orientations, and, for the latter two, we also present lineartime uniform samplers. Counting sinkfree, acyclic, or bipolar orientations are known to be #Pcomplete for general graphs,
motivating our study on a restricted, yet wellstudied, graph class. Our
main focus is sourcesinkfree orientations, a natural restricted version of
sinkfree 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 sinkpopping) that apply to sinkfree orientations do not seem
to apply to sourcesinkfree orientations. We present fast polynomialtime
algorithms counting these orientations on chordal graphs. Our approach
combines dynamic programming with inclusionexclusion (going
two levels deep for sourcesinkfree 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 inclusionexclusion,
the typical approach to obtain a polynomialtime sampling algorithm
does not apply in our case. Obtaining such an almost uniform sampling
algorithm for sourcesinkfree 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 more »
 Publication Date:
 NSFPAR ID:
 10355288
 Journal Name:
 International Conference and Workshops on Algorithms and Computation (WALCOM)
 Volume:
 13174
 Page Range or eLocationID:
 352364
 Sponsoring Org:
 National Science Foundation
More Like this


Sampling Partial Acyclic Orientations in Chordal Graphs by the Lovasz Local Lemma (Student Abstract)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.

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 sublineartime 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 oddlength 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 twomore »

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 failstop 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 SeriesParallel Graphs (MSPGS). It turns out that many realworld workflow applications are naturally structured as MSPGS. For this class of graphs, we propose a recursive listscheduling algorithm that exploits the MSPG structure to assign subgraphs to individual processors, and uses dynamic programming to decide which tasks in these subgaphs should be checkpointed. Furthermore, it is possible to efficiently compute the expected makespan for the solution produced by this algorithm, using a firstorder approximation of task weights and existing evaluation algorithms for 2state probabilistic DAGs. We assess the performance ofmore »

We show variants of spectral sparsification routines can preserve the total spanning tree counts of graphs, which by Kirchhoff's matrixtree 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 generalpurpose 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 totalmore »