Общая грань некоторых $0/1$-многогранников с NP-полным критерием несмежности вершин

В работе рассматриваются многогранники двойных покрытий. В 1995 г. Мацуи установил, что задача проверки несмежности вершин для этих многогранников NP-полна. Мы покажем, что многогранники двойных покрытий являются гранями многогранников, ассоциированных со следующими задачами: задача о рюкзаке, задача о покрытии множества, задача о кубическом подграфе, задача о $3$-выполнимости, задача о частичном упорядочении, задача коммивояжёра и некоторые другие.