9 papers · 1 filter
Max Cut with Small-Dimensional SDP Solutions
Hsien-Chih Chang, Suprovat Ghoshal, Euiwoong Lee
We study the Max-Cut semidefinite programming (SDP) relaxation in the regime where a near-optimal solution admits a low-dimensional realization. While the Goemans--Williamson hyper…
DAG Covers for Structured Graphs: The Steiner Point Effect
Sujoy Bhore, Hsien-Chih Chang, Jonathan Conroy +4
Given a weighted digraph , a -DAG cover is a collection of dominating DAGs such that all distances are approximately preserved: for every pair $(u,v…
Single-Criteria Metric -Dominating Set Problem via Minor-Preserving Support
Reilly Browne, Hsien-Chih Chang
Given an unweighted graph , the *minimum -dominating set problem* asks for the smallest-cardinality subset such that every vertex in is within radius of some vert…
Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3
We give the first truly subquadratic time algorithm, with running time, for computing the diameter of an -vertex unit-disk graph, resolving a central open prob…
Cutting Planarians: Planar Emulators for String Graphs
Hsien-Chih Chang, Jonathan Conroy, Zihan Tan +1
In this paper we construct distance sketches for intersection graphs of arbitrary path-connected regions in the plane (known as the string graphs) in the constant and $1+\varepsilo…
Distance Approximating Minors for Planar and Minor-Free Graphs
Hsien-Chih Chang, Jonathan Conroy
Given an edge-weighted graph and a subset of vertices called terminals, an -distance-approximating minor (-DAM) of is a graph minor of that contains all t…
Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
Hsien-Chih Chang, Jonathan Conroy, Hung Le +2
A -stretch tree cover of an edge-weighted -vertex graph is a collection of trees, where every pair of vertices has a -stretch path in one o…
Embedding Planar Graphs into Graphs of Treewidth
Hsien-Chih Chang, Vincent Cohen-Addad, Jonathan Conroy +3
Cohen-Addad, Le, Pilipczuk, and Pilipczuk [CLPP23] recently constructed a stochastic embedding with expected distortion of -vertex planar graphs (with polynomial…
Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs
Hsien-Chih Chang, Jie Gao, Hung Le
Finding the diameter of a graph in general cannot be done in truly subquadratic assuming the Strong Exponential Time Hypothesis (SETH), even when the underlying graph is unweighted…