More Like this

1. List-Avoiding Orientations

   https://doi.org/10.1007/s00493-024-00109-z  

   Bradshaw, Peter; Chen, Yaobin; Ma, Hao; Mohar, Bojan; Wu, Hehui (October 2024, Combinatorica)
2. Locally Computing Edge Orientations

   Mitrovic, Slobodan; Rubinfeld, Ronitt; Singhal, Mihir (September 2024, 32nd Annual European Symposium on Algorithms (ESA 2024))

   We consider the question of orienting the edges in a graph G such that every vertex has bounded out-degree. For graphs of arboricity α, there is an orientation in which every vertex has out-degree at most α and, moreover, the best possible maximum out-degree of an orientation is at least α - 1. We are thus interested in algorithms that can achieve a maximum out-degree of close to α. A widely studied approach for this problem in the distributed algorithms setting is a "peeling algorithm" that provides an orientation with maximum out-degree α(2+ε) in a logarithmic number of iterations. We consider this problem in the local computation algorithm (LCA) model, which quickly answers queries of the form "What is the orientation of edge (u,v)?" by probing the input graph. When the peeling algorithm is executed in the LCA setting by applying standard techniques, e.g., the Parnas-Ron paradigm, it requires Ω(n) probes per query on an n-vertex graph. In the case where G has unbounded degree, we show that any LCA that orients its edges to yield maximum out-degree r must use Ω(√ n/r) probes to G per query in the worst case, even if G is known to be a forest (that is, α = 1). We also show several algorithms with sublinear probe complexity when G has unbounded degree. When G is a tree such that the maximum degree Δ of G is bounded, we demonstrate an algorithm that uses Δ n^{1-log_Δ r + o(1)} probes to G per query. To obtain this result, we develop an edge-coloring approach that ultimately yields a graph-shattering-like result. We also use this shattering-like approach to demonstrate an LCA which 4-colors any tree using sublinear probes per query. 

   more » « less
3. Wilson spaces, snaith constructions, and elliptic orientations

   https://doi.org/10.1007/s00222-024-01239-3  

   Chatham, Hood; Hahn, Jeremy; Yuan, Allen (April 2024, Inventiones mathematicae)
4. The flow index and strongly connected orientations

   https://doi.org/10.1016/j.ejc.2017.12.009  

   Li, Jiaao; Thomassen, Carsten; Wu, Yezhou; Zhang, Cun-Quan (May 2018, European Journal of Combinatorics)
5. Counting and Sampling Orientations on Chordal Graphs

   https://doi.org/10.1007/978-3-030-96731-4_29  

   Bezakova, Ivona; Sun, Wenbo (January 2022, International Conference and Workshops on Algorithms and Computation (WALCOM))

   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