4 ms·
This will not yield a minimal set; in a cycle, it is only necessary to remove at least one word. The problem is thus to delete the minimum number of vertices to
by hairtuq 8y ago
This will not yield a minimal set; in a cycle, it is only necessary to remove at least one word. The problem is thus to delete the minimum number of vertices to remove all cycles. This is the NP-hard Feedback Vertex Set problem. Here's a paper that solves it for a dictionary (there is some more): https://arxiv.org/abs/0911.5703 https://arxiv.org/abs/0911.5703
- fginionio 8y agoLooks like you found our answer! Someone's already done the hard work.
- zuminator 8y agoThis is not necessarily the answer. It's an upper-bound for the answer.
- titanix2 8y agoI checked the comments to check if this paper was mentioned anywhere. Good recommendation.
- deleted 8y ago[deleted]