How is FLO NP-complete?
Let G be a social network where vertices correspond to people and edges are relationships between people (undirected).
Some pairs of people (who are friends) get married. We allow polygamy: person a could be married to person b and to person c. A friend relationship between person x and person y is defunct if x did not marry y, but either x or y married someone else such as person z. The entire social network is said to be flo if every relationship is either a married couple or a defunct friendship.
Let FLO be the language consisting of strings $<G,k>$ such that G is a social network in which k marriages can make the network become flo.