Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs.
Matthew JohnsonBarnaby MartinSiani SmithSukanya PandeyDaniël PaulusmaErik Jan van LeeuwenPublished in: CoRR (2022)
Keyphrases
- np complete
- vertex set
- undirected graph
- weighted graph
- np hard
- polynomial time complexity
- randomly generated
- binary trees
- bounded treewidth
- edge detection
- directed graph
- graph structure
- tree structures
- planar graphs
- disjoint paths
- computational complexity
- pspace complete
- aggregate functions
- graph model
- satisfiability problem
- conjunctive queries