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

Manuel Sorge

Manuel Sorge appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Discrete MathematicsComputational Complexitymath.COData Structures and AlgorithmsComputational GeometryDigital LibrariesMachine LearningSocial and Information Networks

Catalog footprint

What is connected

15works
8topics
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

15 published item(s)

preprint2026arXiv

Exact and Approximate Algorithms for Polytree Learning

Polytrees are a subclass of Bayesian networks that seek to capture the conditional dependencies between a set of $n$ variables as a directed forest and are motivated by their more efficient inference and improved interpretability. Since the problem of learning the best polytree is NP-hard, we study which restrictions make it more tractable by considering for example in-degree bounds, properties of score functions measuring the quality of a polytree, and approximation algorithms. We devise an algorithm that finds the optimal polytree in time $O((2+ε)^n)$ for arbitrarily small $ε> 0$ and any constant in-degree bound $k$, improving over the fastest previously known algorithm of time complexity $O(3^n)$. We further give polynomial-time algorithms for finding a polytree whose score is within a factor of $k$ from the optimal one for arbitrary scores and a factor of $2$ for additive ones. Many of the results are complemented by (nearly) tight lower bounds for either the time complexity or the approximation factors.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Planarizing Graphs and their Drawings by Vertex Splitting

The splitting number of a graph $G=(V,E)$ is the minimum number of vertex splits required to turn $G$ into a planar graph, where a vertex split removes a vertex $v \in V$, introduces two new vertices $v_1, v_2$, and distributes the edges formerly incident to $v$ among its two split copies $v_1, v_2$. The splitting number problem is known to be NP-complete. In this paper we shift focus to the splitting number of graph drawings in $\mathbb R^2$, where the new vertices resulting from vertex splits can be re-embedded into the existing drawing of the remaining graph. We first provide a non-uniform fixed-parameter tractable (FPT) algorithm for the splitting number problem (without drawings). Then we show the NP-completeness of the splitting number problem for graph drawings, even for its two subproblems of (1) selecting a minimum subset of vertices to split and (2) for re-embedding a minimum number of copies of a given set of vertices. For the latter problem we present an FPT algorithm parameterized by the number of vertex splits. This algorithm reduces to a bounded outerplanarity case and uses an intricate dynamic program on a sphere-cut decomposition.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Influence of Dimensions on the Complexity of Computing Decision Trees

A decision tree recursively splits a feature space $\mathbb{R}^{d}$ and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine-learning toolkit for decades. A large body of work treats heuristic algorithms to compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, little is known about the complexity of the underlying computational problem of computing a minimum-size tree for the given training data. We study this problem with respect to the number $d$ of dimensions of the feature space. We show that it can be solved in $O(n^{2d + 1}d)$ time, but under reasonable complexity-theoretic assumptions it is not possible to achieve $f(d) \cdot n^{o(d / \log d)}$ running time, where $n$ is the number of training examples. The problem is solvable in $(dR)^{O(dR)} \cdot n^{1+o(1)}$ time, if there are exactly two classes and $R$ is an upper bound on the number of tree leaves labeled with the first~class.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The role of twins in computing planar supports of hypergraphs

A support or realization of a hypergraph $H$ is a graph $G$ on the same vertex as $H$ such that for each hyperedge of $H$ it holds that its vertices induce a connected subgraph of $G$. 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 $m$ hyperedges to have an $r$-outerplanar support, which depends only on $r$ and $m$. Since all additional twins can be safely removed, we obtain a linear-time algorithm for computing $r$-outerplanar supports for hypergraphs with $m$ hyperedges if $m$ and $r$ are constant; in other words, the problem is fixed-parameter linear-time solvable with respect to the parameters $m$ and $r$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Efficient fully dynamic elimination forests with applications to detecting long paths and cycles

We present a data structure that in a dynamic graph of treedepth at most $d$, which is modified over time by edge insertions and deletions, maintains an optimum-height elimination forest. The data structure achieves worst-case update time $2^{{\cal O}(d^2)}$, which matches the best known parameter dependency in the running time of a static fpt algorithm for computing the treedepth of a graph. This improves a result of Dvořák et al. [ESA 2014], who for the same problem achieved update time $f(d)$ for some non-elementary (i.e. tower-exponential) function $f$. As a by-product, we improve known upper bounds on the sizes of minimal obstructions for having treedepth $d$ from doubly-exponential in $d$ to $d^{{\cal O}(d)}$. As applications, we design new fully dynamic parameterized data structures for detecting long paths and cycles in general graphs. More precisely, for a fixed parameter $k$ and a dynamic graph $G$, modified over time by edge insertions and deletions, our data structures maintain answers to the following queries: - Does $G$ contain a simple path on $k$ vertices? - Does $G$ contain a simple cycle on at least $k$ vertices? In the first case, the data structure achieves amortized update time $2^{{\cal O}(k^2)}$. In the second case, the amortized update time is $2^{{\cal O}(k^4)} + {\cal O}(k \log n)$. In both cases we assume access to a dictionary on the edges of $G$.

0 citations0 reviewsNo code linkedOpen 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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Minimum Shared Edges Problem on Planar Graphs

We study the Minimum Shared Edges problem introduced by Omran et al. [Journal of Combinatorial Optimization, 2015] on planar graphs: Planar MSE asks, given a planar graph G = (V,E), two distinct vertices s,t in V , and two integers p, k, whether there are p s-t paths in G that share at most k edges, where an edges is called shared if it appears in at least two of the p s-t paths. We show that Planar MSE is NP-hard by reduction from Vertex Cover. We make use of a grid-like structure, where the alignment (horizontal/vertical) of the edges in the grid correspond to selection and validation gadgets respectively.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Parameterized Complexity of the Minimum Shared Edges Problem

We study the NP-complete Minimum Shared Edges (MSE) problem. Given an undirected graph, a source and a sink vertex, and two integers p and k, the question is whether there are p paths in the graph connecting the source with the sink and sharing at most k edges. Herein, an edge is shared if it appears in at least two paths. We show that MSE is W[1]-hard when parameterized by the treewidth of the input graph and the number k of shared edges combined. We show that MSE is fixed-parameter tractable with respect to p, but does not admit a polynomial-size kernel (unless NP is contained in coNP/poly). In the proof of the fixed-parameter tractability of MSE parameterized by p, we employ the treewidth reduction technique due to Marx, O'Sullivan, and Razgon [ACM TALG 2013].

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On Kernelization and Approximation for the Vector Connectivity Problem

In the Vector Connectivity problem we are given an undirected graph $G=(V,E)$, a demand function $ϕ\colon V\to\{0,\ldots,d\}$, and an integer $k$. The question is whether there exists a set $S$ of at most $k$ vertices such that every vertex $v\in V\setminus S$ has at least $ϕ(v)$ vertex-disjoint paths to $S$; this abstractly captures questions about placing servers or warehouses relative to demands. The problem is \NP-hard already for instances with $d=4$ (Cicalese et al., arXiv '14), admits a log-factor approximation (Boros et al., Networks '14), and is fixed-parameter tractable in terms of~$k$ (Lokshtanov, unpublished '14). We prove several results regarding kernelization and approximation for Vector Connectivity and the variant Vector $d$-Connectivity where the upper bound $d$ on demands is a fixed constant. For Vector $d$-Connectivity we give a factor $d$-approximation algorithm and construct a vertex-linear kernelization, i.e., an efficient reduction to an equivalent instance with $f(d)k=O(k)$ vertices. For Vector Connectivity we have a factor $\text{opt}$-approximation and we can show that it has no kernelization to size polynomial in $k$ or even $k+d$ unless $\mathsf{NP\subseteq coNP/poly}$, making $f(d)\operatorname{poly}(k)$ optimal for Vector $d$-Connectivity. Finally, we provide a write-up for fixed-parameter tractability of Vector Connectivity($k$) by giving an alternative FPT algorithm based on matroid intersection.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

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

Given a hypergraph $H$, the Planar Support problem asks whether there is a planar graph $G$ on the same vertex set as $H$ such that each hyperedge induces a connected subgraph of $G$. 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 $r$-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.

0 citations0 reviewsNo code linkedOpen 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.

0 citations0 reviewsNo code linkedOpen 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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On Making Directed Graphs Eulerian

A directed graph is called Eulerian, if it contains a tour that traverses every arc in the graph exactly once. We study the problem of Eulerian extension (EE) where a directed multigraph G and a weight function is given and it is asked whether G can be made Eulerian by adding arcs whose total weight does not exceed a given threshold. This problem is motivated through applications in vehicle routing and flowshop scheduling. However, EE is NP-hard and thus we use the parameterized complexity framework to analyze it. In parameterized complexity, the running time of algorithms is considered not only with respect to input length, but also with respect to other properties of the input - called "parameters". Dorn et. al. proved that EE can be solved in O(4^k n^4) time, where k denotes the parameter "number of arcs that have to be added". In this thesis, we analyze EE with respect to the (smaller) parameters "number c of connected components in the input graph" and "sum b over indeg(v) - outdeg(v) for all vertices v in the input graph where this value is positive". We prove that there is an algorithm for EE whose running time is polynomial except for the term 4^(c log(bc^2)). To obtain this result, we make several observations about the sets of arcs that have to be added to the input graph in order to make it Eulerian. We build upon these observations to restate EE in a matching context. This matching formulation of EE might be an important tool to solve the question of whether EE can be solved within running time whose superpolynomial part depends only on c. We also consider polynomial time preprocessing routines for EE and show that these routines cannot yield instances whose size depends polynomially only on either of the parameters b, c, k unless coNP is contained in NP/poly.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Algorithmic Aspects of Golomb Ruler Construction

We consider Golomb rulers and their construction. Common rulers feature marks at every unit measure, distances can often be measured with numerous pairs of marks. On Golomb rulers, for every distance there are at most two marks measuring it. The construction of optimal---with respect to shortest length for given number of marks or maximum number of marks for given length---is nontrivial, various problems regarding this are NP-complete. We give a simplified hardness proof for one of them. We use a hypergraph characterization of rulers and Golomb rulers to illuminate structural properties. This gives rise to a problem kernel in a fixed-parameter approach to a construction problem. We also take a short look at the practical implications of these considerations.

0 citations0 reviewsNo code linkedOpen access