该问题是否存在多项式时间解法？附O(n³)算法更新

更新：目前我已得到一个O(n³)复杂度的算法。

我正尝试为以下问题设计合理算法：

存在如下边对：

(1,2),(1,3),...,(1,n),  
(2,3),(2,4),...,(2,n),  
...  
(n-2,n-1),(n-2,n),  
(n-1,n)

同时存在m个约束条件（m≥n），每个约束形如至多选择[边对a,边对b,边对c,…]中的一个。每个边对恰好属于一个约束条件。

现需判断是否存在一种选边方案：选出n条边，使得1到n的每个数字恰好出现在2条选中的边对中。仅需判断可行性即可。

示例 #

当n=4时，约束条件为[{(1,2),(2,3)},{(1,3)},{(1,4),(2,4)},{(3,4)}]，选择(1,2),(1,3),(2,4),(3,4)即为合法方案。

疑问与现状 #

若该问题为NP-hard，能否找到时间复杂度低于2^(n²/4)的算法？

遗憾的是，目前我仅能通过枚举所有情况求解，其最坏时间复杂度为2^(n²/4)。

注意：n^m这类时间复杂度不属于多项式时间。

内容的提问来源于stack exchange，提问作者Error_Yuan