Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/80117
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBusygin, Stanislav.en
dc.contributor.authorPasechnik, Dmitrii V.en
dc.date.accessioned2012-07-03T03:04:26Zen
dc.date.accessioned2019-12-06T13:41:03Z-
dc.date.available2012-07-03T03:04:26Zen
dc.date.available2019-12-06T13:41:03Z-
dc.date.copyright2006en
dc.date.issued2006en
dc.identifier.citationBusygina, S., & Pasechnikb, D. V. (2006). On NP-hardness of the clique partition: independence number gap recognition and related problems. Discrete Mathematics, 306(4), 460–463.en
dc.identifier.urihttps://hdl.handle.net/10356/80117-
dc.description.abstractWe show that for a graph G it is NP-hard to decide whether its independence number α(G) equals its clique partition number ¯χ(G) even when some minimum clique partition of G is given. This implies that any α(G)-upper bound provably better than ¯χ (G) is NP-hard to compute. To establish this result we use a reduction of the quasigroup completion problem (QCP, known to be NP-complete) to the maximum independent set problem. A QCP instance is satisfiable if and only if the independence number α(G) of the graph obtained within the reduction is equal to the number of holes h in the QCP instance. At the same time, the inequality ¯χ (G)≤ h always holds. Thus, QCP is satisfiable if and only if α(G) = ¯χ (G) = h. Computing the Lovász number ϑ(G) we can detect QCP unsatisfiability at least when ¯χ (G) <h. In the other cases QCP reduces to ¯χ (G) − α(G) >0 gap recognition, with one minimum clique partition of G known.en
dc.format.extent6 p.en
dc.language.isoenen
dc.relation.ispartofseriesDiscrete mathematicsen
dc.rights© 2006 Elsevier. This is the author created version of a work that has been peer reviewed and accepted for publication by Discrete Mathematics, Elsevier. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: DOI [http://dx.doi.org/10.1016/j.disc.2006.01.004].en
dc.subjectDRNTU::Science::Mathematics::Discrete mathematics::Theory of computationen
dc.titleOn NP-hardness of the clique partition : independence number gap recognition and related problemsen
dc.typeJournal Articleen
dc.contributor.schoolSchool of Physical and Mathematical Sciencesen
dc.identifier.doi10.1016/j.disc.2006.01.004en
dc.description.versionAccepted versionen
item.fulltextWith Fulltext-
item.grantfulltextopen-
Appears in Collections:SPMS Journal Articles
Files in This Item:
File Description SizeFormat 
11.On-NP-hardness.pdf318.56 kBAdobe PDFThumbnail
View/Open

SCOPUSTM   
Citations 50

6
Updated on Jul 18, 2024

Web of ScienceTM
Citations 20

6
Updated on Oct 27, 2023

Page view(s) 20

743
Updated on Jul 18, 2024

Download(s) 20

327
Updated on Jul 18, 2024

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.