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

André Nichterlein

André Nichterlein contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDiscrete Mathematicsmath.COSocial and Information Networks

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
11works
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

11 published item(s)

preprint2026arXiv

Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density

We study $τ$-Bounded-Density Edge Deletion ($τ$-BDED), where given an undirected graph $G$, the task is to remove as few edges as possible to obtain a graph $G&#39;$ where no subgraph of $G&#39;$ has density more than $τ$. The density of a (sub)graph is the number of edges divided by the number of vertices. This problem was recently introduced and shown to be NP-hard for $τ\in \{2/3, 3/4, 1 + 1/25\}$, but polynomial-time solvable for $τ\in \{0,1/2,1\}$ [Bazgan et al., JCSS 2025]. We provide a complete dichotomy with respect to the target density $τ$: 1. If $2τ\in \mathbb{N}$ (half-integral target density) or $τ< 2/3$, then $τ$-BDED is polynomial-time solvable. 2. Otherwise, $τ$-BDED is NP-hard. We complement the NP-hardness with fixed-parameter tractability with respect to the treewidth of $G$. Moreover, for integral target density $τ\in \mathbb{N}$, we show $τ$-BDED to be solvable in randomized $O(m^{1 + o(1)})$ time. Our algorithmic results are based on a reduction to a new general flow problem on restricted networks that, depending on $τ$, can be solved via Maximum s-t-Flow or General Factors. We believe this connection between these variants of flow and matching to be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions

We provide a general framework to exclude parameterized running times of the form $O(\ell^β+ n^γ)$ for problems that have polynomial running time lower bounds under hypotheses from fine-grained complexity. Our framework is based on cross-compositions from parameterized complexity. We (conditionally) exclude running times of the form $O(\ell^{γ/{(γ-1)} - ε} + n^γ)$ for any $1<γ<2$ and $ε>0$ for the following problems: - Longest Common Subsequence: Given two length-$n$ strings and $\ell\in\mathbb{N}$, is there a common subsequence of length $\ell$? - Discrete Fréchet Distance: Given two lists of $n$ points each and $k\in \mathbb{N}$, is the Fréchet distance of the lists at most $k$? Here $\ell$ is the maximum number of points which one list is ahead of the other list in an optimum traversal. Moreover, we exclude running times $O(\ell^{{2γ}/{(γ-1)}-ε} + n^γ)$ for any $1<γ<3$ and $ε>0$ for: - Negative Triangle: Given an edge-weighted graph with $n$ vertices, is there a triangle whose sum of edge-weights is negative? Here $\ell$ is the order of a maximum connected component. - Triangle Collection: Given a vertex-colored graph with $n$ vertices, is there for each triple of colors a triangle whose vertices have these three colors? Here $\ell$ is the order of a maximum connected component. - 2nd Shortest Path: Given an $n$-vertex edge-weighted directed graph, two vertices $s$ and $t$, and $k \in \mathbb{N}$, has the second longest $s$-$t$-path length at most $k$? Here $\ell$ is the directed feedback vertex set. Except for 2nd Shortest Path all these running time bounds are tight, that is, algorithms with running time $O(\ell^{γ/{(γ-1)}} + n^γ)$ for any $1 < γ< 2$ and $O(\ell^{{2γ}/{(γ-1)}} + n^γ)$ for any $1 < γ< 3$, respectively, are known.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

There and Back Again: On Applying Data Reduction Rules by Undoing Others

Data reduction rules are an established method in the algorithmic toolbox for tackling computationally challenging problems. A data reduction rule is a polynomial-time algorithm that, given a problem instance as input, outputs an equivalent, typically smaller instance of the same problem. The application of data reduction rules during the preprocessing of problem instances allows in many cases to considerably shrink their size, or even solve them directly. Commonly, these data reduction rules are applied exhaustively and in some fixed order to obtain irreducible instances. It was often observed that by changing the order of the rules, different irreducible instances can be obtained. We propose to &#34;undo&#34; data reduction rules on irreducible instances, by which they become larger, and then subsequently apply data reduction rules again to shrink them. We show that this somewhat counter-intuitive approach can lead to significantly smaller irreducible instances. The process of undoing data reduction rules is not limited to &#34;rolling back&#34; data reduction rules applied to the instance during preprocessing. Instead, we formulate so-called backward rules, which essentially undo a data reduction rule, but without using any information about which data reduction rules were applied to it previously. In particular, based on the example of Vertex Cover we propose two methods applying backward rules to shrink the instances further. In our experiments we show that this way smaller irreducible instances consisting of real-world graphs from the SNAP and DIMACS datasets can be computed.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Using a geometric lens to find k disjoint shortest paths

Given an undirected $n$-vertex graph and $k$ pairs of terminal vertices $(s_1,t_1), \ldots, (s_k,t_k)$, the $k$-Disjoint Shortest Paths ($k$-DSP)-problem asks whether there are $k$ pairwise vertex-disjoint paths $P_1,\ldots, P_k$ such that $P_i$ is a shortest $s_i$-$t_i$-path for each $i \in [k]$. Recently, Lochet [SODA 2021] provided an algorithm that solves $k$-DSP in $n^{O(k^{5^k})}$ time, answering a 20-year old question about the computational complexity of $k$-DSP for constant $k$. On the one hand, we present an improved $n^{O(k!k)}$-time algorithm based on a novel geometric view on this problem. For the special case $k=2$ on $m$-edge graphs, we show that the running time can be further reduced to $O(nm)$ by small modifications of the algorithm and a refined analysis. On the other hand, we show that $k$-DSP is W[1]-hard with respect to $k$, showing that the dependency of the degree of the polynomial running time on the parameter $k$ is presumably unavoidable.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An Adaptive Version of Brandes&#39; Algorithm for Betweenness Centrality

Betweenness centrality---measuring how many shortest paths pass through a vertex---is one of the most important network analysis concepts for assessing the relative importance of a vertex. The well-known algorithm of Brandes [J. Math. Sociol.~&#39;01] computes, on an $n$-vertex and $m$-edge graph, the betweenness centrality of all vertices in $O(nm)$ worst-case time. In later work, significant empirical speedups were achieved by preprocessing degree-one vertices and by graph partitioning based on cut vertices. We contribute an algorithmic treatment of degree-two vertices, which turns out to be much richer in mathematical structure than the case of degree-one vertices. Based on these three algorithmic ingredients, we provide a strengthened worst-case running time analysis for betweenness centrality algorithms. More specifically, we prove an adaptive running time bound $O(kn)$, where $k < m$ is the size of a minimum feedback edge set of the input graph.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Detecting and Enumerating Small Induced Subgraphs in $c$-Closed Graphs

Fox et al. [SIAM J. Comp. 2020] introduced a new parameter, called $c$-closure, for a parameterized study of clique enumeration problems. A graph $G$ is $c$-closed if every pair of vertices with at least $c$ common neighbors is adjacent. The $c$-closure of $G$ is the smallest $c$ such that $G$ is $c$-closed. We systematically explore the impact of $c$-closure on the computational complexity of detecting and enumerating small induced subgraphs. More precisely, for each graph $H$ on three or four vertices, we investigate parameterized polynomial-time algorithms for detecting $H$ and for enumerating all occurrences of $H$ in a given $c$-closed graph.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Efficient Computation of Optimal Temporal Walks under Waiting-Time Constraints

Node connectivity plays a central role in temporal network analysis. We provide a comprehensive study of various concepts of walks in temporal graphs, that is, graphs with fixed vertex sets but edge sets changing over time. Taking into account the temporal aspect leads to a rich set of optimization criteria for &#34;shortest&#34; walks. Extending and significantly broadening state-of-the-art work of Wu et al. [IEEE TKDE 2016], we provide an algorithm for computing optimal walks that is capable to deal with various optimization criteria and any linear combination of these. It runs in $O (|V| + |E| \log |E|)$ time where $|V|$ is the number of vertices and $|E|$ is the number of time edges. A central distinguishing factor to Wu et al.&#39;s work is that our model allows to, motivated by real-world applications, respect waiting-time constraints for vertices, that is, the minimum and maximum waiting time allowed in intermediate vertices of a walk. Moreover, other than Wu et al. our algorithm also allows to search for walks that pass multiple subsequent edges in one time step, and it can optimize a richer set of optimization criteria. Our experimental studies indicate that our richer modeling can be achieved without significantly worsening the running time when compared to Wu et al.&#39;s algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering

Editing a graph into a disjoint union of clusters is a standard optimization task in graph-based data clustering. Here, complementing classic work where the clusters shall be cliques, we focus on clusters that shall be 2-clubs, that is, subgraphs of diameter two. This naturally leads to the two NP-hard problems 2-Club Cluster Editing (the allowed editing operations are edge insertion and edge deletion) and 2-Club Cluster Vertex Deletion (the allowed editing operations are vertex deletions). Answering an open question from the literature, we show that 2-Club Cluster Editing is W[2]-hard with respect to the number of edge modifications, thus contrasting the fixed-parameter tractability result for the classic Cluster Editing problem (considering cliques instead of 2-clubs). Then focusing on 2-Club Cluster Vertex Deletion, which is easily seen to be fixed-parameter tractable, we show that under standard complexity-theoretic assumptions it does not have a polynomial-size problem kernel when parameterized by the number of vertex deletions. Nevertheless, we develop several effective data reduction and pruning rules, resulting in a competitive solver, clearly outperforming a standard CPLEX solver in most instances of an established biological test data set.

0 citations0 reviewsNo code linkedOpen 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 $n$-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)$-approximating the difference $d$ 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 $2^{o(n)}$ time or in $f(d)\cdot n^{O(1)}$ time for any computable function $f$. Moreover, we show that the special case of connecting $c$ network components with minimum additional cost generally cannot be polynomial-time reduced to instances of size $c^{O(1)}$ unless the polynomial-time hierarchy collapses. On the positive side, we provide an algorithm that reconnects $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 $n$ is sufficiently large compared to $c$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Parameterized Complexity of Min-Power Asymmetric Connectivity

We investigate parameterized algorithms for the NP-hard problem Min-Power Asymmetric Connectivity (MinPAC) that has applications in wireless sensor networks. Given a directed arc-weighted graph, MinPAC asks for a strongly connected spanning subgraph minimizing the summed vertex costs. Here, the cost of each vertex is the weight of its heaviest outgoing arc in the chosen subgraph. We present linear-time algorithms for the cases where the number of strongly connected components in a so-called obligatory subgraph or the feedback edge number in the underlying undirected graph is constant. Complementing these results, we prove that the problem is W[2]-hard with respect to the solution cost, even on restricted graphs with one feedback arc and binary arc weights.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Power of Data Reduction for Matching

Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For $m$-edge and $n$-vertex graphs, it is well-known to be solvable in $O(m\sqrt{n})$ time; however, for several applications this running time is still too slow. We investigate how linear-time (and almost linear-time) data reduction (used as preprocessing) can alleviate the situation. More specifically, we focus on (almost) linear-time kernelization. We start a deeper and systematic study both for general graphs and for bipartite graphs. Our data reduction algorithms easily comply (in form of preprocessing) with every solution strategy (exact, approximate, heuristic), thus making them attractive in various settings.

0 citations0 reviewsNo code linkedOpen access