What's the minimum number of words you'd need to define all other words? (2012)

Re:What's the minimum number of words you'd need to define a... by hairtuq on Thursday March 07, 2019 @04:24PM (#19332621)

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

[ Parent | on HN ]

Re:What's the minimum number of words you'd need to define a... by titanix2 on Thursday March 07, 2019 @05:39PM (#19333319)

I checked the comments to check if this paper was mentioned anywhere. Good recommendation.

[ Parent | on HN ]

Re:What's the minimum number of words you'd need to define a... by fginionio on Thursday March 07, 2019 @04:45PM (#19332805)

Looks like you found our answer! Someone's already done the hard work.

[ Parent | on HN ]

Re:What's the minimum number of words you'd need to define a... by zuminator on Thursday March 07, 2019 @06:19PM (#19333659)

This is not necessarily the answer. It's an upper-bound for the answer.

[ Parent | on HN ]