BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Marieke van der Wegen

Marieke van der Wegen contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational ComplexityData Structures and AlgorithmsDiscrete Mathematicsmath.CO

Trust snapshot

Quick read

Trust 15 - UnverifiedVerification L1Unclaimed author
3works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

3 published item(s)

preprint2022arXiv

Problems hard for treewidth but easy for stable gonality

We show that some natural problems that are XNLP-hard (which implies W[t]-hardness for all t) when parameterized by pathwidth or treewidth, become FPT when parameterized by stable gonality, a novel graph parameter based on optimal maps from graphs to trees. The problems we consider are classical flow and orientation problems, such as Undirected Flow with Lower Bounds (which is strongly NP-complete, as shown by Itai), Minimum Maximum Outdegree (for which W[1]-hardness for treewidth was proven by Szeider), and capacitated optimization problems such as Capacitated (Red-Blue) Dominating Set (for which W[1]-hardness was proven by Dom, Lokshtanov, Saurabh and Villanger). Our hardness proofs (that beat existing results) use reduction to a recent XNLP-complete problem (Accepting Non-deterministic Checking Counter Machine). The new easy parameterized algorithms use a novel notion of weighted tree partition with an associated parameter that we call treebreadth, inspired by Seese's notion of tree-partite graphs, as well as techniques from dynamical programming and integer linear programming.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Algorithms for the rainbow vertex coloring problem on graph classes

Given a vertex-colored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. In the Rainbow Vertex Coloring (RVC) problem we want to decide whether the vertices of a given graph can be colored with at most $k$ colors so that the graph becomes rainbow vertex-connected. This problem is known to be NP-complete even in very restricted scenarios, and very few efficient algorithms are known for it. In this work, we give polynomial-time algorithms for RVC on permutation graphs, powers of trees and split strongly chordal graphs. The algorithm for the latter class also works for the strong variant of the problem, where the rainbow vertex paths between each vertex pair must be shortest paths. We complement the polynomial-time solvability results for split strongly chordal graphs by showing that, for any fixed $p\geq 3$ both variants of the problem become NP-complete when restricted to split $(S_3,\ldots,S_p)$-free graphs, where $S_q$ denotes the $q$-sun graph.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Parameterized Complexity of Scheduling Chains of Jobs with Delays

In this paper, we consider the parameterized complexity of the following scheduling problem. We must schedule a number of jobs on $m$ machines, where each job has unit length, and the graph of precedence constraints consists of a set of chains. Each precedence constraint is labelled with an integer that denotes the exact (or minimum) delay between the jobs. We study different cases; delays can be given in unary and in binary, and the case that we have a single machine is discussed separately. We consider the complexity of this problem parameterized by the number of chains, and by the thickness of the instance, which is the maximum number of chains whose intervals between release date and deadline overlap. We show that this scheduling problem with exact delays in unary is $W[t]$-hard for all $t$, when parameterized by the thickness, even when we have a single machine ($m = 1$). When parameterized by the number of chains, this problem is $W[1]$-complete when we have a single or a constant number of machines, and $W[2]$-complete when the number of machines is a variable. The problem with minimum delays, given in unary, parameterized by the number of chains (and as a simple corollary, also when parameterized by the thickness) is $W[1]$-hard for a single or a constant number of machines, and $W[2]$-hard when the number of machines is variable. With a dynamic programming algorithm, one can show membership in XP for exact and minimum delays in unary, for any number of machines, when parameterized by thickness or number of chains. For a single machine, with exact delays in binary, parameterized by the number of chains, membership in XP can be shown with branching and solving a system of difference constraints. For all other cases for delays in binary, membership in XP is open.

0 citations0 reviewsNo code linkedOpen access