skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


This content will become publicly available on July 1, 2026

Title: A counterexample to the coarse Menger conjecture
Menger's well-known theorem from 1927 characterizes when it is possible to find k vertex-disjoint paths between two sets of vertices in a graph G. Recently, Georgakopoulos and Papasoglu and, independently, Albrechtsen, Huynh, Jacobs, Knappe and Wollan conjectured a coarse analogue of Menger's theorem, when the k paths are required to be pairwise at some distance at least d. The result is known for k ≤ 2, but we will show that it is false for all k ≥ 3, even if G is constrained to have maximum degree at most three. We also give a simpler proof of the result when k = 2.  more » « less
Award ID(s):
2154169
PAR ID:
10607909
Author(s) / Creator(s):
; ;
Publisher / Repository:
ScienceDirect operated by Elsevier
Date Published:
Journal Name:
Journal of Combinatorial Theory, Series B
Volume:
173
Issue:
C
ISSN:
0095-8956
Page Range / eLocation ID:
68 to 82
Subject(s) / Keyword(s):
Menger's Theorem Connectivity Coarse graph theory
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Bringmann, Karl; Grohe, Martin; Puppis, Gabriele; Svensson, Ola (Ed.)
    In the k-Disjoint Shortest Paths (k-DSP) problem, we are given a graph G (with positive edge weights) on n nodes and m edges with specified source vertices s_1, … , s_k, and target vertices t_1, … , t_k, and are tasked with determining if G contains vertex-disjoint (s_i,t_i)-shortest paths. For any constant k, it is known that k-DSP can be solved in polynomial time over undirected graphs and directed acyclic graphs (DAGs). However, the exact time complexity of k-DSP remains mysterious, with large gaps between the fastest known algorithms and best conditional lower bounds. In this paper, we obtain faster algorithms for important cases of k-DSP, and present better conditional lower bounds for k-DSP and its variants. Previous work solved 2-DSP over weighted undirected graphs in O(n⁷) time, and weighted DAGs in O(mn) time. For the main result of this paper, we present optimal linear time algorithms for solving 2-DSP on weighted undirected graphs and DAGs. Our linear time algorithms are algebraic however, and so only solve the detection rather than search version of 2-DSP (we show how to solve the search version in O(mn) time, which is faster than the previous best runtime in weighted undirected graphs, but only matches the previous best runtime for DAGs). We also obtain a faster algorithm for k-Edge Disjoint Shortest Paths (k-EDSP) in DAGs, the variant of k-DSP where one seeks edge-disjoint instead of vertex-disjoint paths between sources and their corresponding targets. Algorithms for k-EDSP on DAGs from previous work take Ω(m^k) time. We show that k-EDSP can be solved over DAGs in O(mn^{k-1}) time, matching the fastest known runtime for solving k-DSP over DAGs. Previous work established conditional lower bounds for solving k-DSP and its variants via reductions from detecting cliques in graphs. Prior work implied that k-Clique can be reduced to 2k-DSP in DAGs and undirected graphs with O((kn)²) nodes. We improve this reduction, by showing how to reduce from k-Clique to k-DSP in DAGs and undirected graphs with O((kn)²) nodes (halving the number of paths needed in the reduced instance). A variant of k-DSP is the k-Disjoint Paths (k-DP) problem, where the solution paths no longer need to be shortest paths. Previous work reduced from k-Clique to p-DP in DAGs with O(kn) nodes, for p = k + k(k-1)/2. We improve this by showing a reduction from k-Clique to p-DP, for p = k + ⌊k²/4⌋. Under the k-Clique Hypothesis from fine-grained complexity, our results establish better conditional lower bounds for k-DSP for all k ≥ 4, and better conditional lower bounds for p-DP for all p ≤ 4031. Notably, our work gives the first nontrivial conditional lower bounds 4-DP in DAGs and 4-DSP in undirected graphs and DAGs. Before our work, nontrivial conditional lower bounds were only known for k-DP and k-DSP on such graphs when k ≥ 6. 
    more » « less
  2. ; ; (, ACM Transactions on Algorithms)
    null (Ed.)
    We consider node-weighted survivable network design (SNDP) in planar graphs and minor-closed families of graphs. The input consists of a node-weighted undirected graph G = ( V , E ) and integer connectivity requirements r ( uv ) for each unordered pair of nodes uv . The goal is to find a minimum weighted subgraph H of G such that H contains r ( uv ) disjoint paths between u and v for each node pair uv . Three versions of the problem are edge-connectivity SNDP (EC-SNDP), element-connectivity SNDP (Elem-SNDP), and vertex-connectivity SNDP (VC-SNDP), depending on whether the paths are required to be edge, element, or vertex disjoint, respectively. Our main result is an O ( k )-approximation algorithm for EC-SNDP and Elem-SNDP when the input graph is planar or more generally if it belongs to a proper minor-closed family of graphs; here, k = max  uv r ( uv ) is the maximum connectivity requirement. This improves upon the O ( k log  n )-approximation known for node-weighted EC-SNDP and Elem-SNDP in general graphs [31]. We also obtain an O (1) approximation for node-weighted VC-SNDP when the connectivity requirements are in {0, 1, 2}; for higher connectivity our result for Elem-SNDP can be used in a black-box fashion to obtain a logarithmic factor improvement over currently known general graph results. Our results are inspired by, and generalize, the work of Demaine, Hajiaghayi, and Klein [13], who obtained constant factor approximations for node-weighted Steiner tree and Steiner forest problems in planar graphs and proper minor-closed families of graphs via a primal-dual algorithm. 
    more » « less
  3. ; (, Contemporary mathematics - American Mathematical Society)
    In previous work [7], the authors constructed and studied a lift of the Galois correspondence to stable homotopy categories. In particular, if L/k is a finite Galois extension of fields with Galois group G, there is a functor c∗L/k : SHG → SHk from the G-equivariant stable homotopy category to the stable motivic homotopy category over k such that c∗L/k(G/H+) = Spec(LH)+. The main theorem of [7] says that when k is a real closed field and L = k[i], the restriction of c∗L/k to the η-complete subcategory is full and faithful. Here we “uncomplete” this theorem so that it applies to c∗L/k itself. Our main tools are Bachmann’s theorem on the (2,η)- periodic stable motivic homotopy category and an isomorphism range for the map πRS → πC2 S induced by C2-equivariant Betti realization. 
    more » « less
  4. ; (, American Journal of Mathematics)
    abstract: In the early 1940s, P. A. Smith showed that if a finite $$p$$-group $$G$$ acts on a finite dimensional complex $$X$$ that is mod $$p$$ acyclic, then its space of fixed points, $X^G$, will also be mod $$p$$ acyclic. In their recent study of the Balmer spectrum of equivariant stable homotopy theory, Balmer and Sanders were led to study a question that can be shown to be equivalent to the following: if a $$G$$-space $$X$$ is a equivariant homotopy retract of the $$p$$-localization of a based finite $$G$$-C.W. complex, given $H 
    more » « less
  5. ; ; ; (, Advances in Combinatorics)
    A _theta_ is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $$\mathcal{H}$$ of graphs, we say a graph $$G$$ is $$\mathcal{H}$$-_free_ if no induced subgraph of $$G$$ is isomorphic to a member of $$\mathcal{H}$$. We prove a conjecture of Sintiari and Trotignon, that there exists an absolute constant $$c$$ for which every (theta, triangle)-free graph $$G$$ has treewidth at most $$c\log (|V(G)|)$$. A construction by Sintiari and Trotignon shows that this bound is asymptotically best possible, and (theta, triangle)-free graphs comprise the first known hereditary class of graphs with arbitrarily large yet logarithmic treewidth.Our main result is in fact a generalization of the above conjecture, that treewidth is at most logarithmic in $|V(G)|$ for every graph $$G$$ excluding the so-called _three-path-configurations_ as well as a fixed complete graph. It follows that several NP-hard problems such as Stable Set, Vertex Cover, Dominating Set and $$k$$-Coloring (for fixed $$k$$) admit polynomial time algorithms in graphs excluding the three-path-configurations and a fixed complete graph. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email