Cliquenweite

Die Cliquenweite ist ein Begriff aus der Graphentheorie und ordnet jedem ungerichteten Graphen eine natürliche Zahl zu. Sie ist daher ein . Mit Hilfe eines k-Ausdrucks (s. u.) lassen sich viele NP-vollständige Probleme wie zum Beispiel HAMILTONKREIS oder CLIQUE und das damit eng verwandte UNABHÄNGIGE MENGE in Zeit lösen, was für konstante eine lineare Laufzeit ist. Da jedoch nicht bekannt ist, ob ein k-Ausdruck hinreichend schnell berechnet werden kann, ist es zur Zeit unklar, ob man hieraus folgern kann, dass diese Probleme auf Graphen mit beschränkter Cliquenweite effizient zu lösen sind.