6 citations · 23 across the 15 of their papers we have counts for
Showing 2007Show all
3 papers · 1 filter
cs.CC2007★ 2 cited
NP by means of lifts and shadows
Gabor Kun, Jaroslav Nesetril
We show that every NP problem is polynomially equivalent to a simple combinatorial problem: the membership problem for a special class of digraphs. These classes are defined by mea…
math.CO2007
Forbidden lists (NP and CSP for combinatorialists)
Gabor Kun, Jaroslav Nesetril
We present a definition of the class NP in combinatorial context as the set of languages of structures defined by finitely many forbidden lifted substructures. We apply this to spe…
math.CO2007★ 6 cited
Constraints, MMSNP and expander relational structures
Gabor Kun
We give a poly-time construction for a combinatorial classic known as Sparse Incomparability Lemma, studied by Erdos, Lovasz, Nesetril, Rodl and others: We show that every Constrai…