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.

An and/or graph is an acyclic, edge-weighted directed graph containing a single source vertex such that every vertex v   has a label f(v)∈{and,or}f(v)∈{and,or}. A solution subgraph H of an and/or-graph must contain the source and obey the following rule: if an and-vertex (resp. or-vertex) is included in H then all (resp. one) of its out-edges must also be included in H  . X-y graphs are defined as a generalization of and/or graphs: every vertex vivi of an x-y graph has a label xixi-yiyi, in such a way that if a vertex vivi is included in a solution subgraph H   of an x-y graph then xixi of its yiyi out-edges must also be included in H. In this work, we analyze complexity aspects (both from the classical and the parameterized point of view) of finding solution subgraphs of minimum weight for and/or and x-y graphs.