Source author record

Katherine Edwards

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Data Structures and Algorithms Computational Complexity math.MG math.PR

Catalog footprint

Research overview

10works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Fast approximation algorithms for $p$ -centres in large $δ$ -hyperbolic graphs

We provide a quasilinear time algorithm for the $p$ -center problem with an additive error less than or equal to 3 times the input graph's hyperbolic constant. Specifically, for the graph $G=(V,E)$ with $n$ vertices, $m$ edges and hyperbolic constant $δ$ , we construct an algorithm for $p$ -centers in time $O(p(δ+1)(n+m)\log(n))$ with radius not exceeding $r_p + δ$ when $p \leq 2$ and $r_p + 3δ$ when $p \geq 3$ , where $r_p$ are the optimal radii. Prior work identified $p$ -centers with accuracy $r_p+δ$ but with time complexity $O((n^3\log n + n^2m)\log(diam(G)))$ which is impractical for large graphs.

preprint2016arXiv

Half-integral linkages in highly connected directed graphs

We study the half-integral $k$ -Directed Disjoint Paths Problem ( $\tfrac12$ kDDPP) in highly strongly connected digraphs. The integral kDDPP is NP-complete even when restricted to instances where $k=2$ , and the input graph is $L$ -strongly connected, for any $L\geq 1$ . We show that when the integrality condition is relaxed to allow each vertex to be used in two paths, the problem becomes efficiently solvable in highly connected digraphs (even with $k$ as part of the input). Specifically, we show that there is an absolute constant $c$ such that for each $k\geq 2$ there exists $L(k)$ such that $\tfrac12$ kDDPP is solvable in time $O(|V(G)|^c)$ for a $L(k)$ -strongly connected directed graph $G$ . As the function $L(k)$ grows rather quickly, we also show that $\tfrac12$ kDDPP is solvable in time $O(|V(G)|^{f(k)})$ in $(36k^3+2k)$ -strongly connected directed graphs. We also show that for each $ε<1$ deciding half-integral feasibility of kDDPP instances is NP-complete when $k$ is given as part of the input, even when restricted to graphs with strong connectivity $εk$ .

preprint2016arXiv

On paths, stars and wyes in trees

We further the study of local profiles of trees. Bubeck and Linial showed that the set of 5-profiles contains a certain polytope, namely the convex hull of d-millipedes, and they proved that the segment [0-millipede, 1-millipede] corresponds to a face of the set of 5-profiles. Our main result shows that the segment [1-millipede, 2-millipede] also corresponds to a face. Surprisingly we also show that for d > 3 the segment [d-millipede, (d+1)-millipede] is not a face of the set of 5-profiles. We do so by exhibiting new trees which are generalized millipedes with intriguing patterns for their degree sequence. The plot thickens, and the set of 5-profiles remains a mysterious convex set.

preprint2015arXiv

Concentration of the number of solutions of random planted CSPs and Goldreich's one-way candidates

This paper shows that the logarithm of the number of solutions of a random planted $k$ -SAT formula concentrates around a deterministic $n$ -independent threshold. Specifically, if $F^*_{k}(α,n)$ is a random $k$ -SAT formula on $n$ variables, with clause density $α$ and with a uniformly drawn planted solution, there exists a function $ϕ_k(\cdot)$ such that, besides for some $α$ in a set of Lesbegue measure zero, we have $\frac{1}{n}\log Z(F^*_{k}(α,n)) \to ϕ_k(α)$ in probability, where $Z(F)$ is the number of solutions of the formula $F$ . This settles a problem left open in Abbe-Montanari RANDOM 2013, where the concentration is obtained only for the expected logarithm over the clause distribution. The result is also extended to a more general class of random planted CSPs; in particular, it is shown that the number of pre-images for the Goldreich one-way function model concentrates for some choices of the predicates.

preprint2014arXiv

A superlocal version of Reed's Conjecture

Reed's well-known $ω$ , $Δ$ , $χ$ conjecture proposes that every graph satisfies $χ\leq \lceil \frac 12(Δ+1+ω)\rceil$ . The second author formulated a {\em local strengthening} of this conjecture that considers a bound supplied by the neighbourhood of a single vertex. Following the idea that the chromatic number cannot be greatly affected by any particular stable set of vertices, we propose a further strengthening that considers a bound supplied by the neighbourhoods of two adjacent vertices. We provide some fundamental evidence in support, namely that the stronger bound holds in the fractional relaxation and holds for both quasi-line graphs and graphs with stability number two. We also conjecture that in the fractional version, we can push the locality even further.

preprint2014arXiv

Disjoint dijoins

A dijoin in a digraph is a set of edges meeting every directed cut. D. R. Woodall conjectured in 1976 that if G is a digraph, and every directed cut of G has at least k edges, then there are k pairwise disjoint dijoins. This remains open, but a capacitated version is known to be false. In particular, A. Schrijver gave a digraph G and a subset S of its edge-set, such that every directed cut contains at least two edges in S, and yet there do not exist two disjoint dijoins included in S. In Schrijver's example, G is planar, and the subdigraph formed by the edges in S consists of three disjoint paths. We conjecture that when k = 2, the disconnectedness of S is crucial: more precisely, that if G is a digraph, and S is a subset of the edges of G that forms a connected subdigraph (as an undirected graph), and every directed cut of G contains at least two edges in S, then we can partition S into two dijoins. We prove this in two special cases: when G is planar, and when the subdigraph formed by the edges in S is a subdivision of a caterpillar.

preprint2013arXiv

Bounding the fractional chromatic number of $K_Δ$ -free graphs

King, Lu, and Peng recently proved that for $Δ\geq 4$ , any $K_Δ$ -free graph with maximum degree $Δ$ has fractional chromatic number at most $Δ-\tfrac{2}{67}$ unless it is isomorphic to $C_5\boxtimes K_2$ or $C_8^2$ . Using a different approach we give improved bounds for $Δ\geq 6$ and pose several related conjectures. Our proof relies on a weighted local generalization of the fractional relaxation of Reed's $ω$ , $Δ$ , $χ$ conjecture.

preprint2012arXiv

A note on hitting maximum and maximal cliques with a stable set

It was recently proved that any graph satisfying $ω> \frac 23(Δ+1)$ contains a stable set hitting every maximum clique. In this note we prove that the same is true for graphs satisfying $ω\geq \frac 23(Δ+1)$ unless the graph is the strong product of $K_{ω/2}$ and an odd hole. We also provide a counterexample to a recent conjecture on the existence of a stable set hitting every sufficiently large maximal clique.

preprint2012arXiv

Edge-colouring eight-regular planar graphs

It was conjectured by the third author in about 1973 that every $d$ -regular planar graph (possibly with parallel edges) can be $d$ -edge-coloured, provided that for every odd set $X$ of vertices, there are at least $d$ edges between $X$ and its complement. For $d = 3$ this is the four-colour theorem, and the conjecture has been proved for all $d\le 7$ , by various authors. Here we prove it for $d = 8$ .

preprint2012arXiv

Edge-colouring seven-regular planar graphs

A conjecture due to the fourth author states that every $d$ -regular planar multigraph can be $d$ -edge-coloured, provided that for every odd set $X$ of vertices, there are at least $d$ edges between $X$ and its complement. For $d = 3$ this is the four-colour theorem, and the conjecture has been proved for all $d\le 8$ , by various authors. In particular, two of us proved it when $d=7$ ; and then three of us proved it when $d=8$ . The methods used for the latter give a proof in the $d=7$ case that is simpler than the original, and we present it here.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Katherine Edwards

Research overview

Is this your work?

10 publications

Fast approximation algorithms for $p$ -centres in large $δ$ -hyperbolic graphs

Half-integral linkages in highly connected directed graphs

On paths, stars and wyes in trees

Concentration of the number of solutions of random planted CSPs and Goldreich's one-way candidates

A superlocal version of Reed's Conjecture

Disjoint dijoins

Bounding the fractional chromatic number of $K_Δ$ -free graphs

A note on hitting maximum and maximal cliques with a stable set

Edge-colouring eight-regular planar graphs

Edge-colouring seven-regular planar graphs

See the researcher in context

Building this map preview

Katherine Edwards

Research overview

Is this your work?

10 publications

Fast approximation algorithms for ppp-centres in large δδδ-hyperbolic graphs

Half-integral linkages in highly connected directed graphs

On paths, stars and wyes in trees

Concentration of the number of solutions of random planted CSPs and Goldreich's one-way candidates

A superlocal version of Reed's Conjecture

Disjoint dijoins

Bounding the fractional chromatic number of KΔK_ΔKΔ​-free graphs

A note on hitting maximum and maximal cliques with a stable set

Edge-colouring eight-regular planar graphs

Edge-colouring seven-regular planar graphs

See the researcher in context

Building this map preview

Fast approximation algorithms for $p$ -centres in large $δ$ -hyperbolic graphs

Bounding the fractional chromatic number of $K_Δ$ -free graphs