Publications
Updated on May 2, 2017


A list of my publications can also be found at DBLP and Google Scholar.

Preprint

  1. Duc A. Hoang, and Ryuhei Uehara.
    Polynomial-Time Algorithms for Sliding Tokens on Cactus Graphs and Block Graphs.

    Abstract ArXiv

    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\)via a sequence of elementary steps, where each step requires sliding a token from one vertex to one of its neighbors so that the resulting set of vertices where tokens are placed remains independent. This problem is PSPACE-complete even for planar graphs of maximum degree \(3\)and bounded-treewidth. In this paper, we show that Sliding Token can be solved efficiently for cactus graphs and block graphs, and give upper bounds on the length of a transformation sequence between any two independent sets of these graph classes. Our algorithms are designed based on two main 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 sufficient condition for determining no-instances can be easily derived using this characterization. Second, without such forbidden structures, a sequence of token slidings between \(I\)and \(J\)does exist. In this case, one can indeed transform \(I\)to \(J\) (and vice versa) using a polynomial number of token-slides.

Journal

  1. Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, 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).

    Abstract DOI ArXiv HDL

    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.

International Conference

  1. Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, 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).

    Abstract DOI ArXiv HDL

    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.

  2. 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).

    Abstract DOI HDL

    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.

  3. 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).

    Abstract DOI

    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.

  4. 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).

    Abstract DOI

    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.

Thesis/Dissertation

  1. Duc A. Hoang.
    The Independent Set Reconfiguration Problem on Some Restricted Graphs.
    Master's thesis. Japan Advanced Institute of Science and Technology (2015).

    HDL