Last Updated: May 7, 2018

A list of my publications can also be found at DBLP and Google Scholar. Some of them are available as preprint manuscripts at arXiv.

The symbol $\bigcirc$ indicates the corresponding author.

- Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, \(\bigcirc\)
__Duc A. Hoang__, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, and Takeshi Yamada.Linear-Time Algorithm for Sliding Tokens on Trees.Theoretical Computer Science 600, pp. 132–142 (2015).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 token problem is to determine whether there exists a sequence of independent sets which transforms \(I_b\) into \(I_r\) so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we thus study the problem restricted to trees, and give the following three results: (1) the decision problem is solvable in linear time; (2) for a yes-instance, we can find in quadratic time an actual sequence of independent sets between \(I_b\) and \(I_r\) whose length (i.e., the number of token-slides) is quadratic; and (3) there exists an infinite family of instances on paths for which any sequence requires quadratic length.

The symbol $\bigcirc$ indicates the speaker at the conference.

- Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, \(\bigcirc\)
__Duc A. Hoang__, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, and Takeshi Yamada.Polynomial-Time Algorithm for Sliding Tokens on Trees.In: Hee-Kap Ahn, and Chan-Su Shin (editors), Proceedings of the 25th International Symposium on Algorithms and Computation, ISAAC 2014, Jeonju, Korea, December 15-17, 2014. Lecture Notes in Computer Science 8889, pp. 389–400. Springer (2014).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 token problem is to determine whether there exists a sequence of independent sets which transforms \(I_b\) into \(I_r\) so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we show that the problem is solvable for trees in quadratic time. Our proof is constructive: for a yes-instance, we can find an actual sequence of independent sets between \(I_b\) and \(I_r\) whose length (i.e., the number of token-slides) is quadratic. We note that there exists an infinite family of instances on paths for which any sequence requires quadratic length.

- \(\bigcirc\) Eli Fox-Epstein,
__Duc A. Hoang__, Yota Otachi, and Ryuhei Uehara.Sliding Token on Bipartite Permutation Graphs.In: Khaled Elbassioni, and Kazuhisa Makino (editors), Proceedings of the 26th International Symposium on Algorithms and Computation, ISAAC 2015, Nagoya, Japan, December 9-11, 2015. Lecture Notes in Computer Science 9472, pp. 237–247. Springer (2015).Sliding Token is a natural reconfiguration problem in which vertices of independent sets are iteratively replaced by neighbors. We develop techniques that may be useful in answering the conjecture that Sliding Token is polynomial-time decidable on bipartite graphs. Along the way, we give efficient algorithms for Sliding Token on bipartite permutation and bipartite distance-hereditary graphs.

- \(\bigcirc\)
__Duc A. Hoang__, and Ryuhei Uehara.Sliding Tokens on a Cactus.In: Seok-Hee Hong (editor), Proceedings of the 27th International Symposium on Algorithms and Computation, ISAAC 2016, Sydney, Australia, December 12-14, 2016. Leibniz International Proceedings in Informatics 64, pp. 37:1–37:26. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik (2016).Given two independent sets \(I\) and \(J\) of a graph \(G\), imagine that a token (coin) is placed on each vertex in \(I\). Then, the Sliding Token problem asks if one could transforms \(I\) to \(J\) using a sequence of elementary steps, where each step requires sliding a token from one vertex to one of its neighbors, such that the resulting set of vertices where tokens are placed still remains independent. In this paper, we describe a polynomial-time algorithm for solving Sliding Token in case the graph \(G\) is a cactus. Our algorithm is designed based on two observations. First, all structures that forbid the existence of a sequence of token slidings between \(I\) and \(J\), if exist, can be found in polynomial time. A no-instance may be easily deduced using this characterization. Second, without such forbidden structures, a sequence of token slidings between \(I\) and \(J\) does exist.

- \(\bigcirc\)
__Duc A. Hoang__, Eli Fox-Epstein, and Ryuhei Uehara.Sliding Tokens on Block Graphs.In: Sheung-Hung Poon, Md. Saidur Rahman, and Hsu-Chun Yen (editors), Proceedings of the 11th International Conference and Workshops on Algorithms and Computation, WALCOM 2017, Hsinchu, Taiwan, March 29-31, 2017. Lecture Notes in Computer Science 10167, pp. 460–471. Springer (2017).Note: We thank Mariana Teatini Ribeiro and Vinícius dos Santos for pointing out a flaw in the proof of Proposition 6. So far, we have not found any way to fix this issue.

Let \(I\), \(J\) be two given independent sets of a graph \(G\). Imagine that the vertices of an independent set are viewed as tokens (coins). A token is allowed to move (or slide) from one vertex to one of its neighbors. The Sliding Token problem asks whether there exists a sequence of independent sets of \(G\) starting from \(I\) and ending with \(J\) such that each intermediate member of the sequence is obtained from the previous one by moving a token according to the allowed rule. In this paper, we claim that this problem is solvable in polynomial time when the input graph is a block graph—a graph whose blocks are cliques. Our algorithm is developed based on the characterization of a non-trivial structure that, in certain conditions, can be used to indicate a no-instance of the problem. Without such a structure, a sequence of token slidings between any two independent sets of the same cardinality exists.

__Duc A. Hoang__.The Independent Set Reconfiguration Problem on Some Restricted Graphs.Master's thesis. Japan Advanced Institute of Science and Technology (2015).__Duc A. Hoang__.Independent Set Reconfiguration and Related Problems for Some Restricted Graphs.PhD thesis. Japan Advanced Institute of Science and Technology (2018).Note: Coming Soon