Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth.
Cédric BentzPierre Le BodicPublished in: Theor. Comput. Sci. (2020)
Keyphrases
- bounded treewidth
- np complete
- decision problems
- tractable cases
- polynomial size
- conjunctive queries
- fixed parameter tractable
- highly parallelizable
- boolean functions
- relational learning
- relational data
- parameterized complexity
- information extraction
- knowledge base
- information retrieval
- query answering
- logic programming
- logic programs
- computational complexity