mirage

On NP-hardness of the clique partition : independence number gap recognition and related problems.

DSpace/Manakin Repository

 

Search DR-NTU


Advanced Search Subject Search

Browse

My Account

On NP-hardness of the clique partition : independence number gap recognition and related problems.

Show simple item record

dc.contributor.author Busygin, Stanislav.
dc.contributor.author Pasechnik, Dmitrii V.
dc.date.accessioned 2012-07-03T03:04:26Z
dc.date.available 2012-07-03T03:04:26Z
dc.date.copyright 2006
dc.date.issued 2012-07-03
dc.identifier.citation Busygina, 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.
dc.identifier.uri http://hdl.handle.net/10220/8272
dc.description.abstract We 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.
dc.format.extent 6 p.
dc.language.iso en
dc.relation.ispartofseries Discrete mathematics
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].
dc.subject DRNTU::Science::Mathematics::Discrete mathematics::Theory of computation.
dc.title On NP-hardness of the clique partition : independence number gap recognition and related problems.
dc.type Journal Article
dc.contributor.school School of Physical and Mathematical Sciences
dc.identifier.doi http://dx.doi.org/10.1016/j.disc.2006.01.004
dc.description.version Accepted version

Files in this item

Files Size Format View
11.On-NP-hardness.pdf 326.2Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Statistics

Total views

All Items Views
On NP-hardness of the clique partition : independence number gap recognition and related problems. 212

Total downloads

All Bitstreams Views
11.On-NP-hardness.pdf 87

Top country downloads

Country Code Views
United States of America 55
Russian Federation 7
China 6
Singapore 4
Unknown Country 2

Top city downloads

city Views
Mountain View 38
Singapore 4
Seattle 2
Birobidzhan 1
Dolgoprudnyy 1

Downloads / month

  2014-05 2014-06 2014-07 total
11.On-NP-hardness.pdf 0 0 3 3