The class of graph deletion problems has been extensively studied in theoretical computer science, particularly in the field of parameterized complexity. Recently, a new notion of graph deletion problems was introduced, called deletion to scattered graph classes , where after deletion, each connected component of the graph should belong to at least one of the given graph classes. While fixed-parameter algorithms were given for a wide variety of problems, little progress has been made on the kernelization complexity of any of them. Here, we present the first non-trivial polynomial kernel for one such deletion problem, where, after deletion, each connected component should be a clique or a tree - that is, as densest as possible or as sparsest as possible (while being connected). We develop a kernel of O ( k 5 ) vertices for the same.

Role mining is a technique that is used to derive a role-based authorization policy from an existing policy. Given a set of users U , a set of permissions P , and a user–permission authorization relation \(\mathit {UPA} \subseteq U \times P\) , a role mining algorithm seeks to compute a set of roles R , a user–role authorization relation \(\mathit {UA} \subseteq U \times R\) , and a permission–role authorization relation \(\mathit {PA} \subseteq R \times P\) , such that the composition of UA and PA is close (in some appropriate sense) to UPA . Role mining is therefore a core problem in the specification of role-based authorization policies. Role mining is known to be hard in general and exact solutions are often impossible to obtain, so there exists an extensive literature on variants of the role mining problem that seek to find approximate solutions and algorithms that use heuristics to find reasonable solutions efficiently. In this article, we first introduce the Generalized Noise Role Mining problem (GNRM)—a generalization of the MinNoise Role Mining problem—which we believe has considerable practical relevance. In particular, GNRM can produce “security-aware” or “availability-aware” solutions. Extending the work of Fomin et al., we show that GNRM is fixed parameter tractable, with parameter \(r + k\) , where \(r\) is the number of roles in the solution and \(k\) is the number of discrepancies between \(\mathit {UPA}\) and the relation defined by the composition of \(\mathit {UA}\) and \(\mathit {PA}\) . We further introduce a bi-objective optimization variant of GNRM, where we wish to minimize both \(r\) and \(k\) subject to upper bounds \(r \le \bar{r}\) and \(k\le \bar{k}\) , where \(\bar{r}\) and \(\bar{k}\) are constants. We show that the Pareto front of this bi-objective optimization problem (BO-GNRM) can be computed in fixed-parameter tractable time with parameter \(\bar{r} +\bar{k}\) . From a practical perspective, a solution to BO-GNRM gives security managers the opportunity to identify a mined policy offering the best tradeoff between the number of policy discrepancies and the number of roles. We then report the results of our experimental work using the integer programming solver Gurobi to solve instances of BO-GNRM. Our key findings are that (a) we obtained strong support that Gurobi’s performance is fixed-parameter tractable, and (b) our results suggest that our techniques may be useful for role mining in practice, based on our experiments in the context of three well-known real-world authorization policies. We observed that, in many cases, our solver is capable of obtaining optimal solutions when the values of either k or r are small.

Given a (connected) undirected graph G, a set X ⊆ V(G) and integers k and p, the Steiner Subgraph Extension problem asks whether there exists a set S ⊇ X of at most k vertices such that G[S] is a p-edge-connected subgraph. This problem is a natural generalization of the well-studied Steiner Tree problem (set p = 1 and X to be the terminals). In this paper, we initiate the study of Steiner Subgraph Extension from the perspective of parameterized complexity and give a fixed-parameter algorithm (i.e., FPT algorithm) parameterized by k and p on graphs of bounded degeneracy (removing the assumption of bounded degeneracy results in W-hardness). Besides being an independent advance on the parameterized complexity of network design problems, our result has natural applications. In particular, we use our result to obtain new single-exponential FPT algorithms for several vertex-deletion problems studied in the literature, where the goal is to delete a smallest set of vertices such that: (i) the resulting graph belongs to a specified hereditary graph class, and (ii) the deleted set of vertices induces a p-edge-connected subgraph of the input graph.

We introduce and study two natural generalizations of the Connected Vertex Cover (VC) problem: the p-Edge-Connected and p-Vertex-Connected VC problem (where p≥2 is a fixed integer). We obtain an 2O(pk)nO(1)-time algorithm for p-Edge-Connected VC and an 2O(k2)nO(1)-time algorithm for p-Vertex-Connected VC. Thus, like Connected VC, both constrained VC problems are FPT. Furthermore, like Connected VC, neither problem admits a polynomial kernel unless NP ⊆ coNP/poly, which is highly unlikely. We prove however that both problems admit time efficient polynomial sized approximate kernelization schemes. Finally, we describe a 2(p+1)-approximation algorithm for the p-Edge-Connected VC. The proofs for the new VC problems require more sophisticated arguments than for Connected VC. In particular, for the approximation algorithm we use Gomory-Hu trees and for the approximate kernels a result on small-size spanning p-vertex/edge-connected subgraphs of a p-vertex/edge-connected graph by Nishizeki and Poljak (1994) and Nagamochi and Ibaraki (1992).

Role mining seeks to compute a set of roles R, a user-role authorization relation UA and a permission-role authorization relation PA, given a user-permission authorization relation UPA, and is therefore a core problem in the specification of role-based authorization policies. Role mining is known to be hard in general and exact solutions are often impossible to obtain, so there exists an extensive literature on variants of the role mining problem that seek to find approximate solutions and algorithms that use heuristics to find reasonable solutions efficiently.

Recent work has shown that many problems of satisfiability and resiliency in workflows may be viewed as special cases of the authorization policy existence problem (APEP), which returns an authorization policy if one exists and “No” otherwise. However, in many practical settings it would be more useful to obtain a “least bad” policy than just a “No,” where “least bad” is characterized by some numerical value indicating the extent to which the policy violates the base authorization relation and constraints. Accordingly, we introduce the Valued APEP, which returns an authorization policy of minimum weight, where the (non-negative) weight is determined by the constraints violated by the returned solution. We then establish a number of results concerning the parameterized complexity of Valued APEP. We prove that the problem is fixed-parameter tractable (FPT) if the set of constraints satisfies two restrictions, but is intractable if only one of these restrictions holds. (Most constraints known to be of practical use satisfy both restrictions.) Our analysis is based on the novel concept of a user profile. We also introduce a new type of resiliency problem in the context of workflow satisfiability, show how it can be addressed using Valued APEP, and use this to build a set of benchmark instances for Valued APEP. We describe two different formulations of this problem using mixed integer programming and report the results of computational experiments which solve the problem using these formulations as input to a general-purpose solver. Our results show that the formulation which employs the user profile concept, has FPT-like running time and usually significantly outperforms our naive formulation of the problem.

Problems of satisfiability and resiliency in workflows have been widely studied in the last decade. Recent work has shown that many such problems may be viewed as special cases of the authorization policy existence problem (APEP), which returns an authorization policy if one exists and "No'' otherwise. A solution may not exist because of the restrictions imposed by the base authorization relation and constraints that form part of the input to APEP.

Golovach, Paulusma, and Song [ Inform. and Comput., 237 (2014), pp. 204--214] asked to determine the parameterized complexity of the following problems parameterized by $k$: 1. Given a graph $G$, a clique modulator $D$ (a clique modulator is a set of vertices, whose removal results in a clique) of size $k$ for $G$, and a list $L(v)$ of colors for every $v\in V(G)$, decide whether $G$ has a proper list coloring. 2. Given a graph $G$, a clique modulator $D$ of size $k$ for $G$, and a pre-coloring $\lambda_P: X \rightarrow Q$ for $X \subseteq V(G),$ decide whether $\lambda_P$ can be extended to a proper coloring of $G$ using only colors from $Q$. For problem 1 we design an ${\mathcal O}^*(2^k)$-time randomized algorithm and for problem 2 we obtain a kernel with at most $3k$ vertices. Banik et al. [in Proceedings of IWOCA 2019, Springer, Berlin, 2019, pp. 61--69] proved the following problem is fixed-parameter tractable and asked whether it admits a polynomial kernel: Given a graph $G$, an integer $k$, and a list $L(v)$ of exactly $n-k$ colors for every $v \in V(G),$ decide whether there is a proper list coloring for $G$. We obtain a kernel with ${\mathcal O}(k^2)$ vertices and colors and a compression to a variation of the problem with ${\mathcal O}(k)$ vertices and ${\mathcal O}(k^2)$ colors.

User authorization queries in the context of role-based access control have attracted considerable interest in the past 15 years. Such queries are used to determine whether it is possible to allocate a set of roles to a user that enables the user to complete a task, in the sense that all the permissions required to complete the task are assigned to the roles in that set. Answering such a query, in general, must take into account a number of factors, including, but not limited to, the roles to which the user is assigned and constraints on the sets of roles that can be activated. Answering such a query is known to be NP-hard. The presence of multiple parameters and the need to find efficient and exact solutions to the problem suggest that a multi-variate approach will enable us to better understand the complexity of the user authorization query problem (UAQ). In this article, we establish a number of complexity results for UAQ. Specifically, we show the problem remains hard even when quite restrictive conditions are imposed on the structure of the problem. Our fixed-parameter tractable (FPT) results show that we have to use either a parameter with potentially quite large values or quite a restricted version of UAQ. Moreover, our second FPT algorithm is complex and requires sophisticated, state-of-the-art techniques. In short, our results show that it is unlikely that all variants of UAQ that arise in practice can be solved reasonably quickly in general.

Graph-modification problems, where we add/delete a small number of vertices/edges to make the given graph to belong to a simpler graph class, is a well-studied optimization problem in all algorithmic paradigms including classical, approximation and parameterized complexity. Specifically, graph-deletion problems, where one needs to delete at most k vertices to place it in a given non-trivial hereditary (closed under induced subgraphs) graph class, captures several well-studied problems including Vertex Cover, Feedback Vertex Set, Odd Cycle Transveral, Cluster Vertex Deletion, and Perfect Deletion. Investigation into these problems in parameterized complexity has given rise to powerful tools and techniques. While a precise characterization of the graph classes for which the problem is fixed-parameter tractable (FPT) is elusive, it has long been known that if the graph class is characterized by a finite set of forbidden graphs, then the problem is FPT. In this paper, we initiate a study of a natural variation of the problem of deletion to scattered graph classes where we need to delete at most k vertices so that in the resulting graph, each connected component belongs to one of a constant number of graph classes. A simple hitting set based approach is no longer feasible even if each of the graph classes is characterized by finite forbidden sets. As our main result, we show that this problem (in the case where each graph class has a finite forbidden set) is fixed-parameter tractable by a O^*(2^(k^O(1))) algorithm, using a combination of the well-known techniques in parameterized complexity - iterative compression and important separators. Our approach follows closely that of a related problem in the context of satisfiability [Ganian, Ramanujan, Szeider, TAlg 2017], where one wants to find a small backdoor set so that the resulting CSP (constraint satisfaction problem) instance belongs to one of several easy instances of satisfiability. While we follow the main idea from this work, there are some challenges for our problem which we needed to overcome. When there are two graph classes with finite forbidden sets to get to, and if one of the forbidden sets has a path, then we show that the problem has a (better) singly exponential algorithm and a polynomial sized kernel. We also design an efficient FPT algorithm for a special case when one of the graph classes has an infinite forbidden set. Specifically, we give a O^*(4^k) algorithm to determine whether k vertices can be deleted from a given graph so that in the resulting graph, each connected component is a tree (the sparsest connected graph) or a clique (the densest connected graph).

There has been a considerable amount of interest in recent years in the problem of workflow satisfiability, which asks whether the existence of constraints in a workflow specification makes it impossible to allocate authorized users to each step in the workflow. Recent developments have seen the workflow satisfiability problem (WSP) studied in the context of workflow specifications in which the set of steps may vary from one instance of the workflow to another. This, in turn, means that some constraints may only apply to certain workflow instances. Inevitably, WSP becomes more complex for such workflow specifications. Other approaches have considered the possibility of associating costs with the violation of "soft'' constraints and authorizations. Workflow satisfiability in this context becomes a question of minimizing the cost of allocating users to steps in the workflow. In this paper, we introduce new problems, which we believe to be of practical relevance, that combine these approaches. In particular, we consider the question of whether, given a workflow specification with costs and a "budget'', all possible workflow instances have an allocation of users to steps that does not exceed the budget. We design a fixed-parameter tractable algorithm to solve this problem parameterized by the total number of steps, release points and xor branchings.

A key result in the field of kernelization, a subfield of parameterized complexity, states that the classic Disjoint Cycle Packing problem, i.e., finding $k$ vertex disjoint cycles in a given graph $G$, admits no polynomial kernel unless ${\sf NP} \subseteq {\sf coNP} / {\sf poly}$. However, very little is known about this problem beyond the aforementioned kernelization lower bound (within the parameterized complexity framework). In the hope of clarifying the picture and better understanding the types of constraints that separate kernelizable from nonkernelizable variants of Disjoint Cycle Packing, we investigate two relaxations of the problem. The first variant, which we call Almost Disjoint Cycle Packing, introduces a global relaxation parameter $t$. That is, given a graph $G$ and integers $k$ and $t$, the goal is to find at least $k$ distinct cycles such that every vertex of $G$ appears in at most $t$ of the cycles. The second variant, Pairwise Disjoint Cycle Packing, introduces a local relaxation parameter, and we seek at least $k$ distinct cycles such that every two cycles intersect in at most $t$ vertices. While the Pairwise Disjoint Cycle Packing problem admits a polynomial kernel for all $t \geq 1$, the kernelization complexity of Almost Disjoint Cycle Packing reveals an interesting spectrum of upper and lower bounds. In particular, for $t = \frac{k}{c}$, where $c$ could be a function of $k$, we obtain a kernel of size $\mathcal{O}(2^{c^2}k^{7 + c}\log^3 k)$ whenever $c\in o(\sqrt k)$. Thus the kernel size varies from being subexponential when $c\in o(\sqrt k)$, to quasi-polynomial when $c\in o(\log^{\ell} k)$, $\ell \in \mathbb{R}_+$, and polynomial when $c\in \mathcal{O}(1)$. We complement these results for Almost Disjoint Cycle Packing by showing that the problem does not admit a polynomial kernel whenever $t \in \mathcal{O}(k^{\epsilon})$ for any $0 \leq \epsilon < 1$, unless ${\sf NP} \subseteq {\sf coNP} / {\sf poly}$.

A key result in the field of kernelization, a subfield of parameterized complexity, states that the classic Disjoint Cycle Packing problem, i.e. finding k vertex disjoint cycles in a given graph G, admits no polynomial kernel unless NP subseteq coNP/poly. However, very little is known about this problem beyond the aforementioned kernelization lower bound (within the parameterized complexity framework). In the hope of clarifying the picture and better understanding the types of "constraints" that separate "kernelizable" from "non-kernelizable" variants of Disjoint Cycle Packing, we investigate two relaxations of the problem. The first variant, which we call Almost Disjoint Cycle Packing, introduces a "global" relaxation parameter t. That is, given a graph G and integers k and t, the goal is to find at least k distinct cycles such that every vertex of G appears in at most t of the cycles. The second variant, Pairwise Disjoint Cycle Packing, introduces a "local" relaxation parameter and we seek at least k distinct cycles such that every two cycles intersect in at most t vertices. While the Pairwise Disjoint Cycle Packing problem admits a polynomial kernel for all t >= 1, the kernelization complexity of Almost Disjoint Cycle Packing reveals an interesting spectrum of upper and lower bounds. In particular, for t = k/c, where c could be a function of k, we obtain a kernel of size O(2^{c^{2}}*k^{7+c}*log^3(k)) whenever c in o(sqrt(k))). Thus the kernel size varies from being sub-exponential when c in o(sqrt(k)), to quasipolynomial when c in o(log^l(k)), l in R_+, and polynomial when c in O(1). We complement these results for Almost Disjoint Cycle Packing by showing that the problem does not admit a polynomial kernel whenever t in O(k^{epsilon}), for any 0 <= epsilon < 1.

A feedback vertex set in an undirected graph is a subset of vertices whose removal results in an acyclic graph. It is well-known that the problem of finding a minimum sized (or k sized in case of decision version of) feedback vertex set (FVS) is polynomial time solvable in (sub)-cubic graphs, in pseudo-forests (graphs where each component has at most one cycle) and mock-forests (graph where each vertex is part of at most one cycle). In general graphs, it is known that the problem is NP-Complete, and has an O*((3.619)^k) fixed-parameter algorithm and an O(k^2) kernel where k, the solution size is the parameter. We consider the parameterized and kernelization complexity of feedback vertex set where the parameter is the size of some structure of the input. In particular, we show that * FVS is fixed-parameter tractable, but is unlikely to have polynomial sized kernel when parameterized by the number of vertices of the graph whose degree is at least 4. This answers a question asked in an earlier paper. * When parameterized by k, the number of vertices, whose deletion results in a pseudo-forest, we give an O(k^6) vertices kernel improving from the previously known O(k^{10}) bound. * When parameterized by the number k of vertices, whose deletion results in a mock-d-forest, we give a kernel consisting of O(k^{3d+3}) vertices and prove a lower bound of Omega(k^{d+2}) vertices (under complexity theoretic assumptions). Mock-d-forest for a constant d is a mock-forest where each component has at most d cycles.

Vertex Cover is one of the most well studied problems in the realm of parameterized algorithms and admits a kernel with O(l^2) edges and 2*l vertices. Here, l denotes the size of a vertex cover we are seeking for. A natural question is whether Vertex Cover admits a polynomial kernel (or a parameterized algorithm) with respect to a parameter k, that is, provably smaller than the size of the vertex cover. Jansen and Bodlaender [STACS 2011, TOCS 2013] raised this question and gave a kernel for Vertex Cover of size O(f^3), where f is the size of a feedback vertex set of the input graph. We continue this line of work and study Vertex Cover with respect to a parameter that is always smaller than the solution size and incomparable to the size of the feedback vertex set of the input graph. Our parameter is the number of vertices whose removal results in a graph of maximum degree two. While vertex cover with this parameterization can easily be shown to be fixed-parameter tractable (FPT), we show that it has a polynomial sized kernel. The input to our problem consists of an undirected graph G, S \subseteq V(G) such that |S| = k and G[V(G)\S] has maximum degree at most 2 and a positive integer l. Given (G,S,l), in polynomial time we output an instance (G',S',l') such that |V(G')|<= O(k^5), |E(G')|<= O(k^6) and G has a vertex cover of size at most l if and only if G' has a vertex cover of size at most l'. When G[V(G)\S] has maximum degree at most 1, we improve the known kernel bound from O(k^3) vertices to O(k^2) vertices (and O(k^3) edges). In general, if G[V(G)\S] is simply a collection of cliques of size at most d, then we transform the graph in polynomial time to an equivalent hypergraph with O(k^d) vertices and show that, for d >= 3, a kernel with O(k^{d-epsilon}) vertices is unlikely to exist for any epsilon >0 unless NP is a subset of coNO/poly.