We show the close connection between the enumeration of cliques in a k-clique free graph G and the length of tree-like resolution refutations for formula Clique(G,k), which claims that G has a k-clique. The length of any such tree-like refutation is within a "fixed parameter tractable" factor from the number of cliques in the graph. We then proceed to drastically simplify the proofs of the lower bounds for the length of tree-like resolution refutations of Clique(G,k) shown in [Beyersdorff et at. 2013, Lauria et al. 2017], which now reduce to a simple estimate of the number of cliques.
Cliques enumeration and tree-like resolution proofs / Lauria, Massimo. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - 135:(2018), pp. 62-67. [10.1016/j.ipl.2018.03.001]
Cliques enumeration and tree-like resolution proofs
Lauria, Massimo
2018
Abstract
We show the close connection between the enumeration of cliques in a k-clique free graph G and the length of tree-like resolution refutations for formula Clique(G,k), which claims that G has a k-clique. The length of any such tree-like refutation is within a "fixed parameter tractable" factor from the number of cliques in the graph. We then proceed to drastically simplify the proofs of the lower bounds for the length of tree-like resolution refutations of Clique(G,k) shown in [Beyersdorff et at. 2013, Lauria et al. 2017], which now reduce to a simple estimate of the number of cliques.| File | Dimensione | Formato | |
|---|---|---|---|
|
Lauria_Cliques-enumeration_2018.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
323.45 kB
Formato
Adobe PDF
|
323.45 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
