Paper Info
Title
Tractability, hardness, and kernelization lower bound for and/or graph solution.
Abstract
And/or graphs are well-known data structures with several applications in many fields of computer science, such as Artificial Intelligence, Distributed Systems, Software Engineering, and Operations Research. An and/or graph is an acyclic digraph G containing a single source vertex s, where every vertex v∈V(G) has a label f(v)∈{ and,or }. In an and/or graph, (weighted) 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. A solution subgraph H of an and/or graph G is a subdigraph of G containing its source vertex and such that 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. In general, solution subgraphs represent feasible solutions of problems modeled by and/or graphs. The optimization problem associated with an and/or graph G consists of finding a minimum weight solution subgraph H of G, where the weight of a solution subgraph is the sum of the weights of its edges. Because of its wide applicability, in this work we develop a multivariate investigation of this optimization problem. In a previous paper (Souza et al., 2013) we have analyzed the complexity of such a problem under various aspects, including parameterized versions of it. However, the main open question has remained open: Is the problem of finding a solution subgraph of weight at most k (where k is the parameter) in FPT? In this paper we answer negatively to this question, proving the W[1]-hardness of the problem, and its W[P]-completeness when zero-weight edges are allowed. We also show that the problem is fixed-parameter tractable when parameterized by the tree-width, but it is W[SAT]-hard with respect to the clique-width and k as aggregated parameters. In addition, we show that when the out-edges of each or-vertex have all the same weight (a condition very common in practice), the problem becomes fixed-parameter tractable by the clique-width. Finally, using a framework developed by Bodlaender et al. (2009) and Fortnow and Santhanam (2011), based upon the notion of compositionality, we show that the tractable cases do not admit a polynomial kernel unless NP⊆coNP∕poly, even restricted to instances without or-vertices with out-degree greater than two.
Year
DOI
Venue
2017
10.1016/j.dam.2017.07.029
Discrete Applied Mathematics
Keywords
Field
DocType
And/or graphs,W[P]-complete,W[1]-hard,FPT,Tree-width,Clique-width
Discrete mathematics,Combinatorics,Edge cover,Vertex (graph theory),Neighbourhood (graph theory),Cycle graph,Induced subgraph isomorphism problem,Degree (graph theory),Vertex cover,Mathematics,Feedback vertex set
Journal
Volume
Issue
ISSN
232
C
0166-218X
Citations 
PageRank 
References 
0
0.34
13
Authors
2
Name
Order
Citations
PageRank
Uéverton S. Souza12021.12
Fábio Protti235746.14