This is my first post on stack exchange!
Say we have a graph whose nodes are connected by a set of arbitrary edges. A node is said to be "defined" if ALL the connecting nodes are defined. How do I construct an algorithm to find the minimum set of nodes to define manually so that by induction, all the nodes in the graph can be defined?
The graph is cyclic.
Thanks very much.
You can't have two neighbors that are both undefined initially. In a cycle this means every other neighbor must be defined initially. If the graph has $2n$ vertices, you must define at least $n$ of them initially; if it has $2n+1$ vertices, you must define at least $n+1$ of them initially.