Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs

November 22, 2022 · The Ethereal · 🏛 Scandinavian Workshop on Algorithm Theory

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Matthew Johnson, Barnaby Martin, Siani Smith, Sukanya Pandey, Daniel Paulusma, Erik Jan van Leeuwen arXiv ID 2211.12203 Category cs.CC: Computational Complexity Cross-listed cs.DM, cs.DS Citations 1 Venue Scandinavian Workshop on Algorithm Theory Last Checked 6 months ago
Abstract
We show that Edge Multiway Cut (also called Multiterminal Cut) and Node Multiway Cut are NP-complete on graphs of maximum degree $3$ (also known as subcubic graphs). This improves on a previous degree bound of $11$. Our NP-completeness result holds even for subcubic graphs that are planar.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 🎉 Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

📜 Similar Papers

In the same crypt — Computational Complexity