12 papers
Charting the Diameter Computation Landscape on Intersection Graphs in the Plane
Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3
Computing the diameter of the intersection graphs of objects is a basic problem in computational geometry. Previous works showed that the complexity of computing the diameter mainl…
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…
Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3
Recent research on computing the diameter of geometric intersection graphs has made significant strides, primarily focusing on the 2D case where truly subquadratic-time algorithms…
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…
Optimal Euclidean Tree Covers
Hsien-Chih Chang, Jonathan Conroy, Hung Le +3
A of a metric space is a collection of trees, where every pair of points has a -stretch path in one of the trees. The…
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…