Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951334 | Journal of Discrete Algorithms | 2016 | 6 Pages |
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
R. Sritharan,