Bounded-Degree Cut is Fixed-Parameter Tractable.
Mingyu XiaoHiroshi NagamochiPublished in: CoRR (2020)
Keyphrases
- fixed parameter tractable
- bounded treewidth
- bounded degree
- parameterized complexity
- np complete
- vertex set
- decision problems
- boolean functions
- computational problems
- np hard
- conjunctive queries
- graph theoretic
- global constraints
- relational learning
- computational complexity
- phase transition
- constraint satisfaction problems
- lower bound