Parameterized Complexity of Vertex Splitting to Pathwidth at most 1.

Jakob Baumann Matthias Pfretzschner Ignaz Rutter

Published in: CoRR (2023)

Keyphrases

parameterized complexity
bounded treewidth
fixed parameter tractable
np complete
vertex set
global constraints
decision problems
relational learning
np hard
directed graph
symmetry breaking
database systems
lower bound
constraint programming
conjunctive queries