BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Erik Jan van Leeuwen

Erik Jan van Leeuwen appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsDiscrete MathematicsComputational Complexitymath.COComputational Geometry

Catalog footprint

What is connected

14works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

14 published item(s)

preprint2022arXiv

Induced Disjoint Paths and Connected Subgraphs for $H$-Free Graphs

Paths $P_1,\ldots, P_k$ in a graph $G=(V,E)$ are mutually induced if any two distinct $P_i$ and $P_j$ have neither common vertices nor adjacent vertices. The Induced Disjoint Paths problem is to decide if a graph $G$ with $k$ pairs of specified vertices $(s_i,t_i)$ contains $k$ mutually induced paths $P_i$ such that each $P_i$ starts from $s_i$ and ends at $t_i$. This is a classical graph problem that is NP-complete even for $k=2$. We introduce a natural generalization, Induced Disjoint Connected Subgraphs: instead of connecting pairs of terminals, we must connect sets of terminals. We give almost-complete dichotomies of the computational complexity of both problems for H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. Finally, we give a complete classification of the complexity of the second problem if the number k of terminal sets is fixed, that is, not part of the input.

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

Upper Bounding Rainbow Connection Number by Forest Number

A path in an edge-colored graph is rainbow if no two edges of it are colored the same, and the graph is rainbow-connected if there is a rainbow path between each pair of its vertices. The minimum number of colors needed to rainbow-connect a graph $G$ is the rainbow connection number of $G$, denoted by $\text{rc}(G)$. A simple way to rainbow-connect a graph $G$ is to color the edges of a spanning tree with distinct colors and then re-use any of these colors to color the remaining edges of $G$. This proves that $\text{rc}(G) \le |V(G)|-1$. We ask whether there is a stronger connection between tree-like structures and rainbow coloring than that is implied by the above trivial argument. For instance, is it possible to find an upper bound of $t(G) -1$ for $\text{rc}(G)$, where $t(G)$ is the number of vertices in the largest induced tree of $G$? The answer turns out to be negative, as there are counter-examples that show that even $c\cdot t(G)$ is not an upper bound for $\text{rc}(G))$ for any given constant $c$. In this work we show that if we consider the forest number $f(G)$, the number of vertices in a maximum induced forest of $G$, instead of $t(G)$, then surprisingly we do get an upper bound. More specifically, we prove that $\text{rc}(G) \leq f(G) + 2$. Our result indicates a stronger connection between rainbow connection and tree-like structures than that was suggested by the simple spanning tree based upper bound.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Approximation and parameterized algorithms for geometric independent set with shrinking

Consider the Maximum Weight Independent Set problem for rectangles: given a family of weighted axis-parallel rectangles in the plane, find a maximum-weight subset of non-overlapping rectangles. The problem is notoriously hard both in the approximation and in the parameterized setting. The best known polynomial-time approximation algorithms achieve super-constant approximation ratios [Chalermsook and Chuzhoy, SODA 2009; Chan and Har-Peled, Discrete & Comp. Geometry 2012], even though there is a $(1+ε)$-approximation running in quasi-polynomial time [Adamaszek and Wiese, FOCS 2013; Chuzhoy and Ene, FOCS 2016]. When parameterized by the target size of the solution, the problem is $\mathsf{W}[1]$-hard even in the unweighted setting [Marx, FOCS 2007]. To achieve tractability, we study the following shrinking model: one is allowed to shrink each input rectangle by a multiplicative factor $1-δ$ for some fixed $δ>0$, but the performance is still compared against the optimal solution for the original, non-shrunk instance. We prove that in this regime, the problem admits an EPTAS with running time $f(ε,δ)\cdot n^{\mathcal{O}(1)}$, and an FPT algorithm with running time $f(k,δ)\cdot n^{\mathcal{O}(1)}$, in the setting where a maximum-weight solution of size at most $k$ is to be computed. This improves and significantly simplifies a PTAS given earlier for this problem [Adamaszek et al., APPROX 2015], and provides the first parameterized results for the shrinking model. Furthermore, we explore kernelization in the shrinking model, by giving efficient kernelization procedures for several variants of the problem when the input rectangles are squares.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Complexity of Metric Dimension on Planar Graphs

The metric dimension of a graph $G$ is the size of a smallest subset $L \subseteq V(G)$ such that for any $x,y \in V(G)$ with $x\not= y$ there is a $z \in L$ such that the graph distance between $x$ and $z$ differs from the graph distance between $y$ and $z$. Even though this notion has been part of the literature for almost 40 years, prior to our work the computational complexity of determining the metric dimension of a graph was still very unclear. In this paper, we show tight complexity boundaries for the Metric Dimension problem. We achieve this by giving two complementary results. First, we show that the Metric Dimension problem on planar graphs of maximum degree $6$ is NP-complete. Then, we give a polynomial-time algorithm for determining the metric dimension of outerplanar graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Independence and Efficient Domination on $P_6$-free Graphs

In the Independent set problem, the input is a graph $G$, every vertex has a non-negative integer weight, and the task is to find a set $S$ of pairwise non-adjacent vertices, maximizing the total weight of the vertices in $S$. We give an $n^{O (\log^2 n)}$ time algorithm for this problem on graphs excluding the path $P_6$ on $6$ vertices as an induced subgraph. Currently, there is no constant $k$ known for which Independent Set on $P_{k}$-free graphs becomes NP-complete, and our result implies that if such a $k$ exists, then $k > 6$ unless all problems in NP can be decided in (quasi)polynomial time. Using the combinatorial tools that we develop for the above algorithm, we also give a polynomial-time algorithm for Efficient Dominating Set on $P_6$-free graphs. In this problem, the input is a graph $G$, every vertex has an integer weight, and the objective is to find a set $S$ of maximum weight such that every vertex in $G$ has exactly one vertex in $S$ in its closed neighborhood, or to determine that no such set exists. Prior to our work, the class of $P_6$-free graphs was the only class of graphs defined by a single forbidden induced subgraph on which the computational complexity of Efficient Dominating Set was unknown.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Parameterized Complexity Dichotomy for Steiner Multicut

The Steiner Multicut problem asks, given an undirected graph G, terminals sets T1,...,Tt $\subseteq$ V(G) of size at most p, and an integer k, whether there is a set S of at most k edges or nodes s.t. of each set Ti at least one pair of terminals is in different connected components of G \ S. This problem generalizes several graph cut problems, in particular the Multicut problem (the case p = 2), which is fixed-parameter tractable for the parameter k [Marx and Razgon, Bousquet et al., STOC 2011]. We provide a dichotomy of the parameterized complexity of Steiner Multicut. That is, for any combination of k, t, p, and the treewidth tw(G) as constant, parameter, or unbounded, and for all versions of the problem (edge deletion and node deletion with and without deletable terminals), we prove either that the problem is fixed-parameter tractable or that the problem is hard (W[1]-hard or even (para-)NP-complete). We highlight that: - The edge deletion version of Steiner Multicut is fixed-parameter tractable for the parameter k+t on general graphs (but has no polynomial kernel, even on trees). We present two proofs: one using the randomized contractions technique of Chitnis et al, and one relying on new structural lemmas that decompose the Steiner cut into important separators and minimal s-t cuts. - In contrast, both node deletion versions of Steiner Multicut are W[1]-hard for the parameter k+t on general graphs. - All versions of Steiner Multicut are W[1]-hard for the parameter k, even when p=3 and the graph is a tree plus one node. Hence, the results of Marx and Razgon, and Bousquet et al. do not generalize to Steiner Multicut. Since we allow k, t, p, and tw(G) to be any constants, our characterization includes a dichotomy for Steiner Multicut on trees (for tw(G) = 1), and a polynomial time versus NP-hardness dichotomy (by restricting k,t,p,tw(G) to constant or unbounded).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Polynomial kernelization for removing induced claws and diamonds

A graph is called (claw,diamond)-free if it contains neither a claw (a $K_{1,3}$) nor a diamond (a $K_4$ with an edge removed) as an induced subgraph. Equivalently, (claw,diamond)-free graphs can be characterized as line graphs of triangle-free graphs, or as linear dominoes, i.e., graphs in which every vertex is in at most two maximal cliques and every edge is in exactly one maximal clique. In this paper we consider the parameterized complexity of the (claw,diamond)-free Edge Deletion problem, where given a graph $G$ and a parameter $k$, the question is whether one can remove at most $k$ edges from $G$ to obtain a (claw,diamond)-free graph. Our main result is that this problem admits a polynomial kernel. We complement this finding by proving that, even on instances with maximum degree $6$, the problem is NP-complete and cannot be solved in time $2^{o(k)}\cdot |V(G)|^{O(1)}$ unless the Exponential Time Hypothesis fail

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Induced Disjoint Paths in Circular-Arc Graphs in Linear Time

The Induced Disjoint Paths problem is to test whether a graph G with k distinct pairs of vertices (s_i,t_i) contains paths P_1,...,P_k such that P_i connects s_i and t_i for i=1,...,k, and P_i and P_j have neither common vertices nor adjacent vertices (except perhaps their ends) for 1<=i < j<=k. We present a linear-time algorithm for Induced Disjoint Paths on circular-arc graphs. For interval graphs, we exhibit a linear-time algorithm for the generalization of Induced Disjoint Paths where the pairs (s_i,t_i) are not necessarily distinct.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Induced Disjoint Paths in Claw-Free Graphs

Paths P1,...,Pk in a graph G=(V,E) are said to be mutually induced if for any 1 <= i < j <= k, Pi and Pj have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to test whether a graph G with k pairs of specified vertices (si,ti) contains k mutually induced paths Pi such that Pi connects si and ti for i=1,...,k. We show that this problem is fixed-parameter tractable for claw-free graphs when parameterized by k. Several related problems, such as the k-in-a-Path problem, are proven to be fixed-parameter tractable for claw-free graphs as well. We show that an improvement of these results in certain directions is unlikely, for example by noting that the Induced Disjoint Paths problem cannot have a polynomial kernel for line graphs (a type of claw-free graphs), unless NP \subseteq coNP/poly. Moreover, the problem becomes NP-complete, even when k=2, for the more general class of K_1,4-free graphs. Finally, we show that the n^O(k)-time algorithm of Fiala et al. for testing whether a claw-free graph contains some k-vertex graph H as a topological induced minor is essentially optimal by proving that this problem is W[1]-hard even if G and H are line graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs

The Induced Graph Matching problem asks to find k disjoint induced subgraphs isomorphic to a given graph H in a given graph G such that there are no edges between vertices of different subgraphs. This problem generalizes the classical Independent Set and Induced Matching problems, among several other problems. We show that Induced Graph Matching is fixed-parameter tractable in k on claw-free graphs when H is a fixed connected graph, and even admits a polynomial kernel when H is a complete graph. Both results rely on a new, strong, and generic algorithmic structure theorem for claw-free graphs. Complementing the above positive results, we prove W[1]-hardness of Induced Graph Matching on graphs excluding K_1,4 as an induced subgraph, for any fixed complete graph H. In particular, we show that Independent Set is W[1]-hard on K_1,4-free graphs. Finally, we consider the complexity of Induced Graph Matching on a large subclass of claw-free graphs, namely on proper circular-arc graphs. We show that the problem is either polynomial-time solvable or NP-complete, depending on the connectivity of H and the structure of G.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Reducing a Target Interval to a Few Exact Queries

Many combinatorial problems involving weights can be formulated as a so-called ranged problem. That is, their input consists of a universe $U$, a (succinctly-represented) set family $\mathcal{F} \subseteq 2^{U}$, a weight function $ω:U \rightarrow \{1,...,N\}$, and integers $0 \leq l \leq u \leq \infty$. Then the problem is to decide whether there is an $X \in \mathcal{F}$ such that $l \leq \sum_{e \in X}ω(e) \leq u$. Well-known examples of such problems include Knapsack, Subset Sum, Maximum Matching, and Traveling Salesman. In this paper, we develop a generic method to transform a ranged problem into an exact problem (i.e. a ranged problem for which $l=u$). We show that our method has several intriguing applications in exact exponential algorithms and parameterized complexity, namely: - In exact exponential algorithms, we present new insight into whether Subset Sum and Knapsack have efficient algorithms in both time and space. In particular, we show that the time and space complexity of Subset Sum and Knapsack are equivalent up to a small polynomial factor in the input size. We also give an algorithm that solves sparse instances of Knapsack efficiently in terms of space and time. - In parameterized complexity, we present the first kernelization results on weighted variants of several well-known problems. In particular, we show that weighted variants of Vertex Cover, Dominating Set, Traveling Salesman and Knapsack all admit polynomial randomized Turing kernels when parameterized by $|U|$. Curiously, our method relies on a technique more commonly found in approximation algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

k-Gap Interval Graphs

We initiate the study of a new parameterization of graph problems. In a multiple interval representation of a graph, each vertex is associated to at least one interval of the real line, with an edge between two vertices if and only if an interval associated to one vertex has a nonempty intersection with an interval associated to the other vertex. A graph on n vertices is a k-gap interval graph if it has a multiple interval representation with at most n+k intervals in total. In order to scale up the nice algorithmic properties of interval graphs (where k=0), we parameterize graph problems by k, and find FPT algorithms for several problems, including Feedback Vertex Set, Dominating Set, Independent Set, Clique, Clique Cover, and Multiple Interval Transversal. The Coloring problem turns out to be W[1]-hard and we design an XP algorithm for the recognition problem.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Parameterized Complexity of Firefighting Revisited

The Firefighter problem is to place firefighters on the vertices of a graph to prevent a fire with known starting point from lighting up the entire graph. In each time step, a firefighter may be permanently placed on an unburned vertex and the fire spreads to its neighborhood in the graph in so far no firefighters are protecting those vertices. The goal is to let as few vertices burn as possible. This problem is known to be NP-complete, even when restricted to bipartite graphs or to trees of maximum degree three. Initial study showed the Firefighter problem to be fixed-parameter tractable on trees in various parameterizations. We complete these results by showing that the problem is in FPT on general graphs when parameterized by the number of burned vertices, but has no polynomial kernel on trees, resolving an open problem. Conversely, we show that the problem is W[1]-hard when parameterized by the number of unburned vertices, even on bipartite graphs. For both parameterizations, we additionally give refined algorithms on trees, improving on the running times of the known algorithms.

0 citations0 reviewsNo code linkedOpen access