2023

1. On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs

   MacRury, Calum, Ma, Will, and Grammel, Nathaniel

   In ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

   Abs arXiv PDF

   We present new results for online contention resolution schemes for the matching polytope of graphs, in the random-order (RCRS) and adversarial (OCRS) arrival models. Our results include improved selectability guarantees (i.e., lower bounds), as well as new impossibility results (i.e., upper bounds). By well-known reductions to the prophet (secretary) matching problem, a c-selectable OCRS (RCRS) implies a c-competitive algorithm for adversarial (random order) edge arrivals. Similar reductions are also known for the query-commit matching problem. For the adversarial arrival model, we present a new analysis of the OCRS of Ezra et al. (EC, 2020). We show that this scheme is 0.344-selectable for general graphs and 0.349-selectable for bipartite graphs, improving on the previous 0.337 selectability result for this algorithm. We also show that the selectability of this scheme cannot be greater than 0.361 for general graphs and 0.382 for bipartite graphs. We further show that no OCRS can achieve a selectability greater than 0.4 for general graphs, and 0.433 for bipartite graphs. For random-order arrivals, we present two attenuation-based schemes which use new attenuation functions. Our first RCRS is 0.474-selectable for general graphs, and our second is 0.476-selectable for bipartite graphs. These results improve upon the recent 0.45 (and 0.456) selectability results for general graphs (respectively, bipartite graphs) due to Pollner et al. (EC, 2022). On general graphs, our 0.474-selectable RCRS provides the best known positive result even for offline contention resolution, and also for the correlation gap. We conclude by proving a fundamental upper bound of 0.5 on the selectability of RCRS, using bipartite graphs.

2022

1. A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process

   Gao, Pu, MacRury, Calum, and Prałat, Paweł

   In RANDOM 2022

   Abs arXiv HTML PDF

   The semi-random graph process is a single player game in which the player is initially presented an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v, and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a Hamiltonian cycle in as few rounds as possible. In particular, we present an adaptive strategy for the player which achieves it in αn rounds, where α< 2.01678 is derived from the solution to some system of differential equations. We also show that the player cannot achieve the desired property in less than βn rounds, where β> 1.26575. These results improve the previously best known bounds and, as a result, the gap between the upper and lower bounds is decreased from 1.39162 to 0.75102.

2. Prophet Matching in the Probe-Commit Model

   Borodin, Allan, MacRury, Calum, and Rakheja, Akash

   In APPROX 2022

   Note Abs arXiv HTML PDF

   We consider the online bipartite stochastic matching problem with known i.d. (independently distributed) online vertex arrivals. In this problem, when an online vertex arrives, its weighted edges must be probed (queried) to determine if they exist, based on known edge probabilities. Our algorithms operate in the probe-commit model, in that if a probed edge exists, it must be used in the matching. Additionally, each online node has a downward-closed probing constraint on its adjacent edges which indicates which sequences of edge probes are allowable. Our setting generalizes the commonly studied patience (or timeout) constraint which limits the number of probes that can be made to an online node’s adjacent edges. Most notably, this includes non-uniform edge probing costs (specified by knapsack/budget constraint). We extend a recently introduced configuration LP to the known i.d. setting, and also provide the first proof that it is a relaxation of an optimal offline probing algorithm (the offline adaptive benchmark). Using this LP, we establish new competitive bounds all of which generalize the standard non-stochastic setting when edges do not need to be probed (i.e., exist with certainty).

   This work generalizes many of the results from a 2020 preprint by the same authors, “Bipartite Stochastic Matching: Online, Random Order, and I.I.D. Models”. The arXiv version is titled "Prophet Matching Meets Probing with Commitment."

3. The Phase Transition of Discrepancy in Random Hypergraphs

   MacRury, Calum, Masařík, Tomáš, Pai, Leilani, and Pérez-Giménez, Xavier

   SIAM Journal on Discrete Mathematics (minor revision) 2022

   Abs arXiv PDF

   Motivated by the Beck-Fiala conjecture, we study the discrepancy problem in two related models of random hypergraphs on n vertices and m edges. In the first (\em edge-independent) model, a random hypergraph H_1 is constructed by fixing a parameter p and allowing each of the n vertices to join each of the m edges independently with probability p. In the parameter range in which pn →∞and pm →∞, we show that with high probability (\whp) H_1 has discrepancy at least Ω(2^-n/m \sqrtpn) when m = O(n), and at least Ω(\sqrtpn \logγ) when m ≫n, where γ= \min{ m/n, pn}. In the second (\em edge-dependent) model, d is fixed and each vertex of H_2 independently joins exactly d edges uniformly at random. We obtain analogous results for this model by generalizing the techniques used for the edge-independent model with p=d/m. Namely, for d →∞and dn/m →∞, we prove that \whp H_2 has discrepancy at least Ω(2^-n/m \sqrtdn/m) when m = O(n), and at least Ω(\sqrt(dn/m) \logγ) when m ≫n, where γ=\min{m/n, dn/m}. Furthermore, we obtain nearly matching asymptotic upper bounds on the discrepancy in both models (when p=d/m), in the dense regime of m ≫n. Specifically, we apply the partial colouring lemma of Lovett and Meka to show that \whp H_1 and H_2 each have discrepancy O( \sqrtdn/m \log(m/n)), provided d →∞, d n/m →∞and m ≫n. This result is algorithmic, and together with the work of Bansal and Meka characterizes how the discrepancy of each random hypergraph model transitions from Θ(\sqrtd) to o(\sqrtd) as m varies from m=Θ(n) to m ≫n.

4. Perfect Matchings in the Semi-random Graph Process

   Gao, Pu, MacRury, Calum, and Prałat, Paweł

   SIAM Journal on Discrete Mathematics 2022

   Abs arXiv HTML PDF

   The semi-random graph process is a single player game in which the player is initially presented an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v, and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a perfect matching in as few rounds as possible. In particular, we present an adaptive strategy for the player which achieves a perfect matching in βn rounds, where the value of β< 1.206 is derived from a solution to some system of differential equations. This improves upon the previously best known upper bound of (1+2/e+o(1)) \,n < 1.736 \,n rounds. We also improve the previously best lower bound of (\ln 2 + o(1)) \,n > 0.693 \,n and show that the player cannot achieve the desired property in less than αn rounds, where the value of α> 0.932 is derived from a solution to another system of differential equations. As a result, the gap between the upper and lower bounds is decreased roughly four times.

5. Localization Game for Random Graphs

   Dudek, Andrzej, English, Sean, Frieze, Alan, MacRury, Calum, and Prałat, Paweł

   Discrete Applied Mathematics 2022

   Abs arXiv HTML PDF

   We consider the localization game played on graphs in which a cop tries to determine the exact location of an invisible robber by exploiting distance probes. The corresponding graph parameter ζ(G) for a given graph G is called the localization number. In this paper, we improve the bounds for dense random graphs determining an asymptotic behaviour of ζ(G). Moreover, we extend the argument to sparse graphs.

6. Hamilton Cycles in the Semi-random Graph Process

   Gao, Pu, Kamiński, Bogumił, MacRury, Calum, and Prałat, Paweł

   European Journal of Combinatorics 2022

   Abs arXiv HTML PDF

   The semi-random graph process is a single player game in which the player is initially presented an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v, and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a Hamilton cycle in as few rounds as possible. In particular, we present a novel strategy for the player which achieves a Hamiltonian cycle in c∗n rounds, where the value of c∗ is the result of a high dimensional optimization problem. Numerical computations indicate that c∗<2.61135. This improves upon the previously best known upper bound of 3n rounds. We also show that the previously best lower bound of (ln2+ln(1+ln2)+o(1))n is not tight.

2021

1. Secretary Matching Meets Probing with Commitment

   Borodin, Allan, MacRury, Calum, and Rakheja, Akash

   In APPROX 2021

   Note Abs arXiv HTML PDF

   Within the context of stochastic probing with commitment, we consider the online stochastic matching problem; that is, the one-sided online bipartite matching problem where edges adjacent to an online node must be probed to determine if they exist based on edge probabilities that become known when an online vertex arrives. If a probed edge exists, it must be used in the matching (if possible). We consider the competitiveness of online algorithms in both the adversarial order model (AOM) and the random order model (ROM). More specifically, we consider a bipartite stochastic graph G = (U,V,E) where U is the set of offline vertices, V is the set of online vertices and G has edge probabilities (p_e)_e ∈E and edge weights (w_e)_e ∈E. Additionally, G has probing constraints (\scrC_v)_v ∈V, where \scrC_v indicates which sequences of edges adjacent to an online vertex v can be probed. We assume that U is known in advance, and that \scrC_v, together with the edge probabilities and weights adjacent to an online vertex are only revealed when the online vertex arrives. This model generalizes the various settings of the classical bipartite matching problem, and so our main contribution is in making progress towards understanding which classical results extend to the stochastic probing model.

   This work generalizes many of the results from a 2020 preprint by the same authors, “Bipartite Stochastic Matching: Online, Random Order, and I.I.D. Models”. The arXiv version is titled "Greedy Approaches to Online Stochastic Matching".

2. Probabilistic Zero Forcing on Random Graphs

   English, Sean, MacRury, Calum, and Prałat, Paweł

   European Journal of Combinatorics 2021

   Note Abs arXiv HTML

   Zero forcing is a deterministic iterative graph coloring process in which vertices are colored either blue or white, and in every round, any blue vertices that have a single white neighbor force these white vertices to become blue. Here we study probabilistic zero forcing, where blue vertices have a non-zero probability of forcing each white neighbor to become blue. We explore the propagation time for probabilistic zero forcing on the Erdős-Réyni random graph G(n,p) when we start with a single vertex colored blue. We show that when p=\log^-o(1)n, then with high probability it takes (1+o(1))\log_2 \log_2 n rounds for all the vertices in G(n,p) to become blue, and when \log n/n ≪p \le \log^-O(1) n, then with high probability it takes Θ(\log(1/p)) rounds.

   Colorings and structural graph theory in context (a tribute to Xuding Zhu)

3. Zero Forcing Number of Random Regular Graphs

   Bal, Deepak, Bennett, Patrick, English, Sean, MacRury, Calum, and Prałat, Paweł

   Journal of Combinatorics 2021

   Abs arXiv HTML PDF

   The zero forcing process is an iterative graph colouring process in which at each time step a coloured vertex with a single uncoloured neighbour can force this neighbour to become coloured. A zero forcing set of a graph is an initial set of coloured vertices that can eventually force the entire graph to be coloured. The zero forcing number is the size of the smallest zero forcing set. We explore the zero forcing number for random regular graphs, improving on bounds given by Kalinowski, Kamc̆ev and Sudakov. We also propose and analyze a degree greedy algorithm for finding small zero forcing sets using the differential equations method.

2020

1. Probabilistically Faulty Searching on a Half-Line

   Bonato, Anthony, Georgiou, Konstantinos, MacRury, Calum, and Prałat, Paweł

   In LATIN 2020

   Abs arXiv HTML

   We study p-Faulty Search, a variant of the classic cow-path optimization problem, where a unit speed robot searches the half-line (or 1-ray) for a hidden item. The searcher is probabilistically faulty, and detection of the item with each visitation is an independent Bernoulli trial whose probability of success p is known. The objective is to minimize the worst case expected detection time, relative to the distance of the hidden item to the origin. A variation of the same problem was first proposed by Gal in 1980. Then in 2003, Alpern and Gal [The Theory of Search Games and Rendezvous] proposed a so-called monotone solution for searching the line (2-rays); that is, a trajectory in which the newly searched space increases monotonically in each ray and in each iteration. Moreover, they conjectured that an optimal trajectory for the 2-rays problem must be monotone. We disprove this conjecture when the search domain is the half-line (1-ray). We provide a lower bound for all monotone algorithms, which we also match with an upper bound. Our main contribution is the design and analysis of a sequence of refined search strategies, outside the family of monotone algorithms, which we call t-sub-monotone algorithms. Such algorithms induce performance that is strictly decreasing with t, and for all p ∈(0,1). The value of t quantifies, in a certain sense, how much our algorithms deviate from being monotone, demonstrating that monotone algorithms are sub-optimal when searching the half-line.

2018

1. The Robot Crawler Graph Process

   Bonato, Anthony, del Río-Chanona, Rita M., MacRury, Calum, Nicolaidis, Jake, Pérez-Giménez, Xavier, Prałat, Paweł, and Ternovsky, Kirill

   Discrete Applied Mathematics 2018

   Note Abs HTML

   Information gathering by crawlers on the web is of practical interest. We consider a simplified model for crawling complex networks such as the web graph, which is a variation of the robot vacuum edge-cleaning process of Messinger and Nowakowski. In our model, a crawler visits nodes via a deterministic walk determined by their weightings which change during the process deterministically. The minimum, maximum, and average time for the robot crawler to visit all the nodes of a graph is considered on various graph classes such as trees, multi-partite graphs, binomial random graphs, and graphs generated by the preferential attachment model.

   Journal version of “The Robot Crawler Number of a Graph”.

2. Distribution of Coefficients of Rank Polynomials for Random Sparse Graphs

   Jakobson, Dmitry, MacRury, Calum, Norin, Sergey, and Turner, Lise

   The Electronic Journal of Combinatorics 2018

   Abs HTML PDF

   We study the distribution of coefficients of rank polynomials of random sparse graphs. We first discuss the limiting distribution for general graph sequences that converge in the sense of Benjamini-Schramm. Then we compute the limiting distri-bution and Newton polygons of the coefficients of the rank polynomial of randomd-regular graphs.

2015

1. The Robot Crawler Number of a Graph

   Bonato, Anthony, Rı́o-Chanona, Rita M., MacRury, Calum, Nicolaidis, Jake, Pérez-Giménez, Xavier, Prałat, Paweł, and Ternovsky, Kirill

   In WAW 2015

   Note Abs HTML

   Information gathering by crawlers on the web is of practical interest. We consider a simplified model for crawling complex networks such as the web graph, which is a variation of the robot vacuum edge-cleaning process of Messinger and Nowakowski. In our model, a crawler visits nodes via a deterministic walk determined by their weightings which change during the process deterministically. The minimum, maximum, and average time for the robot crawler to visit all the nodes of a graph is considered on various graph classes such as trees, multi-partite graphs, binomial random graphs, and graphs generated by the preferential attachment model.

   Conference version of “The Robot Crawler Graph Process”.

2022

1. Optimizing Transport Frequency in Multi-Layered Urban Transportation Networks for Pandemic Prevention

   MacRury, Calum, Polituchyi, Nykyta, Prałat, Paweł, Siuta, Kinga, and Szufel, Przemysław

   2022

   Abs PDF

   In this paper, we identify determinants of pandemic spread in urban populations. Specifically, we develop a multi-agent simulation framework to model virus spread in complex networks. Our agents periodically commute between home and work via a combination of walking routes and public transit, and make decisions intelligently based upon their location, available routes, and expectations of public transport arrival times. Our infection scheme allows for different contagiousness levels, as a function of the virus’s strain and where the agents interact (i.e., inside or outside). Our results show that the pandemic’s scale is heavily impacted by the network’s structure, and the decision making of the agents. In particular, the progression of the pandemic greatly differs when agents primarily infect each other in a crowded urban transportation system, opposed to while walking. Additionally, the results show that local subgraph characteristics, including topology, structure, and statistics such as its degree distribution and density, affect the viruses’ transmission rates. We also assess the effect of modifying the public transport’s running frequency on the spread of two different virus strains (with different levels of contagiousness). In particular, lowering the running frequency can discourage agents from taking public transportation too often, especially for shorter distances. On the other hand, the low frequency contributes to more crowded streetcars or subway cars if the policy is not designed correctly, which is why such an analysis may prove valuable for finding “sweet spots” that optimize the system. The proposed approach has been validated on real world data, and a model of the transportation network of downtown Toronto. The framework used is flexible and can be easily adjusted to model other urban environments, and additional forms of transportation (such as carpooling, ride-share and more).

2. Sharp Thresholds in Adaptive Random Graph Processes

   MacRury, Calum, and Surya, Erlang

   2022

   Abs arXiv PDF

   Suppose that K_n is the complete graph on vertex set [n], and \mathcalD is a distribution on subsets of its edges. The \mathcalD-adaptive random graph process (or \mathcalD-process) is a single player game in which the player is initially presented the empty graph on [n]. In each step, a subset of edges of K_n, say X, is independently sampled from \mathcalD and presented to the player. The player then adaptively selects precisely one edge e from X, and adds e to its current graph. For a fixed (edge) monotone graph property, the objective of the player is to force the graph to satisfy the property in as few steps as possible. Through appropriate choices of \mathcalD, the \mathcalD-process generalizes well-studied adaptive processes, such as the Achlioptas process and the semi-random graph process. We prove a theorem which gives a sufficient condition for the existence of a sharp threshold for the property \mathcalP in the \mathcalD-process. We apply our theorem to the semi-random graph process and prove the existence of a sharp threshold when \mathcalP corresponds to being Hamiltonian or to containing a perfect matching. These are the first results for the semi-random graph process which show the existence of a sharp threshold when \mathcalP corresponds to containing a \textitsparse spanning graph. Using a separate analytic argument, we show that each sharp threshold is of the form C_\mathcalPn for some fixed constant C_\mathcalP>0. This answers two of the open problems proposed by Ben-Eliezer et al. (SODA 2020) in the affirmative. Unlike similar results which establish sharp thresholds for certain distributions and properties, we establish the existence of sharp thresholds without explicitly identifying asymptotically optimal strategies.

2021

2020

1. Bipartite Stochastic Matching: Online, Random Order, and I.I.D. Models

   Borodin, Allan, MacRury, Calum, and Rakheja, Akash

   2020

   Note Abs arXiv PDF

   Within the context of stochastic probing with commitment, we consider the online stochastic matching problem; that is, the one sided online bipartite matching problem where edges adjacent to an online node must be probed to determine if they exist, based on known edge probabilities. If a probed edge exists, it must be used in the matching (if possible). We study this problem in the generality of a patience (or budget) constraint which limits the number of probes that can be made to edges adjacent to an online node. The patience constraint results in modelling and computational efficiency issues that are not encountered in the special cases of unit patience and full (i.e., unlimited) patience. The stochastic matching problem leads to a variety of settings. Our main contribution is to provide a new LP relaxation and a unified approach for establishing new and improved competitive bounds in three different input model settings (namely, adversarial, random order, and known i.i.d.). In all these settings, the algorithm does not have any control on the ordering of the online nodes. We establish competitive bounds in these settings, all of which generalize the standard non-stochastic setting when edges do not need to be probed (i.e., exist with certainty). All of our competitive ratios hold for arbitrary edge probabilities and patience constraints: (1) A 1−1/e ratio when the stochastic graph is known, offline vertices are weighted and online arrivals are adversarial. (2) A 1−1/e ratio when the stochastic graph is known, edges are weighted, and online arrivals are given in random order (i.e., in ROM, the random order model). (3) A 1−1/e ratio when online arrivals are drawn i.i.d. from a known stochastic type graph and edges are weighted. (4) A (tight) 1/e ratio when the stochastic graph is unknown, edges are weighted and online arrivals are given in random order.

   This work is an earlier version of works “Prophet Matching Meets Probing with Commitment” and “Secretary Matching Meets Probing with Commitment”.

2016

1. Injective Colouring of Binomial Random Graphs

   Rı́o-Chanona, Rita M., MacRury, Calum, Nicolaidis, Jake, Pérez-Giménez, Xavier, Prałat, Paweł, and Ternovsky, Kirill

   2016

   Abs PDF

   The injective chromatic number of a graph G is the minimum number of colours needed to colour the vertices of G so that two vertices with a common neighbour receive distinct colours. In this paper, we investigate the injective chromatic number of the binomial random graph G(n, p) for a wide range of p. We also study a natural generalization of this graph parameter for the same model of random graphs.