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


updated 2023-12-25

Latest news

  • 2018-12-30 Added support for speed.
  • 2015-03-26 Added support for graph parameters.
  • 2014-03-15 Add preview tooltips for references.