Determining if a graph is a cycle or is bipartite is very easy (in L), but finding a maximum bipartite or a maximum cycle subgraph is NP-complete.
Determinarea dacă un graf este ciclic⁠(d) sau este bipartit este foarte ușoară (în L), dar găsirea unui subgraf bipartit maxim sau a unui subgraf ciclic maxim este NP-completă.