Source author record

Sheng-Lung Peng

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

ResearcherUnclaimed source record

Discrete Mathematics math.CO Data Structures and Algorithms

Catalog footprint

Research overview

3works

3topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On the $d$ -Claw Vertex Deletion Problem

Let $d$ -claw (or $d$ -star) stand for $K_{1,d}$ , the complete bipartite graph with 1 and $d\ge 1$ vertices on each part. The $d$ -claw vertex deletion problem, $d$ -CLAW-VD, asks for a given graph $G$ and an integer $k$ if one can delete at most $k$ vertices from $G$ such that the resulting graph has no $d$ -claw as an induced subgraph. Thus, 1-CLAW-VD and 2-CLAW-VD are just the famous VERTEX COVER problem and the CLUSTER VERTEX DELETION problem, respectively. In this paper, we strengthen a hardness result in [M. Yannakakis, Node-Deletion Problems on Bipartite Graphs, SIAM J. Comput. (1981)], by showing that CLUSTER VERTEX DELETION remains NP-complete when restricted to bipartite graphs of maximum degree 3. Moreover, for every $d\ge 3$ , we show that $d$ -CLAW-VD is NP-complete even when restricted to bipartite graphs of maximum degree $d$ . These hardness results are optimal with respect to degree constraint. By extending the hardness result in [F. Bonomo-Braberman et al., Linear-Time Algorithms for Eliminating Claws in Graphs, COCOON 2020], we show that, for every $d\ge 3$ , $d$ -CLAW-VD is NP-complete even when restricted to split graphs without $(d+1)$ -claws, and split graphs of diameter 2. On the positive side, we prove that $d$ -CLAW-VD is polynomially solvable on what we call $d$ -block graphs, a class properly contains all block graphs. This result extends the polynomial-time algorithm in [Y. Cao et al., Vertex deletion problems on chordal graphs, Theor. Comput. Sci. (2018)] for 2-CLAW-VD on block graphs to $d$ -CLAW-VD for all $d\ge 2$ and improves the polynomial-time algorithm proposed by F. Bonomo-Brabeman et al. for (unweighted) 3-CLAW-VD on block graphs to 3-block graphs.

preprint2016arXiv

Good characterizations and linear time recognition for 2-probe block graphs

Block graphs are graphs in which every block (biconnected component) is a clique. A graph $G=(V,E)$ is said to be an (unpartitioned) $k$ -probe block graph if there exist $k$ independent sets $N_i\subseteq V$ , $1\le i\le k$ , such that the graph $G'$ obtained from $G$ by adding certain edges between vertices inside the sets $N_i$ , $1\le i\le k$ , is a block graph; if the independent sets $N_i$ are given, $G$ is called a partitioned $k$ -probe block graph. In this paper we give good characterizations for $2$ -probe block graphs, in both unpartitioned and partitioned cases. As an algorithmic implication, partitioned and unpartitioned probe block graphs can be recognized in linear time, improving a recognition algorithm of cubic time complexity previously obtained by Chang et al. [Block-graph width, Theoretical Computer Science 412 (2011), 2496--2502].

preprint2016arXiv

On the complete width and edge clique cover problems

A complete graph is the graph in which every two vertices are adjacent. For a graph $G=(V,E)$ , the complete width of $G$ is the minimum $k$ such that there exist $k$ independent sets $\mathtt{N}_i\subseteq V$ , $1\le i\le k$ , such that the graph $G'$ obtained from $G$ by adding some new edges between certain vertices inside the sets $\mathtt{N}_i$ , $1\le i\le k$ , is a complete graph. The complete width problem is to decide whether the complete width of a given graph is at most $k$ or not. In this paper we study the complete width problem. We show that the complete width problem is NP-complete on $3K_2$ -free bipartite graphs and polynomially solvable on $2K_2$ -free bipartite graphs and on $(2K_2,C_4)$ -free graphs. As a by-product, we obtain the following new results: the edge clique cover problem is NP-complete on $\overline{3K_2}$ -free co-bipartite graphs and polynomially solvable on $C_4$ -free co-bipartite graphs and on $(2K_2, C_4)$ -free graphs. We also give a characterization for $k$ -probe complete graphs which implies that the complete width problem admits a kernel of at most $2^k$ vertices. This provides another proof for the known fact that the edge clique cover problem admits a kernel of at most $2^k$ vertices. Finally we determine all graphs of small complete width $k\le 3$ .

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.

Sheng-Lung Peng

Research overview

Is this your work?

3 publications

On the $d$ -Claw Vertex Deletion Problem

Good characterizations and linear time recognition for 2-probe block graphs

On the complete width and edge clique cover problems

See the researcher in context

Building this map preview

Sheng-Lung Peng

Research overview

Is this your work?

3 publications

On the ddd-Claw Vertex Deletion Problem

Good characterizations and linear time recognition for 2-probe block graphs

On the complete width and edge clique cover problems

See the researcher in context

Building this map preview

On the $d$ -Claw Vertex Deletion Problem