More Like this

1. Stochastic Matching via In-n-Out Local Computation Algorithms

   Azarmehr, Amir; Behnezhad, Soheil; Ghafari, Alma; Rubinfeld, Ronitt (June 2025, 57th Annual ACM Symposium on Theory of Computing (STOC 2025))

   Consider the following stochastic matching problem. We are given a known graph 𝐺 = (𝑉 , 𝐸). An unknown subgraph 𝐺𝑝 = (𝑉 , 𝐸𝑝 ) is realized where 𝐸𝑝 includes every edge of 𝐸 independently with some probability 𝑝 ∈ (0, 1]. The goal is to query a sparse subgraph 𝐻 of 𝐺, such that the realized edges in 𝐻 include an approximate maximum matching of 𝐺𝑝 . This problem has been studied extensively over the last decade due to its applications in kidney exchange, online dating, and online labor markets. For any fixed 𝜀 > 0, [BDH STOC’20] showed that any graph 𝐺 has a subgraph 𝐻 with quasipoly(1/𝑝) = (1/𝑝)poly(log(1/𝑝 ) ) maximum degree, achieving a (1 − 𝜀)-approximation. A major open question is the best approximation achievable with poly(1/𝑝)- degree subgraphs. A long line of work has progressively improved the approximation in the poly(1/𝑝)-degree regime from .5 [BDH+ EC’15] to .501 [AKL EC’17], .656 [BHFR SODA’19], .666 [AB SOSA’19], .731 [BBD SODA’22] (bipartite graphs), and most recently to .68 [DS ’24]. In this work, we show that a poly(1/𝑝)-degree subgraph can obtain a (1 − 𝜀)-approximation for any desirably small fixed 𝜀 > 0, achieving the best of both worlds. Beyond its quantitative improvement, a key conceptual contribu- tion of our work is to connect local computation algorithms (LCAs) to the stochastic matching problem for the first time. While prior work on LCAs mainly focuses on their out-queries (the number of vertices probed to produce the output of a given vertex), our analysis also bounds the in-queries (the number of vertices that probe a given vertex). We prove that the outputs of LCAs with bounded in- and out-queries (in-n-out LCAs for short) have limited correlation, a property that our analysis crucially relies on and might find applications beyond stochastic matchings. 

   more » « less
2. On the Maximum Spread of Planar and Outerplanar Graphs

   https://doi.org/10.37236/11844  

   Li, Zelong; Linz, William; Lu, Linyuan; Wang, Zhiyu (July 2024, The Electronic Journal of Combinatorics)

   The spread of a graph $$G$$ is the difference between the largest and smallest eigenvalue of the adjacency matrix of $$G$$. Gotshall, O'Brien and Tait conjectured that for sufficiently large $$n$$, the $$n$$-vertex outerplanar graph with maximum spread is the graph obtained by joining a vertex to a path on $n-1$ vertices. In this paper, we disprove this conjecture by showing that the extremal graph is the graph obtained by joining a vertex to a path on $$\lceil(2n-1)/3\rceil$$ vertices and $$\lfloor(n-2)/3\rfloor$$ isolated vertices. For planar graphs, we show that the extremal $$n$$-vertex planar graph attaining the maximum spread is the graph obtained by joining two nonadjacent vertices to a path on $$\lceil(2n-2)/3\rceil$$ vertices and $$\lfloor(n-4)/3\rfloor$$ isolated vertices. 

   more » « less
3. A Note on the Gyárfás–Sumner Conjecture

   https://doi.org/10.1007/s00373-024-02754-z  

   Nguyen, Tung; Scott, Alex; Seymour, Paul (April 2024, Graphs and Combinatorics)

   The Gyárfás–Sumner conjecture says that for every tree T and every integer t ≥ 1, if G is a graph with no clique of size t and with sufficiently large chromatic number, then G contains an induced subgraph isomorphic to T. This remains open, but we prove that under the same hypotheses, G contains a subgraph H isomorphic to T that is “path-induced”; that is, for some distinguished vertex r, every path of H with one end r is an induced path of G. 

   more » « less
4. Cops and Robbers on P5-Free Graphs

   https://doi.org/10.1137/23M1549912  

   Chudnovsky, Maria; Norin, Sergey; Seymour, Paul D; Turcotte, Jérémie (March 2024, SIAM Journal on Discrete Mathematics)

   We prove that every connected P5-free graph has cop number at most two, solving a conjecture of Sivaraman. In order to do so, we first prove that every connected P5-free graph G with independence number at least three contains a three-vertex induced path with vertices a-b-c in order, such that every neighbor of c is also adjacent to one of a,b. 

   more » « less
5. Sampling List Packings

   https://doi.org/10.4230/LIPIcs.ITCS.2025.24  

   Camrud, Evan; Davies, Ewan; Karduna, Alex; Lee, Holden (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   We initiate the study of approximately counting the number of list packings of a graph. The analogous problem for usual vertex coloring and list coloring has attracted substantial attention. For list packing the setup is similar, but we seek a full decomposition of the lists of colors into pairwise-disjoint proper list colorings. The existence of a list packing implies the existence of a list coloring, but the converse is false. Recent works on list packing have focused on existence or extremal results of on the number of list packings, but here we turn to the algorithmic aspects of counting and sampling. In graphs of maximum degree Δ and when the number of colors is at least Ω(Δ²), we give a fully polynomial-time randomized approximation scheme (FPRAS) based on rapid mixing of a natural Markov chain (the Glauber dynamics) which we analyze with the path coupling technique. Some motivation for our work is the investigation of an atypical spin system, one where the number of spins for each vertex is much larger than the graph degree. 

   more » « less