BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

René van Bevern

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

ResearcherUnclaimed source record
Discrete MathematicsData Structures and Algorithmsmath.COmath.OCSocial and Information NetworksDigital LibrariesFormal Languages and Automata Theory

Catalog footprint

Research overview

14works
7topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

14 publications

preprint2022arXiv

The role of twins in computing planar supports of hypergraphs

A support or realization of a hypergraph HH is a graph GG on the same vertex as HH such that for each hyperedge of HH it holds that its vertices induce a connected subgraph of GG. The NP-hard problem of finding a planar support has applications in hypergraph drawing and network design. Previous algorithms for the problem assume that twins -- pairs of vertices that are in precisely the same hyperedges -- can safely be removed from the input hypergraph. We prove that this assumption is generally wrong, yet that the number of twins necessary for a hypergraph to have a planar support only depends on its number of hyperedges. We give an explicit upper bound on the number of twins necessary for a hypergraph with mm hyperedges to have an rr-outerplanar support, which depends only on rr and mm. Since all additional twins can be safely removed, we obtain a linear-time algorithm for computing rr-outerplanar supports for hypergraphs with mm hyperedges if mm and rr are constant; in other words, the problem is fixed-parameter linear-time solvable with respect to the parameters mm and rr.

Open access
preprint2021arXiv

The Hierarchical Chinese Postman Problem: the slightest disorder makes it hard, yet disconnectedness is manageable

The Hierarchical Chinese Postman Problem is finding a shortest traversal of all edges of a graph respecting precedence constraints given by a partial order on classes of edges. We show that the special case with connected classes is NP-hard even on orders decomposable into a chain and an incomparable class. For the case with linearly ordered (possibly disconnected) classes, we get 5/3-approximations and fixed-parameter algorithms by transferring results from the Rural Postman Problem.

Open access
preprint2020arXiv

On approximate data reduction for the Rural Postman Problem: Theory and experiments

Given an undirected graph with edge weights and a subset RR of its edges, the Rural Postman Problem (RPP) is to find a closed walk of minimum total weight containing all edges of RR. We prove that RPP is WK[1]-complete parameterized by the number and cost dd of edges traversed additionally to the required ones. Thus, in particular, RPP instances cannot be polynomial-time compressed to instances of size polynomial in dd unless the polynomial-time hierarchy collapses. In contrast, denoting by b≤2db\leq 2d the number of vertices incident to an odd number of edges of RR and by c≤dc\leq d the number of connected components formed by the edges in RR, we show how to reduce any RPP instance II to an RPP instance I′I' with 2b+O(c/ε)2b+O(c/\varepsilon) vertices in O(n3)O(n^3) time so that any αα-approximate solution for I′I' gives an α(1+ε)α(1+\varepsilon)-approximate solution for II, for any α≥1α\geq 1 and ε>0\varepsilon>0. That is, we provide a polynomial-size approximate kernelization scheme (PSAKS). We experimentally evaluate it on wide-spread benchmark data sets as well as on two real snow plowing instances from Berlin. On instances with few connected components, the number of vertices and required edges is reduced to about 50 %50\,\% at a 1 %1\,\% solution quality loss. We also make first steps towards a PSAKS for the parameter cc.

Open access
preprint2020arXiv

Optimal-size problem kernels for dd-Hitting Set in linear time and space

The known linear-time kernelizations for dd-Hitting Set guarantee linear worst-case running times using a quadratic-size data structure (that is not fully initialized). Getting rid of this data structure, we show that problem kernels of asymptotically optimal size O(kd)O(k^d) for dd-Hitting Set are computable in linear time and space. Additionally, we experimentally compare the linear-time kernelizations for dd-Hitting Set to each other and to a classical data reduction algorithm due to Weihe.

Open access
preprint2020arXiv

Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments

We study an NP-hard problem motivated by energy-efficiently maintaining the connectivity of a symmetric wireless communication network: Given an edge-weighted nn-vertex graph, find a connected spanning subgraph of minimum cost, where the cost is determined by letting each vertex pay the most expensive edge incident to it in the subgraph. On the negative side, we show that o(log⁡n)o(\log n)-approximating the difference dd between the optimal solution cost and a natural lower bound is NP-hard and that, under the Exponential Time Hypothesis, there are no exact algorithms running in 2o(n)2^{o(n)} time or in f(d)⋅nO(1)f(d)\cdot n^{O(1)} time for any computable function ff. Moreover, we show that the special case of connecting cc network components with minimum additional cost generally cannot be polynomial-time reduced to instances of size cO(1)c^{O(1)} unless the polynomial-time hierarchy collapses. On the positive side, we provide an algorithm that reconnects O(log⁡n)O(\log n) connected components with minimum additional cost in polynomial time. These algorithms are motivated by application scenarios of monitoring areas or where an existing sensor network may fall apart into several connected components due to sensor faults. In experiments, the algorithm outperforms CPLEX with known ILP formulations when nn is sufficiently large compared to cc.

Open access
preprint2019arXiv

h-Index Manipulation by Undoing Merges

The h-index is an important bibliographic measure used to assess the performance of researchers. Dutiful researchers merge different versions of their articles in their Google Scholar profile even though this can decrease their h-index. In this article, we study the manipulation of the h-index by undoing such merges. In contrast to manipulation by merging articles (van Bevern et al. [Artif. Intel. 240:19-35, 2016]) such manipulation is harder to detect. We present numerous results on computational complexity (from linear-time algorithms to parameterized computational hardness results) and empirically indicate that at least small improvements of the h-index by splitting merged articles are unfortunately easily achievable.

Open access
preprint2016arXiv

Precedence-constrained scheduling problems parameterized by partial order width

Negatively answering a question posed by Mnich and Wiese (Math. Program. 154(1-2):533-562), we show that P2|prec,pj∈{1,2}p_j{\in}\{1,2\}|Cmax⁡C_{\max}, the problem of finding a non-preemptive minimum-makespan schedule for precedence-constrained jobs of lengths 1 and 2 on two parallel identical machines, is W[2]-hard parameterized by the width of the partial order giving the precedence constraints. To this end, we show that Shuffle Product, the problem of deciding whether a given word can be obtained by interleaving the letters of kk other given words, is W[2]-hard parameterized by kk, thus additionally answering a question posed by Rizzi and Vialette (CSR 2013). Finally, refining a geometric algorithm due to Servakh (Diskretn. Anal. Issled. Oper. 7(1):75-82), we show that the more general Resource-Constrained Project Scheduling problem is fixed-parameter tractable parameterized by the partial order width combined with the maximum allowed difference between the earliest possible and factual starting time of a job.

Open access
preprint2015arXiv

Myhill-Nerode methods for hypergraphs

We give an analog of the Myhill-Nerode methods from formal language theory for hypergraphs and use it to derive the following results for two NP-hard hypergraph problems: * We provide an algorithm for testing whether a hypergraph has cutwidth at most k that runs in linear time for constant k. In terms of parameterized complexity theory, the problem is fixed-parameter linear parameterized by k. * We show that it is not expressible in monadic second-order logic whether a hypergraph has bounded (fractional, generalized) hypertree width. The proof leads us to conjecture that, in terms of parameterized complexity theory, these problems are W[1]-hard parameterized by the incidence treewidth (the treewidth of the incidence graph). Thus, in the form of the Myhill-Nerode theorem for hypergraphs, we obtain a method to derive linear-time algorithms and to obtain indicators for intractability for hypergraph problems parameterized by incidence treewidth. In an appendix, we point out an error and a fix to the proof of the Myhill-Nerode theorem for graphs in Downey and Fellow's book on parameterized complexity.

Open access
preprint2015arXiv

Network-Based Vertex Dissolution

We introduce a graph-theoretic vertex dissolution model that applies to a number of redistribution scenarios such as gerrymandering in political districting or work balancing in an online situation. The central aspect of our model is the deletion of certain vertices and the redistribution of their load to neighboring vertices in a completely balanced way. We investigate how the underlying graph structure, the knowledge of which vertices should be deleted, and the relation between old and new vertex loads influence the computational complexity of the underlying graph problems. Our results establish a clear borderline between tractable and intractable cases.

Open access
preprint2015arXiv

Well-Formed Separator Sequences, with an Application to Hypergraph Drawing

Given a hypergraph HH, the Planar Support problem asks whether there is a planar graph GG on the same vertex set as HH such that each hyperedge induces a connected subgraph of GG. Planar Support is motivated by applications in graph drawing and data visualization. We show that Planar Support is fixed-parameter tractable when parameterized by the number of hyperedges in the input hypergraph and the outerplanarity number of the sought planar graph. To this end, we develop novel structural results for rr-outerplanar triangulated disks, showing that they admit sequences of separators with structural properties enabling data reduction. This allows us to obtain a problem kernel for Planar Support, thus showing its fixed-parameter tractability.

Open access
preprint2014arXiv

Constant-factor approximations for Capacitated Arc Routing without triangle inequality

Given an undirected graph with edge costs and edge demands, the Capacitated Arc Routing problem (CARP) asks for minimum-cost routes for equal-capacity vehicles so as to satisfy all demands. Constant-factor polynomial-time approximation algorithms were proposed for CARP with triangle inequality, while CARP was claimed to be NP-hard to approximate within any constant factor in general. Correcting this claim, we show that any factor α approximation for CARP with triangle inequality yields a factor α approximation for the general CARP.

Open access
preprint2014arXiv

Interval scheduling and colorful independent sets

Numerous applications in scheduling, such as resource allocation or steel manufacturing, can be modeled using the NP-hard Independent Set problem (given an undirected graph and an integer k, find a set of at least k pairwise non-adjacent vertices). Here, one encounters special graph classes like 2-union graphs (edge-wise unions of two interval graphs) and strip graphs (edge-wise unions of an interval graph and a cluster graph), on which Independent Set remains NP-hard but admits constant-ratio approximations in polynomial time. We study the parameterized complexity of Independent Set on 2-union graphs and on subclasses like strip graphs. Our investigations significantly benefit from a new structural "compactness" parameter of interval graphs and novel problem formulations using vertex-colored interval graphs. Our main contributions are: 1. We show a complexity dichotomy: restricted to graph classes closed under induced subgraphs and disjoint unions, Independent Set is polynomial-time solvable if both input interval graphs are cluster graphs, and is NP-hard otherwise. 2. We chart the possibilities and limits of effective polynomial-time preprocessing (also known as kernelization). 3. We extend Halldórsson and Karlsson (2006)'s fixed-parameter algorithm for Independent Set on strip graphs parameterized by the structural parameter "maximum number of live jobs" to show that the problem (also known as Job Interval Selection) is fixed-parameter tractable with respect to the parameter k and generalize their algorithm from strip graphs to 2-union graphs. Preliminary experiments with random data indicate that Job Interval Selection with up to fifteen jobs and 5*10^5 intervals can be solved optimally in less than five minutes.

Open access
preprint2014arXiv

On the Parameterized Complexity of Computing Balanced Partitions in Graphs

A balanced partition is a clustering of a graph into a given number of equal-sized parts. For instance, the Bisection problem asks to remove at most k edges in order to partition the vertices into two equal-sized parts. We prove that Bisection is FPT for the distance to constant cliquewidth if we are given the deletion set. This implies FPT algorithms for some well-studied parameters such as cluster vertex deletion number and feedback vertex set. However, we show that Bisection does not admit polynomial-size kernels for these parameters. For the Vertex Bisection problem, vertices need to be removed in order to obtain two equal-sized parts. We show that this problem is FPT for the number of removed vertices k if the solution cuts the graph into a constant number c of connected components. The latter condition is unavoidable, since we also prove that Vertex Bisection is W[1]-hard w.r.t. (k,c). Our algorithms for finding bisections can easily be adapted to finding partitions into d equal-sized parts, which entails additional running time factors of n^{O(d)}. We show that a substantial speed-up is unlikely since the corresponding task is W[1]-hard w.r.t. d, even on forests of maximum degree two. We can, however, show that it is FPT for the vertex cover number.

Open access
preprint2014arXiv

Towards Optimal and Expressive Kernelization for d-Hitting Set

d-Hitting Set is the NP-hard problem of selecting at most k vertices of a hypergraph so that each hyperedge, all of which have cardinality at most d, contains at least one selected vertex. The applications of d-Hitting Set are, for example, fault diagnosis, automatic program verification, and the noise-minimizing assignment of frequencies to radio transmitters. We show a linear-time algorithm that transforms an instance of d-Hitting Set into an equivalent instance comprising at most O(k^d) hyperedges and vertices. In terms of parameterized complexity, this is a problem kernel. Our kernelization algorithm is based on speeding up the well-known approach of finding and shrinking sunflowers in hypergraphs, which yields problem kernels with structural properties that we condense into the concept of expressive kernelization. We conduct experiments to show that our kernelization algorithm can kernelize instances with more than 10^7 hyperedges in less than five minutes. Finally, we show that the number of vertices in the problem kernel can be further reduced to O(k^{d-1}) with additional O(k^{1.5 d}) processing time by nontrivially combining the sunflower technique with d-Hitting Set problem kernels due to Abu-Khzam and Moser.

Open access

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.