Source author record

Duc A. Hoang

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics Computational Complexity

Catalog footprint

Research overview

2works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Reconfiguring k-path vertex covers

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 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 \textsc{ $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 \textsc{Vertex Cover Reconfiguration (VCR)} problem, has been well-studied in the literature. We show that certain known hardness results for \textsc{VCR} on different graph classes including planar graphs, bounded bandwidth graphs, chordal graphs, and bipartite graphs, can be extended for \textsc{ $k$ -PVCR}. In particular, we prove a complexity dichotomy for \textsc{ $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 \textsc{ $k$ -PVCR} on trees under each of $\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.

preprint2014arXiv

Linear-Time Algorithm for Sliding Tokens on Trees

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.