Duc A. Hoang

activity

20142026

most citedOn Reconfiguration Graphs of Independent Sets under Token Sliding

6 citations · 17 across the 13 of their papers we have counts for

collaborators

17 papers

cs.DS2026

Kempe Reachability with $k \geq 3$ Colors Is $PSPACE$ -Complete on Claw-Free Graphs

Duc A. Hoang

A \emph{proper vertex coloring} assigns colors to vertices so that adjacent vertices have distinct colors. A \emph{Kempe change} in a proper vertex coloring exchanges two colors on…

cs.DS2026

A Polynomial-Time Algorithm for $k$ -Path Vertex Cover Reconfiguration on Trees under Token Sliding

Duc A. Hoang

A $k$ -path vertex cover ( $k$ -PVC) of a graph is a set of vertices meeting every path on $k$ vertices. In Token Sliding, one token occupies each vertex of a cover; a move slides one…

math.CO2026

Token-sliding realizability for complements, Cartesian-products, and grid graph families

Duc A. Hoang

For an integer $k \geq 0$ and a graph $G$ , the \emph{token-sliding reconfiguration graph $TS_{k} (G)$ } has the independent $k$ -sets of $G$ as vertices. Two vertices are adjacen…

math.CO2026

On Realizing Reconfiguration Graphs of Cliques

Duc A. Hoang

For a graph $H$ and an integer $k \geq 1$ , the \emph{Token Sliding reconfiguration graph} $TS_{k} (H)$ and the \emph{Token Jumping reconfiguration graph} $TJ_{k} (H)$ hav…

math.CO2025

A Note on Reconfiguration Graphs of Cliques

Quan N. Lam, Huu An Phan, Duc A. Hoang

In a reconfiguration setting, each clique of a graph $G$ is viewed as a set of tokens placed on vertices of $G$ such that no vertex has more than one token and any two tokens are a…

cs.CL2025

FAID: Fine-Grained AI-Generated Text Detection Using Multi-Task Auxiliary and Multi-Level Contrastive Learning

Minh Ngoc Ta, Dong Cao Van, Duc-Anh Hoang +6

The growing collaboration between humans and AI models in generative tasks has introduced new challenges in distinguishing between human-written, LLM-generated, and human-LLM colla…

cs.DS2024

Directed Token Sliding

Niranka Banerjee, Christian Engels, Duc A. Hoang

Reconfiguration problems involve determining whether two given configurations can be transformed into each other under specific rules. The Token Sliding problem asks whether, given…

cs.DS2024

Distance Recoloring

Niranka Banerjee, Christian Engels, Duc A. Hoang

Reconfiguration problems ask whether one feasible solution can be transformed into another by a sequence of local moves while maintaining feasibility throughout. For integers $d \g…

cs.DS2023

The Complexity of Distance- $r$ Dominating Set Reconfiguration

Niranka Banerjee, Duc A. Hoang

For a fixed integer $r \geq 1$ , a distance- $r$ dominating set (D $r$ DS) of a graph $G = (V, E)$ is a vertex subset $D \subseteq V$ such that every vertex in $V$ is within distance $…

math.CO2023★ 1 cited

A Note On Acyclic Token Sliding Reconfiguration Graphs of Independent Sets

David Avis, Duc A. Hoang

We continue the study of token sliding reconfiguration graphs of independent sets initiated by the authors in an earlier paper (arXiv:2203.16861). Two of the topics in that paper w…

cs.DS2022★ 1 cited

On the Complexity of Distance- $d$ Independent Set Reconfiguration

Duc A. Hoang

For a fixed positive integer $d \geq 2$ , a distance- $d$ independent set (D $d$ IS) of a graph is a vertex subset whose distance between any two members is at least $d$ . Imagine that…

math.CO2022★ 6 cited

On Reconfiguration Graphs of Independent Sets under Token Sliding

David Avis, Duc A. Hoang

An independent set of a graph $G$ is a vertex subset $I$ such that there is no edge joining any two vertices in $I$ . Imagine that a token is placed on each vertex of an independent…

cs.DS2022★ 1 cited

TS-Reconfiguration of $k$ -Path Vertex Covers in Caterpillars for $k \geq 4$

Duc A. Hoang

A $k$ -path vertex cover ( $k$ -PVC) of a graph $G$ is a vertex subset $I$ such that each path on $k$ vertices in $G$ contains at least one member of $I$ . Imagine that a token is plac…

cs.DS2019

Reconfiguring k-path vertex covers

Duc A. Hoang, Akira Suzuki, Tsuyoshi Yagita

A vertex subset $I$ of a graph $G$ is called a $k$ -path vertex cover if every path on $k$ vertices in $G$ contains at least one vertex from $I$ . The \textsc{ $k$ -Path Vertex Cover R…

cs.DS2018★ 4 cited

Shortest Reconfiguration Sequence for Sliding Tokens on Spiders

Duc A. Hoang, Amanj Khorramian, Ryuhei Uehara

Suppose that two independent sets $I$ and $J$ of a graph with $∣ I ∣ = ∣ J ∣$ are given, and a token is placed on each vertex in $I$ . The Sliding Token problem is t…

cs.DM2017★ 3 cited

Polynomial-Time Algorithms for Sliding Tokens on Cactus Graphs and Block Graphs

Duc A. Hoang, Ryuhei Uehara

Given two independent sets $I, J$ of a graph $G$ , and imagine that a token (coin) is placed at each vertex of $I$ . The Sliding Token problem asks if one could transform $I$ to $J$ …

cs.DM2014★ 1 cited

Linear-Time Algorithm for Sliding Tokens on Trees

Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein +6

Suppose that we are given two independent sets $I_{b}$ and $I_{r}$ of a graph such that $∣ I_{b} ∣ = ∣ I_{r} ∣$ , and imagine that a token is placed on each vertex in $I_{b}$ . Then, the sliding tok…

Kempe Reachability with k≥3 Colors Is PSPACE-Complete on Claw-Free Graphs

A Polynomial-Time Algorithm for k-Path Vertex Cover Reconfiguration on Trees under Token Sliding

Token-sliding realizability for complements, Cartesian-products, and grid graph families

On Realizing Reconfiguration Graphs of Cliques

A Note on Reconfiguration Graphs of Cliques

FAID: Fine-Grained AI-Generated Text Detection Using Multi-Task Auxiliary and Multi-Level Contrastive Learning

Directed Token Sliding

Distance Recoloring

The Complexity of Distance-r Dominating Set Reconfiguration

A Note On Acyclic Token Sliding Reconfiguration Graphs of Independent Sets

On the Complexity of Distance-d Independent Set Reconfiguration

On Reconfiguration Graphs of Independent Sets under Token Sliding

TS-Reconfiguration of k-Path Vertex Covers in Caterpillars for k≥4

Reconfiguring k-path vertex covers

Shortest Reconfiguration Sequence for Sliding Tokens on Spiders

Polynomial-Time Algorithms for Sliding Tokens on Cactus Graphs and Block Graphs

Linear-Time Algorithm for Sliding Tokens on Trees

Kempe Reachability with $k \geq 3$ Colors Is $PSPACE$ -Complete on Claw-Free Graphs

A Polynomial-Time Algorithm for $k$ -Path Vertex Cover Reconfiguration on Trees under Token Sliding

The Complexity of Distance- $r$ Dominating Set Reconfiguration

On the Complexity of Distance- $d$ Independent Set Reconfiguration

TS-Reconfiguration of $k$ -Path Vertex Covers in Caterpillars for $k \geq 4$