BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Katherine Edwards

Katherine Edwards appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.CODiscrete MathematicsData Structures and AlgorithmsComputational Complexitymath.MGmath.PR

Catalog footprint

What is connected

10works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

10 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access