Screenshots

Browse database window

The 'browse database' window. Currently the Berge graphs are selected. The window shows complexity of the Independent Set problem on Berge graphs (polynomial) and its super-, sub-, and equivalent classes.

Complexity boundary for independent set

The boundary between polynomial/NP-complete for the Independent Set problem, as seen when starting from bridged graphs. Red classes are NP-Complete, dark green are polynomial, light green are linear, while white are still open.

Relation between two classes

Finding and drawing the relation between $2K2$ and $(2K2,C4,C5)$-free graphs. The system calculates that $(2K2,C4,C5)$-free graphs are a subclass of $2K2$-free graphs and draws all classes that are superset of one and a subset of the other class.

Choosing the naming preference

The same diagram, but with forbidden subgraph characterization as naming preference.

Database contents

1691classes
242656inclusions
28919complexities
51902bounds

updated 2026-05-10


Latest news

  • 2025-11-16 Added pages for speed and self-complimentariness.
  • 2024-07-22 Java application instructions updated.
  • 2018-12-30 Added support for speed.