JGJaroslav Garvardt
Jaroslav Garvardt
*This is an algorithmically generated author record based on publicly available information.
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
Jaroslav Garvardt has a total of 8 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
4 shared publications - Frank Sommer
Institute of Logic and Computation TU Wien Austria
2 shared publications - Berthold Blatt Lorke
TU Berlin
1 shared publication Christian Komusiewicz
1 shared publication- Jannik Schestag
Delft University of Technology, Delft, The Netherlands
1 shared publication - Niels Grüttemeier
Fraunhofer IOSB-INA Lemgo Germany
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
- 22 December 2025
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 383, 169-183
When can Cluster Deletion with bounded weights be solved efficiently?
- 22 December 2025
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 383, 169-183
Open AccessWhen can Cluster Deletion with bounded weights be solved efficiently?
- 16 October 2024
- Published by Springer Nature
- p. 82-97
Protective and Nonprotective Subset Sum Games: A Parameterized Complexity Analysis
- 16 October 2024
- Published by Springer Nature
- p. 82-97
Protective and Nonprotective Subset Sum Games: A Parameterized Complexity Analysis
- Open Access
- 12 August 2023
- Published by Springer Nature in Theory of Computing Systems
- Vol. 67 (5) , 1050-1081
The Parameterized Complexity of s-Club with Triangle and Seed Constraints
The s-Club problem asks whether a given undirected graph G contains a vertex set S of size at least k such that G[S], the subgraph of G induced by S, has diameter at most s. We consider variants of s-Club where one additionally demands that each vertex of G[S] is contained in at least $$\ell $$ triangles in G[S], that each edge of G[S] is contained in at least $$\ell $$ triangles in G[S], or that S contains a given set W of seed vertices. We show that in general these variants are W[1]-hard when parameterized by the solution size k, making them significantly harder than the unconstrained s-Club problem. On the positive side, we obtain some FPT algorithms for the case when $$\ell =1$$ and for the case when G[W], the graph induced by the set of seed vertices, is a clique.- 12 August 2023
- Published by Springer Nature in Theory of Computing Systems
- Vol. 67 (5) , 1050-1081
Open AccessThe Parameterized Complexity of s-Club with Triangle and Seed Constraints
The s-Club problem asks whether a given undirected graph G contains a vertex set S of size at least k such that G[S], the subgraph of G induced by S, has diameter at most s. We consider variants of s-Club where one additionally demands that each vertex of G[S] is contained in at least $$\ell $$ triangles in G[S], that each edge of G[S] is contained in at least $$\ell $$ triangles in G[S], or that S contains a given set W of seed vertices. We show that in general these variants are W[1]-hard when parameterized by the solution size k, making them significantly harder than the unconstrained s-Club problem. On the positive side, we obtain some FPT algorithms for the case when $$\ell =1$$ and for the case when G[W], the graph induced by the set of seed vertices, is a clique. - 29 May 2022
- Published by Springer Nature
- p. 313-326
The Parameterized Complexity of s-Club with Triangle and Seed Constraints
- 29 May 2022
- Published by Springer Nature
- p. 313-326
The Parameterized Complexity of s-Club with Triangle and Seed Constraints