Publications

Updated: June 22, 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.

Preprint

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

    Note: The algorithm for block graphs in this manuscript contains some flaws. More precisely, Proposition 20 is not correct. Therefore, we withdraw this manuscript.

    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 \(\mathsf{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.

  2. Duc A. Hoang, Amanj Khorramian, and Ryuhei Uehara.
    Shortest Reconfiguration Sequence for Sliding Tokens on Spiders.

    Abstract ArXiv PDF

    Suppose that two independent sets \(I\) and \(J\) of a graph with \(\vert I \vert = \vert J \vert\) are given, and a token is placed on each vertex in \(I\). The Sliding Token problem is to determine whether there exists a sequence of independent sets which transforms \(I\) into \(J\) so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. It is one of the representative reconfiguration problems that attract the attention from the viewpoint of theoretical computer science. For a yes-instance of a reconfiguration problem, finding a shortest reconfiguration sequence has a different aspect. In general, even if it is polynomial time solvable to decide whether two instances are reconfigured with each other, it can be \(\mathsf{NP}\)-hard to find a shortest sequence between them. In this paper, we show that the problem for finding a shortest sequence between two independent sets is polynomial time solvable for spiders (i.e., trees having exactly one vertex of degree at least three).

Journal

The symbol $\bigcirc$ indicates the corresponding author.

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

    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

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

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

    Abstract DOI ArXiv HDL Slide

    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. \(\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).

    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. \(\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).

    Abstract DOI HDL Slide

    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. \(\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 Fernandes 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.

    Abstract DOI Slide

    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

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

    Slide