FSFrank Sommer

Frank Sommer

*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


Frank Sommer has a total of 40 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Temporal Dominating Set and Temporal Vertex Cover under the Lens of Degree Restrictions

    by Anton Herrmann, Christian Komusiewicz, Nils Morawietz, Frank Sommer

  • Open Access

    The Parameter Report: An Orientation Guide for Data-Driven Parameterization

    by Christian Komusiewicz, Nils Morawietz, Frank Sommer, Luca Pascal Staus

    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.


  • Polynomial-Size Enumeration Kernelizations for Long Path Enumeration

    by Christian Komusiewicz, Diptapriyo Majumdar, Frank Sommer


  • Open Access

    Improving Decision Trees through the Lens of Parameterized Local Search

    by Juha Harviainen, Frank Sommer, Manuel Sorge

    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

    Multi-parameter analysis of finding minors and induced subgraphs in edge-periodic temporal graphs

    by Emmanuel Arrighi, Niels Grüttemeier, Nils Morawietz, Frank Sommer, Petra Wolf


  • Open Access

    Optimal Decision Tree Pruning Revisited: Algorithms and Complexity

    by Juha Harviainen, Frank Sommer, Manuel Sorge, Stefan Szeider

    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

    by Christian Komusiewicz, Diptapriyo Majumdar, Frank Sommer

    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

    Efficient branch-and-bound algorithms for finding triangle-constrained 2-clubs

    by Niels Grüttemeier, Philipp Heinrich Keßler, Christian Komusiewicz, Frank Sommer

    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

    The Parameterized Complexity of s-Club with Triangle and Seed Constraints

    by Jaroslav Garvardt, Christian Komusiewicz, Frank Sommer

    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$$ ℓ = 1 and for the case when G[W], the graph induced by the set of seed vertices, is a clique.


  • Open Access

    Computing Dense and Sparse Subgraphs of Weakly Closed Graphs

    by Tomohiro Koana, Christian Komusiewicz, Frank Sommer

    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 $$ | N ( u ) ∩ N ( v ) | < γ . The weak closure $$\gamma (G)$$ γ ( 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)$$ γ ( 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}$$ G which is closed under taking subgraphs admits a kernel with at most $$\gamma k^2$$ γ k 2 vertices. Finally, we provide fixed-parameter algorithms for Independent Dominating Set and Dominating Clique when parameterized by $$\gamma +k$$ γ + 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.