Tight lower bounds for the Workflow Satisfiability Problem based on the Strong Exponential Time Hypothesis. / Gutin, Gregory; Wahlstrom, Magnus.

In: Information Processing Letters, Vol. 116, No. 3, 03.2016, p. 223-226.

Research output: Contribution to journalArticlepeer-review

Published

Standard

Tight lower bounds for the Workflow Satisfiability Problem based on the Strong Exponential Time Hypothesis. / Gutin, Gregory; Wahlstrom, Magnus.

In: Information Processing Letters, Vol. 116, No. 3, 03.2016, p. 223-226.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

BibTeX

@article{6d2db1da42fb4c94aa2e3ff48920ae22,
title = "Tight lower bounds for the Workflow Satisfiability Problem based on the Strong Exponential Time Hypothesis",
abstract = "The Workflow Satisfiability Problem (WSP) asks whether there exists an assignment of authorized users to the steps in a workflow specification, subject to certain constraints on the assignment. The problem is NP-hard even when restricted to just not equal constraints. Since the number of steps k is relatively small in practice, Wang and Li (2010) [21] introduced a parametrisation of WSP by k. Wang and Li (2010) [21] showed that, in general, the WSP is W[1]-hard, i.e., it is unlikely that there exists a fixed-parameter tractable (FPT) algorithm for solving the WSP. Crampton et al. (2013) [10] and Cohen et al. (2014) [6] designed FPT algorithms of running time O⁎(2k) and O⁎(2klog2⁡k) for the WSP with so-called regular and user-independent constraints, respectively. In this note, we show that there are no algorithms of running time O⁎(2ck) and O⁎(2cklog2⁡k) for the two restrictions of WSP, respectively, with any c<1, unless the Strong Exponential Time Hypothesis fails.",
author = "Gregory Gutin and Magnus Wahlstrom",
year = "2016",
month = mar,
doi = "10.1016/j.ipl.2015.11.008",
language = "English",
volume = "116",
pages = "223--226",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "3",

}

RIS

TY - JOUR

T1 - Tight lower bounds for the Workflow Satisfiability Problem based on the Strong Exponential Time Hypothesis

AU - Gutin, Gregory

AU - Wahlstrom, Magnus

PY - 2016/3

Y1 - 2016/3

N2 - The Workflow Satisfiability Problem (WSP) asks whether there exists an assignment of authorized users to the steps in a workflow specification, subject to certain constraints on the assignment. The problem is NP-hard even when restricted to just not equal constraints. Since the number of steps k is relatively small in practice, Wang and Li (2010) [21] introduced a parametrisation of WSP by k. Wang and Li (2010) [21] showed that, in general, the WSP is W[1]-hard, i.e., it is unlikely that there exists a fixed-parameter tractable (FPT) algorithm for solving the WSP. Crampton et al. (2013) [10] and Cohen et al. (2014) [6] designed FPT algorithms of running time O⁎(2k) and O⁎(2klog2⁡k) for the WSP with so-called regular and user-independent constraints, respectively. In this note, we show that there are no algorithms of running time O⁎(2ck) and O⁎(2cklog2⁡k) for the two restrictions of WSP, respectively, with any c<1, unless the Strong Exponential Time Hypothesis fails.

AB - The Workflow Satisfiability Problem (WSP) asks whether there exists an assignment of authorized users to the steps in a workflow specification, subject to certain constraints on the assignment. The problem is NP-hard even when restricted to just not equal constraints. Since the number of steps k is relatively small in practice, Wang and Li (2010) [21] introduced a parametrisation of WSP by k. Wang and Li (2010) [21] showed that, in general, the WSP is W[1]-hard, i.e., it is unlikely that there exists a fixed-parameter tractable (FPT) algorithm for solving the WSP. Crampton et al. (2013) [10] and Cohen et al. (2014) [6] designed FPT algorithms of running time O⁎(2k) and O⁎(2klog2⁡k) for the WSP with so-called regular and user-independent constraints, respectively. In this note, we show that there are no algorithms of running time O⁎(2ck) and O⁎(2cklog2⁡k) for the two restrictions of WSP, respectively, with any c<1, unless the Strong Exponential Time Hypothesis fails.

U2 - 10.1016/j.ipl.2015.11.008

DO - 10.1016/j.ipl.2015.11.008

M3 - Article

VL - 116

SP - 223

EP - 226

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 3

ER -