HLHoang-Oanh Le

Hoang-Oanh Le

*This is an algorithmically generated author record based on publicly available information.

Hoang-Oanh Le has a total of 4 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    The parameterized complexity of Strong Conflict-Free Vertex-Connection Colorability

    by Carl Feghali, Hoang-Oanh Le, Van Bang Le

    This paper continues the study of a new variant of graph coloring with a connectivity constraint recently introduced by Hsieh et al. [COCOON 2024]. A path in a vertex-colored graph is called conflict-free if there is a color that appears exactly once on its vertices. A connected graph is said to be strongly conflict-free vertex-connection $k$-colorable if it admits a (proper) vertex $k$-coloring such that any two distinct vertices are connected by a conflict-free shortest path. Among others, we show that deciding, for a given graph $G$ and an integer $k$, whether $G$ is strongly conflict-free $k$-colorable is fixed-parameter tractable when parameterized by the vertex cover number. But under the standard complexity-theoretic assumption NP $\not\subseteq$ coNP/poly, deciding, for a given graph $G$, whether $G$ is strongly conflict-free $3$-colorable does not admit a polynomial kernel, even for bipartite graphs. This kernel lower bound is in stark contrast to the ordinal $k$-Coloring problem which is known to admit a polynomial kernel when parameterized by the vertex cover number.

  • Open Access

    The complexity of strong conflict-free vertex-connection $k$-colorability

    by Sun-Yuan Hsieh, Hoang-Oanh Le, Van Bang Le, Sheng-Lung Peng

    We study a new variant of graph coloring by adding a connectivity constraint. A path in a vertex-colored graph is called conflict-free if there is a color that appears exactly once on its vertices. A connected graph $G$ is said to be strongly conflict-free vertex-connection $k$-colorable if $G$ admits a vertex $k$-coloring such that any two distinct vertices of $G$ are connected by a conflict-free $shortest$ path. Among others, we show that deciding whether a given graph is strongly conflict-free vertex-connection $3$-colorable is NP-complete even when restricted to $3$-colorable graphs with diameter $3$, radius $2$ and domination number $3$, and, assuming the Exponential Time Hypothesis (ETH), cannot be solved in $2^{o(n)}$ time on such restricted input graphs with $n$ vertices. This hardness result is quite strong when compared to the ordinary $3$-COLORING problem: it is known that $3$-COLORING is solvable in polynomial time in graphs with bounded domination number, and assuming ETH, cannot be solved in $2^{o(\sqrt{n})}$ time in $n$-vertex graphs with diameter $3$ and radius $2$. On the positive side, we point out that a strong conflict-free vertex-connection coloring with minimum color number of a given split graph or a co-bipartite graph can be computed in polynomial time.

  • Open Access

    Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs

    by Hoang-Oanh Le, Van Bang Le

    The well-known Cluster Vertex Deletion problem (cluster-vd) asks for a given graph G and an integer k whether it is possible to delete a set S of at most k vertices of G such that the resulting graph $$G-S$$ G - S is a cluster graph (a disjoint union of cliques). We give a complete characterization of graphs H for which cluster-vd on H-free graphs is polynomially solvable and for which it is $$\textsf{NP}$$ NP -complete. Moreover, in the $$\textsf{NP}$$ NP -completeness cases, cluster-vd cannot be solved in sub-exponential time in the vertex number of the H-free input graphs unless the Exponential-Time Hypothesis fails. We also consider the connected variant of cluster-vd, the Connected Cluster Vertex Deletion problem (connected cluster-vd), in which the set S has to induce a connected subgraph of G. It turns out that connected cluster-vd admits the same complexity dichotomy for H-free graphs. Our results enlarge a list of rare dichotomy theorems for well-studied problems on H-free graphs.


  • On the d-Claw Vertex Deletion Problem

    by Sun-Yuan Hsieh, Hoang-Oanh Le, Van Bang Le, Sheng-Lung Peng