Revisiting the complexity of and/or graph solution
From MaRDI portal
(Redirected from Publication:394337)
Abstract: This paper presents a study on two data structures that have been used to model several problems in computer science: and/or graphs and x-y graphs. An and/or graph is an acyclic digraph containing a source, such that every vertex v has a label f(v) in {and,or} and edges represent dependency relations between vertices: a vertex labeled and depends on all of its out-neighbors, while a vertex labeled or depends on only one of its out-neighbors. X-y graphs are defined as a natural generalization of and/or graphs: every vertex vi of an x-y graph has a label xi-yi to mean that vi depends on xi of its yi out-neighbors. We analyze the complexity of the optimization problems Min-and/or and Min-x-y, which consist of finding solution subgraphs of optimal weight for and/or and x-y graphs, respectively. Motivated by the large applicability as well as the hardness of Min-and/or and Min-x-y, we study new complexity aspects of such problems, both from a classical and a parameterized point of view. We prove that Min-and/or remains NP-hard even for a very restricted family of and/or graphs where edges have weight one and or-vertices have out-degree at most two (apart from other property related to some in-degrees), and that deciding whether there is a solution subtree with weight exactly k of a given x-y tree is also NP-hard. We also show that: (i) the parameterized problem Min-and/or(k, r), which asks whether there is a solution subgraph of weight at most k where every or-vertex has at most r out-edges with the same weight, is FPT; (ii) the parameterized problem Min-and/or0(k), whose domain includes and/or graphs allowing zero-weight edges, is W[2]-hard; (iii) the parameterized problem Min-x-y(k) is W[1]-hard.
Recommendations
Cites work
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 2050889 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem
- A randomized competitive algorithm for evaluating priced AND/OR trees
- Computationally Related Problems
- Models for parallel and distributed computation. Theory, algorithmic techniques and application
- On the Optimal Solutions to AND/OR Series-Parallel Graphs
- Parametrized complexity theory.
Cited in
(9)- And/or-convexity: a graph convexity based on processes and deadlock models
- ANALYZING VULNERABILITIES OF CRITICAL INFRASTRUCTURES USING FLOWS AND CRITICAL VERTICES IN AND/OR GRAPHS
- Succinct certification of monotone circuits
- Tractability, hardness, and kernelization lower bound for and/or graph solution
- Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case
- On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem
- Searching for a minimal solution subgraph in explicit AND/OR graphs
- Succinct monotone circuit certification: planarity and parameterized complexity
- Computing the best-case energy complexity of satisfying assignments in monotone circuits
This page was built for publication: Revisiting the complexity of and/or graph solution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q394337)
