Does the input network contain the input subset of leaves as a softwired cluster?

Bibliographic references on the *Who is who in phylogenetic networks*

**Input:** A phylogenetic network *N* on a set *X* of taxa and a subset *C* of *X*.

**Output:** YES if *N* contains a tree which has *C* as a cluster, NO otherwise.

- binary galled network: Solvable in polynomial time. [reference] (Lemma 1. The proof is a bit more detailed in Proposition 12 of this reference.)
- binary level-2: Solvable in O(
*n*) time [reference] (Observation 1) - binary level-3: Solvable in O(
*n*) time [reference] (Observation 1) - binary level-k: Solvable in O(2
^{k}.*n*) time [reference] (Observation 1) - binary reticulation-visible: Solvable in O(
*n*) time [reference]

- binary: NP-hard, reduction from Cluster Containment in general graphs [reference] (Lemma 4.1)
- binary regular: NP-hard, reduction from Cluster Containment in general graphs using:

In the inclusion diagram below, the names of classes with positive results on this problem are colored green and the name of the classes with negative results are colored red. Classes with both positive and negative results are colored yellow.

This website was programmed and is maintained by Philippe Gambette. It was started during the internship of Maxime Morgado at LIGM, in June-July 2015, and also contains contributions made from Narges Tavassoli from November 2016 to January 2017.

Please contact Philippe Gambette if you have any suggestions about this website, especially about problems, properties, results or subclasses to add.