Polynomial kernels and user reductions for the workflow satisfiability problem

DOI10.1007/S00453-015-9986-9zbMATH Open1350.68143arXiv1409.7261OpenAlexW2065131193MaRDI QIDQ309799FDOQ309799

Magnus Wahlström, G. Gutin, Stefan Kratsch

Publication date: 7 September 2016

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

parameterized complexitykernelizationworkflow satisfiability problem

Mathematics Subject Classification ID

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

Cites Work

• Fundamentals of parameterized complexity
• Kernelization – Preprocessing with a Guarantee
• Partial Kernelization for Rank Aggregation: Theory and Experiments
• Kernelization Lower Bounds Through Colors and IDs
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• A Completeness Theory for Polynomial (Turing) Kernelization
• Iterative Plan Construction for the Workflow Satisfiability Problem
• Engineering Algorithms for Workflow Satisfiability Problem with User-Independent Constraints
• Fixed-Parameter Tractability of Workflow Satisfiability in the Presence of Seniority Constraints

Cited In (1)

• Parameterized Complexity of 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)