Publications

Updated: July 16, 2019

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

In Preparation

  1. Duc A. Hoang, Akira Suzuki, and Tsuyoshi Yagita.
    Reconfiguring \(k\)-Path Vertex Covers.

    Abstract PDF

    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 \(k\)-Path Vertex Cover Reconfiguration (\(k\)-PVCR) problem asks if one can transform one \(k\)-path vertex cover into another via a sequence of \(k\)-path vertex covers where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. We investigate the computational complexity of \(k\)-PVCR from the viewpoint of graph classes under the well-known reconfiguration rules: \(\mathsf{TS}\), \(\mathsf{TJ}\), and \(\mathsf{TAR}\). The problem for \(k=2\), known as the Vertex Cover Reconfiguration (VCR) problem, has been well-studied in the literature. We show that certain known hardness results for VCR on different graph classes including planar graphs, bounded bandwidth graphs, chordal graphs, and bipartite graphs, can be extended for \(k\)-PVCR. In particular, we prove a complexity dichotomy for \(k\)-PVCR on general graphs: on those whose maximum degree is 3 (and even planar), the problem is \(\mathtt{PSPACE}\)-complete, while on those whose maximum degree is 2 (i.e., paths and cycles), the problem can be solved in polynomial time. Additionally, we also design polynomial-time algorithms for \(k\)-PVCR on trees under \(\mathsf{TJ}\) and \(\mathsf{TAR}\). Moreover, on paths, cycles, and trees, we describe how one can construct a reconfiguration sequence between two given \(k\)-path vertex covers in a yes-instance. In particular, on paths, our constructed reconfiguration sequence is shortest.

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.

Refereed International Conference

The symbol $\bigcirc$ indicates the speaker at the conference. See my list of events for extra information and materials including slides, photos, notes, and so on.

  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 Slides

    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 Slides

    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 Slides

    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 Proposition 6. See this page for more detail.

    Abstract DOI HDL Slides

    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.

  5. Duc A. Hoang, Amanj Khorramian, and \(\bigcirc\) Ryuhei Uehara.
    Shortest Reconfiguration Sequence for Sliding Tokens on Spiders.
    In: Pinar Heggernes (editor), Proceedings of the 11th International Conference on Algorithms and Complexity, CIAC 2019, Rome, Italy, May 27-29, 2019. Lecture Notes in Computer Science 11485, pp. 262–273. Springer (2019).

    Abstract DOI ArXiv Slides 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).

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

    HDL Slides