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

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

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 w...

Saved in:

書目詳細資料
Main Authors:	Busygin, Stanislav., Pasechnik, Dmitrii V.
其他作者:	School of Physical and Mathematical Sciences
格式:	Article
語言:	English
出版:	2012
主題:	DRNTU::Science::Mathematics::Discrete mathematics::Theory of computation
在線閱讀:	https://hdl.handle.net/10356/80117 http://hdl.handle.net/10220/8272
標簽:	添加標簽沒有標簽, 成為第一個標記此記錄!
機構:	Nanyang Technological University
語言:	English

相似書籍

Improved lower bounds on book crossing numbers of complete graphs
由: Salazar, G., et al.
出版: (2014)

Products of positive forms, linear matrix inequalities, and Hilbert 17th problem for ternary forms
由: Klerk, Etienne de., et al.
出版: (2012)

Minimum 2-clique and 3-clique partitions of simple connected graphs
由: Alto, Washington Lee
出版: (1992)

c-Extensions of the F4(2)-building
由: Ivanov, A. A., et al.
出版: (2012)

On the clique number of a strongly regular graph
由: Greaves, Gary Royden Watson, et al.
出版: (2021)

Clique algorithm
由: Tan, Majorvin N., et al.
出版: (2008)

Clique algorithm
由: Tan, Marjovin N., et al.
出版: (2008)

ID Numbers of Lobster Graphs
由: Tolentino, Mark Anthony C, et al.
出版: (2024)

The ride sharing routing problem : an optimization algorithm
由: Lawrence, Lucas
出版: (2021)

Efficient implementations of the BP heuristic for the shortest linear program (SLP) problem
由: Liu, Shuqing
出版: (2021)

Approximation of the stability number of a graph via copositive programming
由: Klerk, Etienne de., et al.
出版: (2011)

A problem on clique partitions of regular graphs
由: Campena, Francis Joseph H., et al.
出版: (2018)

Clique coverings and clique partitions of the K-power of graphs
由: Tanawat Wichianpaisarn
出版: (2014)

Clique coverings and clique partitions of the K-power of graphs
由: Tanawat Wichianpaisarn
出版: (2007)

Voter model on networks partitioned into two cliques of arbitrary sizes
由: Gastner, Michael T, et al.
出版: (2020)

A note on the stability number of an orthogonality graph
由: Klerk, Etienne de., et al.
出版: (2011)

String C-groups of order 1024
由: Gomi, Yasushi, et al.
出版: (2018)

A Framework for Coloring Symmetrical Patterns
由: De Las Peñas, Ma. Louise Antonette N, et al.
出版: (1999)

On eigenvalue bounds for the finite-state birth-death process intensity matrix
由: Tan, R.R.P, et al.
出版: (2020)

Fairness and incentives in committee election
由: Ly, Tevbot
出版: (2020)

Asymptotic improvement of GV bound
由: Yip, Jose Zheng Ho
出版: (2022)

Clique partitions of glued graphs
由: Uthoomporn Jongthawonwuth
出版: (2012)

Clique partitions of glued graphs
由: Uthoomporn Jongthawonwuth
出版: (2009)

On the Independence Number of Cayley Digraphs of Rectangular Groups
由: Sayan Panma, et al.
出版: (2018)

A common generalization of line graphs and clique graphs
由: Bernardo, Servando D., Jr.
出版: (2004)

Improved bounds for the crossing numbers of Km,n and Kn
由: Klerk, Etienne de., et al.
出版: (2011)

Applications of Polya’s theorem to distribution problems and partitions of integers
由: Vites Longani
出版: (2018)

Applications of Polya’s theorem to distribution problems and partitions of integers
由: Vites Longani
出版: (2018)

Min-entropy uncertainty relation for finite-size cryptography
由: Ng, Nelly Huei Ying., et al.
出版: (2013)

A study of private information retrieval and related primitives.
由: Zhang, Liang Feng
出版: (2012)

Constructions of relative difference sets with classical parameters and circulant weighing matrices
由: Leung, Ka Hin, et al.
出版: (2009)

Independent domination number in Cayley digraphs of rectangular groups
由: Nuttawoot Nupo, et al.
出版: (2018)

Random walks in distributed networks and their applications
由: Anisur Rahaman Molla
出版: (2014)

On (p^a,p^b,p^a,p^{a-b})-relative difference sets
由: Schmidt, Bernhard
出版: (2009)

On Hecke eigenvalues at primes of the form [g(n)]
由: Baier, Stephan, et al.
出版: (2015)

Demonstration of attacks on SSL-TLS protocols
由: Iyer Rajagopal Mahadevan
出版: (2022)

Examples of weak AES implementation and attacks against them
由: Yeap, Ernest Zong Han
出版: (2022)

Optimising implementation of block ciphers
由: Tan, Quan Quan
出版: (2019)

On the Fourier spectra of new APN functions
由: Tan, Yin, et al.
出版: (2014)

On the variance of average distance of subsets in the Hamming space
由: Fu, Fang-Wei, et al.
出版: (2013)