Frank Sommer
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
Research Subjects
Frank Sommer has a total of 40 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
15 shared publications - Niels Grüttemeier
Fraunhofer IOSB-INA Lemgo Germany
4 shared publications Niels Grüttemeier
3 shared publications- Nils Morawietz
Philipps-Universität Marburg
3 shared publications Christian Komusiewicz
2 shared publications- Diptapriyo Majumdar
Indraprastha Institute of Information Technology Delhi, New Delhi, India
2 shared publications
Latest Publications
- Open Access
- 10 July 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1084
Temporal Dominating Set and Temporal Vertex Cover under the Lens of Degree Restrictions
- 10 July 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1084
Open AccessTemporal Dominating Set and Temporal Vertex Cover under the Lens of Degree Restrictions
- Open Access
- 17 January 2026
- Published by Journal of Graph Algorithms and Applications in Journal of Graph Algorithms and Applications
- Vol. 30 (1) , 385-419
The Parameter Report: An Orientation Guide for Data-Driven Parameterization
A strength of parameterized algorithmics is that each problem can be parameterized by an essentially inexhaustible set of parameters. Usually, the choice of the considered parameter is informed by the theoretical relations between parameters with the general goal of achieving FPT-algorithms for smaller and smaller parameters. However, the FPT-algorithms for smaller parameters usually have higher running times and it is unclear whether the decrease in the parameter value or the increase in the running time bound dominates in real-world data. This question cannot be answered from purely theoretical considerations and any answer requires knowledge on typical parameter values. To provide a data-driven guideline for parameterized complexity studies of graph problems, we present the first comprehensive comparison of parameter values for a set of benchmark graphs originating from real-world applications. Our study covers degree-related parameters, such as maximum degree or degeneracy, neighborhood-based parameters such as neighborhood diversity and modular-width, modulator-based parameters such as vertex cover number and feedback vertex set number, and the treewidth of the graphs. Our results may help assess the significance of FPT-running time bounds on the solvability of real-world instances. For example, the vertex cover number $vc$ of $n$-vertex graphs is often only slightly below $n/2$. Thus, a running time bound of $O(2^{vc})$ is only slightly better than a running time bound of $O(1.4^{n})$. In contrast, the treewidth $tw$ is almost always below $n/3$ and often close to $n/9$, making a running time of $O(2^{tw})$ much more practical on real-world instances.We make our implementation and full experimental data openly available. In particular, this provides the first implementations for several graph parameters such as 4-path vertex cover number and vertex integrity.- 17 January 2026
- Published by Journal of Graph Algorithms and Applications in Journal of Graph Algorithms and Applications
- Vol. 30 (1) , 385-419
Open AccessThe Parameter Report: An Orientation Guide for Data-Driven Parameterization
A strength of parameterized algorithmics is that each problem can be parameterized by an essentially inexhaustible set of parameters. Usually, the choice of the considered parameter is informed by the theoretical relations between parameters with the general goal of achieving FPT-algorithms for smaller and smaller parameters. However, the FPT-algorithms for smaller parameters usually have higher running times and it is unclear whether the decrease in the parameter value or the increase in the running time bound dominates in real-world data. This question cannot be answered from purely theoretical considerations and any answer requires knowledge on typical parameter values. To provide a data-driven guideline for parameterized complexity studies of graph problems, we present the first comprehensive comparison of parameter values for a set of benchmark graphs originating from real-world applications. Our study covers degree-related parameters, such as maximum degree or degeneracy, neighborhood-based parameters such as neighborhood diversity and modular-width, modulator-based parameters such as vertex cover number and feedback vertex set number, and the treewidth of the graphs. Our results may help assess the significance of FPT-running time bounds on the solvability of real-world instances. For example, the vertex cover number $vc$ of $n$-vertex graphs is often only slightly below $n/2$. Thus, a running time bound of $O(2^{vc})$ is only slightly better than a running time bound of $O(1.4^{n})$. In contrast, the treewidth $tw$ is almost always below $n/3$ and often close to $n/9$, making a running time of $O(2^{tw})$ much more practical on real-world instances.We make our implementation and full experimental data openly available. In particular, this provides the first implementations for several graph parameters such as 4-path vertex cover number and vertex integrity. - 2 January 2026
- Published by Springer Nature
- p. 331-344
Polynomial-Size Enumeration Kernelizations for Long Path Enumeration
- 2 January 2026
- Published by Springer Nature
- p. 331-344
Polynomial-Size Enumeration Kernelizations for Long Path Enumeration
- Open Access
Improving Decision Trees through the Lens of Parameterized Local Search
Algorithms for learning decision trees often include heuristic local-search operations such as (1) adjusting the threshold of a cut or (2) also exchanging the feature of that cut. We study minimizing the number of classification errors by performing a fixed number of a single type of these operations. Although we discover that the corresponding problems are NP-complete in general, we provide a comprehensive parameterized-complexity analysis with the aim of determining those properties of the problems that explain the hardness and those that make the problems tractable. For instance, we show that the problems remain hard for a small number $d$ of features or small domain size $D$ but the combination of both yields fixed-parameter tractability. That is, the problems are solvable in $(D + 1)^{2d} \cdot |I|^{O(1)}$ time, where $|I|$ is the size of the input. We also provide a proof-of-concept implementation of this algorithm and report on empirical results.Open AccessImproving Decision Trees through the Lens of Parameterized Local Search
Algorithms for learning decision trees often include heuristic local-search operations such as (1) adjusting the threshold of a cut or (2) also exchanging the feature of that cut. We study minimizing the number of classification errors by performing a fixed number of a single type of these operations. Although we discover that the corresponding problems are NP-complete in general, we provide a comprehensive parameterized-complexity analysis with the aim of determining those properties of the problems that explain the hardness and those that make the problems tractable. For instance, we show that the problems remain hard for a small number $d$ of features or small domain size $D$ but the combination of both yields fixed-parameter tractability. That is, the problems are solvable in $(D + 1)^{2d} \cdot |I|^{O(1)}$ time, where $|I|$ is the size of the input. We also provide a proof-of-concept implementation of this algorithm and report on empirical results. - Open Access
- 15 July 2025
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 378, 102-119
Multi-parameter analysis of finding minors and induced subgraphs in edge-periodic temporal graphs
- 15 July 2025
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 378, 102-119
Open AccessMulti-parameter analysis of finding minors and induced subgraphs in edge-periodic temporal graphs
- Open Access
Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
We present a comprehensive classical and parameterized complexity analysis of decision tree pruning operations, extending recent research on the complexity of learning small decision trees. Thereby, we offer new insights into the computational challenges of decision tree simplification, a crucial aspect of developing interpretable and efficient machine learning models. We focus on fundamental pruning operations of subtree replacement and raising, which are used in heuristics. Surprisingly, while optimal pruning can be performed in polynomial time for subtree replacement, the problem is NP-complete for subtree raising. Therefore, we identify parameters and combinations thereof that lead to fixed-parameter tractability or hardness, establishing a precise borderline between these complexity classes. For example, while subtree raising is hard for small domain size $D$ or number $d$ of features, it can be solved in $D^{2d} \cdot |I|^{O(1)}$ time, where $|I|$ is the input size. We complement our theoretical findings with preliminary experimental results, demonstrating the practical implications of our analysis.Open AccessOptimal Decision Tree Pruning Revisited: Algorithms and Complexity
We present a comprehensive classical and parameterized complexity analysis of decision tree pruning operations, extending recent research on the complexity of learning small decision trees. Thereby, we offer new insights into the computational challenges of decision tree simplification, a crucial aspect of developing interpretable and efficient machine learning models. We focus on fundamental pruning operations of subtree replacement and raising, which are used in heuristics. Surprisingly, while optimal pruning can be performed in polynomial time for subtree replacement, the problem is NP-complete for subtree raising. Therefore, we identify parameters and combinations thereof that lead to fixed-parameter tractability or hardness, establishing a precise borderline between these complexity classes. For example, while subtree raising is hard for small domain size $D$ or number $d$ of features, it can be solved in $D^{2d} \cdot |I|^{O(1)}$ time, where $|I|$ is the input size. We complement our theoretical findings with preliminary experimental results, demonstrating the practical implications of our analysis. - Open Access
Polynomial-Size Enumeration Kernelizations for Long Path Enumeration
Enumeration kernelization for parameterized enumeration problems was defined by Creignou et al. [Theory Comput. Syst. 2017] and was later refined by Golovach et al. [J. Comput. Syst. Sci. 2022, STACS 2021] to polynomial-delay enumeration kernelization. We consider ENUM LONG-PATH, the enumeration variant of the Long-Path problem, from the perspective of enumeration kernelization. Formally, given an undirected graph G and an integer k, the objective of ENUM LONG-PATH is to enumerate all paths of G having exactly k vertices. We consider the structural parameters vertex cover number, dissociation number, and distance to clique and provide polynomial-delay enumeration kernels of polynomial size for each of these parameters.
Open AccessPolynomial-Size Enumeration Kernelizations for Long Path Enumeration
Enumeration kernelization for parameterized enumeration problems was defined by Creignou et al. [Theory Comput. Syst. 2017] and was later refined by Golovach et al. [J. Comput. Syst. Sci. 2022, STACS 2021] to polynomial-delay enumeration kernelization. We consider ENUM LONG-PATH, the enumeration variant of the Long-Path problem, from the perspective of enumeration kernelization. Formally, given an undirected graph G and an integer k, the objective of ENUM LONG-PATH is to enumerate all paths of G having exactly k vertices. We consider the structural parameters vertex cover number, dissociation number, and distance to clique and provide polynomial-delay enumeration kernels of polynomial size for each of these parameters.
- 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. - 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. - Open Access
- 20 January 2023
- Published by Springer Nature in Algorithmica
- Vol. 85 (7) , 2156-2187
Computing Dense and Sparse Subgraphs of Weakly Closed Graphs
A graph G is weakly $$\gamma $$ -closed if every induced subgraph of G contains one vertex v such that for each non-neighbor u of v it holds that $$ \vert N(u)\cap N(v) \vert <\gamma $$ . The weak closure $$\gamma (G)$$ of a graph, recently introduced by Fox et al. (SIAM J Comput 49(2):448–464, 2020), is the smallest number such that G is weakly $$\gamma $$ -closed. This graph parameter is never larger than the degeneracy (plus one) and can be significantly smaller. Extending the work of Fox et al. (2020) on clique enumeration, we show that several problems related to finding dense subgraphs, such as the enumeration of bicliques and s-plexes, are fixed-parameter tractable with respect to $$\gamma (G)$$ . Moreover, we show that the problem of determining whether a weakly $$\gamma $$ -closed graph G has a subgraph on at least k vertices that belongs to a graph class $$\mathcal {G}$$ which is closed under taking subgraphs admits a kernel with at most $$\gamma k^2$$ vertices. Finally, we provide fixed-parameter algorithms for Independent Dominating Set and Dominating Clique when parameterized by $$\gamma +k$$ where k is the solution size. Furthermore, we show that Independent Dominating Set does not admit a polynomial kernel for constant $$\gamma $$ under standard assumptions.- 20 January 2023
- Published by Springer Nature in Algorithmica
- Vol. 85 (7) , 2156-2187
Open AccessComputing Dense and Sparse Subgraphs of Weakly Closed Graphs
A graph G is weakly $$\gamma $$ -closed if every induced subgraph of G contains one vertex v such that for each non-neighbor u of v it holds that $$ \vert N(u)\cap N(v) \vert <\gamma $$ . The weak closure $$\gamma (G)$$ of a graph, recently introduced by Fox et al. (SIAM J Comput 49(2):448–464, 2020), is the smallest number such that G is weakly $$\gamma $$ -closed. This graph parameter is never larger than the degeneracy (plus one) and can be significantly smaller. Extending the work of Fox et al. (2020) on clique enumeration, we show that several problems related to finding dense subgraphs, such as the enumeration of bicliques and s-plexes, are fixed-parameter tractable with respect to $$\gamma (G)$$ . Moreover, we show that the problem of determining whether a weakly $$\gamma $$ -closed graph G has a subgraph on at least k vertices that belongs to a graph class $$\mathcal {G}$$ which is closed under taking subgraphs admits a kernel with at most $$\gamma k^2$$ vertices. Finally, we provide fixed-parameter algorithms for Independent Dominating Set and Dominating Clique when parameterized by $$\gamma +k$$ where k is the solution size. Furthermore, we show that Independent Dominating Set does not admit a polynomial kernel for constant $$\gamma $$ under standard assumptions.