Arrow Research search

Author name cluster

Hsueh-I Lu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers
2 author rows

Possible papers

7

I&C Journal 2026 Journal Article

Improved algorithms for perfect graphs and odd holes

  • Yung-Chung Chiu
  • Hsueh-I Lu

We present the following three improved complexity bounds for an n-vertex simple undirected unweighted graph G: • Testing whether G is perfect takes O(n 7) time (previously O(n 8) [1]). • Reporting an odd hole of G or certifying that G has none takes O(n 7) time (previously O(n 9) [1]). • Reporting a shortest odd hole of G or certifying that G has none takes O(n 13) time (previously O(n 14) [2]).

Details DOI

I&C Journal 2024 Journal Article

Blazing a trail via matrix multiplications: A faster algorithm for non-shortest induced paths

  • Yung-Chung Chiu
  • Hsueh-I Lu

For vertices u and v of an n-vertex graph G, a uv-trail of G is an induced uv-path of G that is not a shortest uv-path of G. Berger, Seymour, and Spirkl [Discrete Mathematics 2021] gave the previously only known polynomial-time algorithm, running in O ( n 18 ) time, to either output a uv-trail of G or ensure that G admits no uv-trail. We reduce the complexity to the time required to perform a poly-logarithmic number of multiplications of n 2 × n 2 Boolean matrices, leading to a largely improved O ( n 4. 75 ) -time algorithm. Our result improves the previous O ( n 21 ) -time algorithm by Cook, Horsfield, Preissmann, Robin, Seymour, Sintiari, Trotignon, and Vušković [Journal of Combinatorial Theory, Series B, 2024] for recognizing graphs with all holes the same length, and reduces the running time to O ( n 7. 75 ).

Details DOI

STOC Conference 2020 Conference Paper

Three-in-a-tree in near linear time

  • Kai-Yuan Lai 0001
  • Hsueh-I Lu
  • Mikkel Thorup

The three-in-a-tree problem is to determine if a simple undirected graph contains an induced subgraph which is a tree connecting three given vertices. Based on a beautiful characterization that is proved in more than twenty pages, Chudnovsky and Seymour [ Combinatorica 2010] gave the previously only known polynomial-time algorithm, running in O ( mn 2 ) time, to solve the three-in-a-tree problem on an n -vertex m -edge graph. Their three-in-a-tree algorithm has become a critical subroutine in several state-of-the-art graph recognition and detection algorithms.

Details

SODA Conference 2012 Conference Paper

A faster algorithm to recognize even-hole-free graphs

  • Hsien-Chih Chang
  • Hsueh-I Lu

We study the problem of determining whether an n -node m -edge graph has an even hole, i. e. , an induced simple cycle consisting of an even number of nodes. Conforti, Cornuéjols, Kapoor, and Vušković gave the first polynomial-time algorithm for the problem, which runs in O ( n 40 ) time. Later, Chudnovsky, Kawarabayashi, and Seymour reduced the running time to O ( n 31 ). The best previously known algorithm for the problem, due to da Silva and Vušković, runs in O ( n 19 ) time. In this paper, we solve the problem in time O ( n 11 ).

Details
v2026.09.13