The Library
Maximum regular induced subgraphs in -free graphs
Tools
Lozin, Vadim V. and Mosca, Raffaele (2012) Maximum regular induced subgraphs in -free graphs. Theoretical Computer Science, Vol. 460 . pp. 26-33. doi:10.1016/j.tcs.2012.06.014 ISSN 03043975.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.tcs.2012.06.014
Abstract
Finding maximum regular induced subgraphs is a family of algorithmic graph problems containing several important representatives such as maximum independent set, maximum clique, and maximum induced matching. These problems are generally NP-hard. On the other hand, each of them may become polynomially solvable when restricted to graphs in special classes. However, polynomial-time solutions are available only for very few monogenic classes, i.e. classes defined by a single forbidden induced subgraph. Only three such results are available for the maximum independent set and maximum clique problems and only two for the maximum induced matching problem. In the present paper, we extend this restricted list of results by exploring the complexity of the problems in the class of 2P3-free graphs, which recently attracted considerable attention in the literature. By elaborating a polynomial-time solution to the maximum independent set problem in the class of 2K2-free graphs proposed by Farber in [16], we show that both maximum independent set (0-regular induced subgraph) and maximum induced matching(1-regular induced subgraph) are solvable in polynomial time for 2P3-free graphs. We also conjecture that the same is true for finding maximum k-regular induced subgraphs for each value of k. On the other hand, we conjecture that finding a maximum subset of vertices inducing the complement of a k-regular induced subgraph is NP-hard for 2P3-free graphs and verify the conjecture for k=0 (maximum clique), k=1 (maximum induced co-matching), and k=2.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Theoretical Computer Science | ||||
Publisher: | Elsevier BV | ||||
ISSN: | 03043975 | ||||
Official Date: | 2012 | ||||
Dates: |
|
||||
Volume: | Vol. 460 | ||||
Page Range: | pp. 26-33 | ||||
DOI: | 10.1016/j.tcs.2012.06.014 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |