When *X* is a path graph, we show that the connected components of FS(*X*,*Y*) correspond to the acyclic orientations of the complement of *Y*. When *X* is a cycle, we obtain a full description of the connected components of FS(*X*,*Y*) in terms of toric acyclic orientations of the complement of *Y*. In a more probabilistic vein, we address the case of "typical" *X* and *Y* by proving that if *X* and *Y* are independent Erdős-Rényi random graphs with *n* vertices and edge probability *p*, then the threshold probability guaranteeing the connectedness of FS(*X*,*Y*) with high probability is *p* = *n*^{-1/2+o(1)}. We also study the case of "extremal" *X* and *Y* by proving that the smallest minimum degree of the *n*-vertex graphs *X* and *Y* that guarantees the connectedness of FS(*X*,*Y*) is between 3*n*/5+*O*(1) and 9*n*/14+*O*(1). Furthermore, we obtain bipartite analogues of the latter two results.

Received: December 1, 2020. Accepted: March 1, 2021. Final version: April 29, 2021.

The following versions are available:

- PDF ( K)
- TeX version