Source author record

Tom C. van der Zanden

Tom C. van der Zanden appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity Computer Science and Game Theory Data Structures and Algorithms math.CO

Catalog footprint

What is connected

4works

4topics

2close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2022arXiv

Efficiently Computing the Shapley Value of Connectivity Games in Low-Treewidth Graphs

The Shapley value is the solution concept in cooperative game theory that is most used in both theoretical as practical settings. Unfortunately, computing the Shapley value is computationally intractable in general. This paper focuses on computing the Shapley value of (weighted) connectivity games. For these connectivity games, that are defined on an underlying (weighted) graph, computing the Shapley value is #P-hard, and thus (likely) intractable even for graphs with a moderate number of vertices. We present an algorithm that can efficiently compute the Shapley value if the underlying graph has bounded treewidth. Next, we apply our algorithm to several real-world (covert) networks. We show that our algorithm can compute exact Shapley values for these networks quickly, whereas in prior work these values could only be approximated using a heuristic method. Finally, it is shown that our algorithm can also compute the Shapley value time efficiently for several larger (artificial) benchmark graphs from the PACE 2018 challenge.

preprint2016arXiv

Improved Lower Bounds for Graph Embedding Problems

In this paper, we give new, tight subexponential lower bounds for a number of graph embedding problems. We introduce two related combinatorial problems, which we call String Crafting and Orthogonal Vector crafting, and show that these cannot be solved in time $2^{o(|s|/\log{|s|})}$, unless the Exponential Time Hypothesis fails. These results are used to obtain simplified hardness results for several graph embedding problems, on more restricted graph classes than previously known: assuming the Exponential Time Hypothesis, there do not exist algorithms that run in $2^{o(n/\log n)}$ time for Subgraph Isomorphism on graphs of pathwidth 1, Induced Subgraph Isomorphism on graphs of pathwidth 1, Graph Minor on graphs of pathwidth 1, Induced Graph Minor on graphs of pathwidth 1, Intervalizing 5-Colored Graphs on trees, and finding a tree or path decomposition with width at most $c$ with a minimum number of bags, for any fixed $c\geq 16$. $2^{Θ(n/\log n)}$ appears to be the "correct" running time for many packing and embedding problems on restricted graph classes, and we think String Crafting and Orthogonal Vector Crafting form a useful framework for establishing lower bounds of this form.

preprint2015arXiv

Parameterized Complexity of Graph Constraint Logic

Graph constraint logic is a framework introduced by Hearn and Demaine, which provides several problems that are often a convenient starting point for reductions. We study the parameterized complexity of Constraint Graph Satisfiability and both bounded and unbounded versions of Nondeterministic Constraint Logic (NCL) with respect to solution length, treewidth and maximum degree of the underlying constraint graph as parameters. As a main result we show that restricted NCL remains PSPACE-complete on graphs of bounded bandwidth, strengthening Hearn and Demaine's framework. This allows us to improve upon existing results obtained by reduction from NCL. We show that reconfiguration versions of several classical graph problems (including independent set, feedback vertex set and dominating set) are PSPACE-complete on planar graphs of bounded bandwidth and that Rush Hour, generalized to $k\times n$ boards, is PSPACE-complete even when $k$ is at most a constant.

preprint2014arXiv

PSPACE-completeness of Bloxorz and of Games with 2-Buttons

Bloxorz is an online puzzle game where players move a 1 by 1 by 2 block by tilting it on a subset of the two dimensional grid. Bloxorz features switches that open and close trapdoors. The puzzle is to move the block from its initial position to an upright position on the destination square. We show that the problem of deciding whether a given Bloxorz level is solvable is PSPACE-complete and that this remains so even when all trapdoors are initially closed or all trapdoors are initially open. We also answer an open question of Viglietta, showing that 2-buttons are sufficient for PSPACE-hardness of general puzzle games. We also examine the hardness of some variants of Bloxorz, including variants where the block is a 1 by 1 by 1 cube, and variants with single-use tiles.