No label defined (Q4034894)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 175833
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 175833

      Statements

      0 references
      18 May 1993
      0 references
      NP-complete
      0 references
      kernel
      0 references
      [For the entire collection see Zbl 0746.00034.] It is proved that the following problems are NP-complete. \(\Pi_ 1\): An ordinary graph \(G=(V,E)\) and a non-empty set \(V'\subseteq V\) are given. Does kernel of the graph \(G\) exist in \(V'\)? \(\Pi_ 4\): A finite set \(S=\{a_ j:j\in\overline{1,n},n\geq 3\}\) and a family \(S_ 1,\dots,S_ m\) of its three-element subsets are given. Does a subset \(S'\subset S\) exist such that \(| S_ i-S'|=2\) for every \(i\in\overline{1,m}\)?
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references