Article ID Journal Published Year Pages File Type
4951334 Journal of Discrete Algorithms 2016 6 Pages PDF
Abstract
The issue of determining the complexity of modification problems for chordal bipartite graphs has been raised multiple times in the literature. We show that the completion and deletion problems for chordal bipartite graphs are NP-hard. The corresponding problems for weakly chordal graphs are already known to be hard. As a byproduct, we obtain results on modification problems for a variety of related classes of graphs and also simplify the arguments for the class of weakly chordal graphs.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,