Revisiting the complexity of and/or graph solution

作者：

Highlights：

• 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.

摘要

•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,Computational complexity,Fixed parameter tractability,NP-hardness,W[1]-hardness,W[2]-hardness

论文评审过程：Received 22 December 2011, Revised 18 March 2013, Accepted 8 April 2013, Available online 16 April 2013.

论文官网地址：https://doi.org/10.1016/j.jcss.2013.04.001