Niels Grüttemeier
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Niels Grüttemeier has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
- Christian Komusiewicz
Institute of Computer Science, Friedrich Schiller University Jena, Jena, Germany
7 shared publications - Frank Sommer
Institute of Logic and Computation TU Wien Austria
4 shared publications Christian Komusiewicz
3 shared publications- Nils Morawietz
Philipps-Universität Marburg
3 shared publications Manuel Sorge
2 shared publications- Emmanuel Arrighi
University of Bergen
1 shared publication
Latest Publications
- Open Access
- 17 September 2026
- Published by Springer Nature in Annals of Operations Research
- Vol. 365 (2-3) , 523-563
Parameterized Local Search for Max c-Cut
In the NP-hard Max c -Cut problem, one is given an undirected edge-weighted graph G and aims to color the vertices of G with c colors such that the total weight of edges with distinctly colored endpoints is maximal. The case with $$c=2$$ is the famous Max Cut problem. To deal with the NP-hardness of this problem, we study parameterized local search algorithms. More precisely, we study LS Max c -Cut where we are also given a vertex coloring and an integer k and the task is to find a better coloring that changes the color of at most k vertices, if such a coloring exists; otherwise, the given coloring is k -optimal. We show that, for all $$c\ge 2$$ , LS Max c -Cut presumably cannot be solved in $$f(k)\cdot n^{\mathcal {O}(1)}$$ time even on bipartite graphs. We then present an algorithm for LS Max c -Cut with running time $$\mathcal {O}((3e\Delta )^k\cdot c\cdot k^3\cdot \Delta \cdot n)$$ , where $$\Delta $$ is the maximum degree of the input graph. Finally, we evaluate the practical performance of this algorithm in a hill-climbing approach as a post-processing for a state-of-the-art heuristic for Max c -Cut . We show that using parameterized local search, the results of this state-of-the-art heuristic can be further improved on a set of standard benchmark instances.- 17 September 2026
- Published by Springer Nature in Annals of Operations Research
- Vol. 365 (2-3) , 523-563
Open AccessParameterized Local Search for Max c-Cut
In the NP-hard Max c -Cut problem, one is given an undirected edge-weighted graph G and aims to color the vertices of G with c colors such that the total weight of edges with distinctly colored endpoints is maximal. The case with $$c=2$$ is the famous Max Cut problem. To deal with the NP-hardness of this problem, we study parameterized local search algorithms. More precisely, we study LS Max c -Cut where we are also given a vertex coloring and an integer k and the task is to find a better coloring that changes the color of at most k vertices, if such a coloring exists; otherwise, the given coloring is k -optimal. We show that, for all $$c\ge 2$$ , LS Max c -Cut presumably cannot be solved in $$f(k)\cdot n^{\mathcal {O}(1)}$$ time even on bipartite graphs. We then present an algorithm for LS Max c -Cut with running time $$\mathcal {O}((3e\Delta )^k\cdot c\cdot k^3\cdot \Delta \cdot n)$$ , where $$\Delta $$ is the maximum degree of the input graph. Finally, we evaluate the practical performance of this algorithm in a hill-climbing approach as a post-processing for a state-of-the-art heuristic for Max c -Cut . We show that using parameterized local search, the results of this state-of-the-art heuristic can be further improved on a set of standard benchmark instances. - Open Access
- 21 September 2024
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 48 (3) , 1-27
Efficient branch-and-bound algorithms for finding triangle-constrained 2-clubs
In the Vertex Triangle 2-Club problem, we are given an undirected graph G and aim to find a maximum-vertex subgraph of G that has diameter at most 2 and in which every vertex is contained in at least $$\ell $$ triangles in the subgraph. So far, the only algorithm for solving Vertex Triangle 2-Club relies on an ILP formulation (Almeida and Brás in Comput Oper Res 111:258–270, 2019). In this work, we develop a combinatorial branch-and-bound algorithm that, coupled with a set of data reduction rules, outperforms the existing implementation and is able to find optimal solutions on sparse real-world graphs with more than 100,000 vertices in a few minutes. We also extend our algorithm to the Edge Triangle 2-Club problem where the triangle constraint is imposed on all edges of the subgraph.- 21 September 2024
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 48 (3) , 1-27
Open AccessEfficient branch-and-bound algorithms for finding triangle-constrained 2-clubs
In the Vertex Triangle 2-Club problem, we are given an undirected graph G and aim to find a maximum-vertex subgraph of G that has diameter at most 2 and in which every vertex is contained in at least $$\ell $$ triangles in the subgraph. So far, the only algorithm for solving Vertex Triangle 2-Club relies on an ILP formulation (Almeida and Brás in Comput Oper Res 111:258–270, 2019). In this work, we develop a combinatorial branch-and-bound algorithm that, coupled with a set of data reduction rules, outperforms the existing implementation and is able to find optimal solutions on sparse real-world graphs with more than 100,000 vertices in a few minutes. We also extend our algorithm to the Edge Triangle 2-Club problem where the triangle constraint is imposed on all edges of the subgraph. - 1 January 2023
- Published by Springer Nature
- p. 283-297
Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge-Periodic Temporal Graphs
- 1 January 2023
- Published by Springer Nature
- p. 283-297
Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge-Periodic Temporal Graphs
- Open Access
- 22 September 2022
- Published by Springer Nature in Theory of Computing Systems
- Vol. 66 (5) , 1019-1045
Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs
In the NP-hard Colored (s,t)-Cut problem, the input is a graph G = (V,E) together with an edge-coloring ℓ : E → C, two vertices s and t, and a number k. The question is whether there is a set $S\subseteq C$ S ⊆ C of at most k colors such that deleting every edge with a color from S destroys all paths between s and t in G. We continue the study of the parameterized complexity of Colored (s,t)-Cut. First, we consider parameters related to the structure of G. For example, we study parameterization by the number ξi of edge deletions that are needed to transform G into a graph with maximum degree i. We show that Colored (s,t)-Cut is W[2]-hard when parameterized by ξ3, but fixed-parameter tractable when parameterized by ξ2. Second, we consider parameters related to the coloring ℓ. We show fixed-parameter tractability for three parameters that are potentially smaller than the total number of colors |C| and provide a linear-size problem kernel for a parameter related to the number of edges with rare edge colors.
- 22 September 2022
- Published by Springer Nature in Theory of Computing Systems
- Vol. 66 (5) , 1019-1045
Open AccessRefined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs
In the NP-hard Colored (s,t)-Cut problem, the input is a graph G = (V,E) together with an edge-coloring ℓ : E → C, two vertices s and t, and a number k. The question is whether there is a set $S\subseteq C$ S ⊆ C of at most k colors such that deleting every edge with a color from S destroys all paths between s and t in G. We continue the study of the parameterized complexity of Colored (s,t)-Cut. First, we consider parameters related to the structure of G. For example, we study parameterization by the number ξi of edge deletions that are needed to transform G into a graph with maximum degree i. We show that Colored (s,t)-Cut is W[2]-hard when parameterized by ξ3, but fixed-parameter tractable when parameterized by ξ2. Second, we consider parameters related to the coloring ℓ. We show fixed-parameter tractability for three parameters that are potentially smaller than the total number of colors |C| and provide a linear-size problem kernel for a parameter related to the number of edges with rare edge colors.
- 29 May 2022
- Published by Springer Nature
- p. 494-508
On Critical Node Problems with Vulnerable Vertices
- Open Access
Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis
We study the problem of learning the structure of an optimal Bayesian network when additional constraints are posed on the network or on its moralized graph. More precisely, we consider the constraint that the network or its moralized graph are close, in terms of vertex or edge deletions, to a sparse graph class $\Pi$. For example, we show that learning an optimal network whose moralized graph has vertex deletion distance at most $k$ from a graph with maximum degree 1 can be computed in polynomial time when $k$ is constant. This extends previous work that gave an algorithm with such a running time for the vertex deletion distance to edgeless graphs [Korhonen & Parviainen, NIPS 2015]. We then show that further extensions or improvements are presumably impossible. For example, we show that learning optimal networks where the network or its moralized graph have maximum degree $2$ or connected components of size at most $c$, $c\ge 3$, is NP-hard. Finally, we show that learning an optimal network with at most $k$ edges in the moralized graph presumably has no $f(k)\cdot |I|^{O(1)}$-time algorithm and that, in contrast, an optimal network with at most $k$ arcs can be computed in $2^{O(k)}\cdot |I|^{O(1)}$ time where $|I|$ is the total input size.Open AccessLearning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis
We study the problem of learning the structure of an optimal Bayesian network when additional constraints are posed on the network or on its moralized graph. More precisely, we consider the constraint that the network or its moralized graph are close, in terms of vertex or edge deletions, to a sparse graph class $\Pi$. For example, we show that learning an optimal network whose moralized graph has vertex deletion distance at most $k$ from a graph with maximum degree 1 can be computed in polynomial time when $k$ is constant. This extends previous work that gave an algorithm with such a running time for the vertex deletion distance to edgeless graphs [Korhonen & Parviainen, NIPS 2015]. We then show that further extensions or improvements are presumably impossible. For example, we show that learning optimal networks where the network or its moralized graph have maximum degree $2$ or connected components of size at most $c$, $c\ge 3$, is NP-hard. Finally, we show that learning an optimal network with at most $k$ edges in the moralized graph presumably has no $f(k)\cdot |I|^{O(1)}$-time algorithm and that, in contrast, an optimal network with at most $k$ arcs can be computed in $2^{O(k)}\cdot |I|^{O(1)}$ time where $|I|$ is the total input size. - 1 September 2021
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 120, 75-96
Your rugby mates don't need to know your colleagues: Triadic closure with edge colors
- 1 September 2021
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 120, 75-96
Your rugby mates don't need to know your colleagues: Triadic closure with edge colors
- Open Access
Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs
Given an undirected graph $G$ and integers $c$ and $k$, the Maximum Edge-Colorable Subgraph problem asks whether we can delete at most $k$ edges in $G$ to obtain a graph that has a proper edge coloring with at most $c$ colors. We show that Maximum Edge-Colorable Subgraph admits, for every fixed $c$, a linear-size problem kernel when parameterized by the edge deletion distance of $G$ to a graph with maximum degree $c-1$. This parameterization measures the distance to instances that, due to Vizing's famous theorem, are trivial yes-instances. For $c\le 4$, we also provide a linear-size kernel for the same parameterization for Multi Strong Triadic Closure, a related edge coloring problem with applications in social network analysis. We provide further results for Maximum Edge-Colorable Subgraph parameterized by the vertex deletion distance to graphs where every component has order at most $c$ and for the list-colored versions of both problems.Open AccessMaximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs
Given an undirected graph $G$ and integers $c$ and $k$, the Maximum Edge-Colorable Subgraph problem asks whether we can delete at most $k$ edges in $G$ to obtain a graph that has a proper edge coloring with at most $c$ colors. We show that Maximum Edge-Colorable Subgraph admits, for every fixed $c$, a linear-size problem kernel when parameterized by the edge deletion distance of $G$ to a graph with maximum degree $c-1$. This parameterization measures the distance to instances that, due to Vizing's famous theorem, are trivial yes-instances. For $c\le 4$, we also provide a linear-size kernel for the same parameterization for Multi Strong Triadic Closure, a related edge coloring problem with applications in social network analysis. We provide further results for Maximum Edge-Colorable Subgraph parameterized by the vertex deletion distance to graphs where every component has order at most $c$ and for the list-colored versions of both problems. - 16 August 2019
- Published by Springer Nature in Algorithmica
- Vol. 82 (4) , 853-880
On the Relation of Strong Triadic Closure and Cluster Deletion
- 16 August 2019
- Published by Springer Nature in Algorithmica
- Vol. 82 (4) , 853-880
On the Relation of Strong Triadic Closure and Cluster Deletion
- 6 April 2019
- Published by Springer Nature
- p. 99-111
Your Rugby Mates Don’t Need to Know Your Colleagues: Triadic Closure with Edge Colors
- 6 April 2019
- Published by Springer Nature
- p. 99-111
Your Rugby Mates Don’t Need to Know Your Colleagues: Triadic Closure with Edge Colors