Revisiting the complexity of and/or graph solution

DOI10.1016/J.JCSS.2013.04.001zbMATH Open1311.68078arXiv1203.3249OpenAlexW2027224637MaRDI QIDQ394337FDOQ394337

Maise Dantas da Silva, Uéverton dos Santos Souza, Fábio Protti

Publication date: 27 January 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1203.3249

Recommendations

• Tractability, hardness, and kernelization lower bound for and/or graph solution
• Searching for a minimal solution subgraph in explicit AND/OR graphs
• On fast path-finding algorithms in AND-OR graphs
• scientific article; zbMATH DE number 2089979
• scientific article; zbMATH DE number 1163292

zbMATH Keywords

computational complexityNP-hardnessfixed parameter tractabilityW[1-hardness]and/or graphsW[2-hardness]

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Title not available (Why is that?)
• Parametrized complexity theory.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computationally Related Problems
• A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem
• Models for parallel and distributed computation. Theory, algorithmic techniques and application
• Title not available (Why is that?)
• On the Optimal Solutions to AND/OR Series-Parallel Graphs
• A randomized competitive algorithm for evaluating priced AND/OR trees

Cited In (9)

• ANALYZING VULNERABILITIES OF CRITICAL INFRASTRUCTURES USING FLOWS AND CRITICAL VERTICES IN AND/OR GRAPHS
• Succinct monotone circuit certification: planarity and parameterized complexity
• And/or-convexity: a graph convexity based on processes and deadlock models
• 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
• Succinct certification of monotone circuits
• Computing the best-case energy complexity of satisfying assignments in monotone circuits
• Searching for a minimal solution subgraph in explicit AND/OR graphs
• On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem

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)