Revisiting the complexity of and/or graph solution
We study new complexity aspects of optimization problems associated with and/or-graphs and x-y graphs. AND/OR GRAPH SOLUTION parameterized by size of solution and number of out-edges of same weight of or-vertices is in FPT. X-Y GRAPH SOLUTION when parameterized by the size of the solution subgraph is W[1]-hard.
and/or graphs w[1]-hardness computational complexity fixed parameter tractability np-hardness w[2]-hardness