Source author record

Magnus Wahlstrom

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Cryptography and Security Computer Science and Game Theory Discrete Mathematics math.CO

Catalog footprint

Research overview

8works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms

We introduce and study two natural generalizations of the Connected VertexCover (VC) problem: the $p$ -Edge-Connected and $p$ -Vertex-Connected VC problem (where $p \geq 2$ is a fixed integer). Like Connected VC, both new VC problems are FPT, but do not admit a polynomial kernel unless $NP \subseteq coNP/poly$ , which is highly unlikely. We prove however that both problems admit time efficient polynomial sized approximate kernelization schemes. We obtain an $O(2^{O(pk)}n^{O(1)})$ -time algorithm for the $p$ -Edge-Connected VC and an $O(2^{O(k^2)}n^{O(1)})$ -time algorithm for the $p$ -Vertex-Connected VC. 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 subgraph of a $p$ -vertex/edge-connected graph obtained independently by Nishizeki and Poljak (1994) and Nagamochi and Ibaraki (1992).

preprint2016arXiv

Acyclicity in Edge-Colored Graphs

A walk $W$ in edge-colored graphs is called properly colored (PC) if every pair of consecutive edges in $W$ is of different color. We introduce and study five types of PC acyclicity in edge-colored graphs such that graphs of PC acyclicity of type $i$ is a proper superset of graphs of acyclicity of type $i+1$ , $i=1,2,3,4.$ The first three types are equivalent to the absence of PC cycles, PC trails, and PC walks, respectively. While graphs of types 1, 2 and 3 can be recognized in polynomial time, the problem of recognizing graphs of type 4 is, somewhat surprisingly, NP-hard even for 2-edge-colored graphs (i.e., when only two colors are used). The same problem with respect to type 5 is polynomial-time solvable for all edge-colored graphs. Using the five types, we investigate the border between intractability and tractability for the problems of finding the maximum number of internally vertex disjoint PC paths between two vertices and the minimum number of vertices to meet all PC paths between two vertices.

preprint2015arXiv

On the Workflow Satisfiability Problem with Class-Independent Constraints

A workflow specification defines sets of steps and users. An authorization policy determines for each user a subset of steps the user is allowed to perform. Other security requirements, such as separation-of-duty, impose constraints on which subsets of users may perform certain subsets of steps. The \emph{workflow satisfiability problem} (WSP) is the problem of determining whether there exists an assignment of users to workflow steps that satisfies all such authorizations and constraints. An algorithm for solving WSP is important, both as a static analysis tool for workflow specifications, and for the construction of run-time reference monitors for workflow management systems. Given the computational difficulty of WSP, it is important, particularly for the second application, that such algorithms are as efficient as possible. We introduce class-independent constraints, enabling us to model scenarios where the set of users is partitioned into groups, and the identities of the user groups are irrelevant to the satisfaction of the constraint. We prove that solving WSP is fixed-parameter tractable (FPT) for this class of constraints and develop an FPT algorithm that is useful in practice. We compare the performance of the FPT algorithm with that of SAT4J (a pseudo-Boolean SAT solver) in computational experiments, which show that our algorithm significantly outperforms SAT4J for many instances of WSP. User-independent constraints, a large class of constraints including many practical ones, are a special case of class-independent constraints for which WSP was proved to be FPT (Cohen {\em et al.}, J. Artif. Intel. Res. 2014). Thus our results considerably extend our knowledge of the fixed-parameter tractability of WSP.

preprint2015arXiv

Structural Parameterizations of the Mixed Chinese Postman Problem

In the Mixed Chinese Postman Problem (MCPP), given a weighted mixed graph $G$ ( $G$ may have both edges and arcs), our aim is to find a minimum weight closed walk traversing each edge and arc at least once. The MCPP parameterized by the number of edges in $G$ or the number of arcs in $G$ is fixed-parameter tractable as proved by van Bevern {\em et al.} (in press) and Gutin, Jones and Sheng (ESA 2014), respectively. In this paper, we consider the unweighted version of MCPP. Solving an open question of van Bevern {\em et al.} (in press), we show that somewhat unexpectedly MCPP parameterized by the (undirected) treewidth of $G$ is W[1]-hard. In fact, we prove that even the MCPP parameterized by the pathwidth of $G$ is W[1]-hard. On the positive side, we show that the unweighted version of MCPP parameterized by tree-depth is fixed-parameter tractable. We are unaware of any natural graph parameters between pathwidth and tree-depth and so our results provide a dichotomy of the complexity of MCPP. Furthermore, we believe that MCPP is the first problem known to be W[1]-hard with respect to treewidth but FPT with respect to tree-depth.

preprint2015arXiv

Tight Lower Bounds for the Workflow Satisfiability Problem Based on the Strong Exponential Time Hypothesis

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 equals constraints. Since the number of steps $k$ is relatively small in practice, Wang and Li (2010) introduced a parametrisation of WSP by $k$ . Wang and Li (2010) 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) and Cohen et al. (2014) designed FPT algorithms of running time $O^*(2^{k})$ and $O^*(2^{k\log_2 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^*(2^{ck})$ and $O^*(2^{ck\log_2 k})$ for the two restrictions of WSP, respectively, with any $c<1$ , unless the Strong Exponential Time Hypothesis fails.

preprint2014arXiv

Parameterized Directed $k$ -Chinese Postman Problem and $k$ Arc-Disjoint Cycles Problem on Euler Digraphs

In the Directed $k$ -Chinese Postman Problem ( $k$ -DCPP), we are given a connected weighted digraph $G$ and asked to find $k$ non-empty closed directed walks covering all arcs of $G$ such that the total weight of the walks is minimum. Gutin, Muciaccia and Yeo (Theor. Comput. Sci. 513 (2013) 124--128) asked for the parameterized complexity of $k$ -DCPP when $k$ is the parameter. We prove that the $k$ -DCPP is fixed-parameter tractable. We also consider a related problem of finding $k$ arc-disjoint directed cycles in an Euler digraph, parameterized by $k$ . Slivkins (ESA 2003) showed that this problem is W[1]-hard for general digraphs. Generalizing another result by Slivkins, we prove that the problem is fixed-parameter tractable for Euler digraphs. The corresponding problem on vertex-disjoint cycles in Euler digraphs remains W[1]-hard even for Euler digraphs.

preprint2014arXiv

Parameterized Rural Postman Problem

The Directed Rural Postman Problem (DRPP) can be formulated as follows: given a strongly connected directed multigraph $D=(V,A)$ with nonnegative integral weights on the arcs, a subset $R$ of $A$ and a nonnegative integer $\ell$ , decide whether $D$ has a closed directed walk containing every arc of $R$ and of total weight at most $\ell$ . Let $k$ be the number of weakly connected components in the the subgraph of $D$ induced by $R$ . Sorge et al. (2012) ask whether the DRPP is fixed-parameter tractable (FPT) when parameterized by $k$ , i.e., whether there is an algorithm of running time $O^*(f(k))$ where $f$ is a function of $k$ only and the $O^*$ notation suppresses polynomial factors. Sorge et al. (2012) note that this question is of significant practical relevance and has been open for more than thirty years. Using an algebraic approach, we prove that DRPP has a randomized algorithm of running time $O^*(2^k)$ when $\ell$ is bounded by a polynomial in the number of vertices in $D$ . We also show that the same result holds for the undirected version of DRPP, where $D$ is a connected undirected multigraph.

preprint2010arXiv

Parameterized Two-Player Nash Equilibrium

We study the computation of Nash equilibria in a two-player normal form game from the perspective of parameterized complexity. Recent results proved hardness for a number of variants, when parameterized by the support size. We complement those results, by identifying three cases in which the problem becomes fixed-parameter tractable. These cases occur in the previously studied settings of sparse games and unbalanced games as well as in the newly considered case of locally bounded treewidth games that generalizes both these two cases.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Magnus Wahlstrom

Research overview

Is this your work?

8 publications

p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms

Acyclicity in Edge-Colored Graphs

On the Workflow Satisfiability Problem with Class-Independent Constraints

Structural Parameterizations of the Mixed Chinese Postman Problem

Tight Lower Bounds for the Workflow Satisfiability Problem Based on the Strong Exponential Time Hypothesis

Parameterized Directed $k$ -Chinese Postman Problem and $k$ Arc-Disjoint Cycles Problem on Euler Digraphs

Parameterized Rural Postman Problem

Parameterized Two-Player Nash Equilibrium

See the researcher in context

Building this map preview

Magnus Wahlstrom

Research overview

Is this your work?

8 publications

p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms

Acyclicity in Edge-Colored Graphs

On the Workflow Satisfiability Problem with Class-Independent Constraints

Structural Parameterizations of the Mixed Chinese Postman Problem

Tight Lower Bounds for the Workflow Satisfiability Problem Based on the Strong Exponential Time Hypothesis

Parameterized Directed kkk-Chinese Postman Problem and kkk Arc-Disjoint Cycles Problem on Euler Digraphs

Parameterized Rural Postman Problem

Parameterized Two-Player Nash Equilibrium

See the researcher in context

Building this map preview

Parameterized Directed $k$ -Chinese Postman Problem and $k$ Arc-Disjoint Cycles Problem on Euler Digraphs