Polynomial kernels and user reductions for the workflow satisfiability problem

DOI10.1007/S00453-015-9986-9MaRDI QIDQ309799zbMATH OpenOpenAlexFDO

Authors G. Gutin, Stefan Kratsch, Magnus Wahlström

Publication date 7 September 2016

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

parameterized complexitykernelizationworkflow satisfiability problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Abstract: The Workflow Satisfiability Problem (WSP) is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by business rules. We are required to decide whether there exists a plan -- an assignment of tasks to authorized users -- such that all constraints are satisfied. The WSP is, in fact, the conservative Constraint Satisfaction Problem (i.e., for each variable, here called task, we have a unary authorization constraint) and is, thus, NP-complete. It was observed by Wang and Li (2010) that the number k of tasks is often quite small and so can be used as a parameter, and several subsequent works have studied the parameterized complexity of WSP regarding parameter k. We take a more detailed look at the kernelization complexity of WSP(Gamma) when Gamma denotes a finite or infinite set of allowed constraints. Our main result is a dichotomy for the case that all constraints in Gamma are regular: (1) We are able to reduce the number n of users to n' <= k. This entails a kernelization to size poly(k) for finite Gamma, and, under mild technical conditions, to size poly(k+m) for infinite Gamma, where m denotes the number of constraints. (2) Already WSP(R) for some R in Gamma allows no polynomial kernelization in k+m unless the polynomial hierarchy collapses.

Recommendations

• Polynomial kernels and user reductions for the workflow satisfiability problem
• Iterative Plan Construction for the Workflow Satisfiability Problem
• Tight lower bounds for the workflow satisfiability problem based on the strong exponential time hypothesis
• Parameterized complexity of the workflow satisfiability problem
• On the workflow satisfiability problem with class-independent constraints

Cites work

• A completeness theory for polynomial (Turing) kernelization
• Engineering algorithms for workflow satisfiability problem with user-independent constraints
• Fixed-parameter tractability of workflow satisfiability in the presence of seniority constraints
• Fundamentals of parameterized complexity
• Iterative Plan Construction for the Workflow Satisfiability Problem
• Kernelization -- preprocessing with a guarantee
• Kernelization lower bounds through colors and IDs
• Partial kernelization for rank aggregation: theory and experiments
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses

Cited in

(2)

• Parameterized complexity of the workflow satisfiability problem
• Polynomial kernels and user reductions for the workflow satisfiability problem

This page was built for publication: Polynomial kernels and user reductions for the workflow satisfiability problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q309799)