ningago @ 2022-07-02 16:18:36
RT。蒟蒻太菜了，只会二分图，既然如此求教一下无向图最大独立集可以多项式求解吗？qwq
by jijidawang @ 2022-07-02 16:20:10
我记得是 NPC .
by liaoyichen @ 2022-07-02 16:24:25
没有多项式做法
by liaoyichen @ 2022-07-02 16:25:00
是补图的最大团
by ningago @ 2022-07-02 16:25:49
@liaoyichen 那有没有其他的特殊图可以多项式求解呢？
by liaoyichen @ 2022-07-02 16:26:55
二分图
by ningago @ 2022-07-02 16:27:12
@liaoyichen 其他的（（（（
by jijidawang @ 2022-07-02 16:28:15
@ningago 基环树（？
by liaoyichen @ 2022-07-02 16:29:02
菊花图，n - 1
by fjy666 @ 2022-07-02 16:29:58
贰分图和基环树
by liaoyichen @ 2022-07-02 16:30:36
@jijidawang 基环树咋做，复杂度多少