Showing cs.CCShow all
3 papers · 1 filter
cs.CC2026
: Truly Linear FPT
Benjamin Merlin Bumpus, Rod Downey, Tala Eagling-Vose +7
Parameterized complexity has always been concerned with practical computing: by confining combinatorial explosion to a secondary parameter , one can uncover why and how many NP-…
cs.CC2025
Restricted CSPs and F-free Digraph Algorithmics
Santiago Guzmán-Pro, Barnaby Martin
In recent years, much attention has been placed on the complexity of graph homomorphism problems when the input is restricted to -free and -subgraph-f…
cs.CC2022
Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
Matthew Johnson, Barnaby Martin, Siani Smith +3
We show that Edge Multiway Cut (also called Multiterminal Cut) and Node Multiway Cut are NP-complete on graphs of maximum degree (also known as subcubic graphs). This improves…