Source author record

Frank Sommer

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Discrete Mathematics Machine Learning

Catalog footprint

Research overview

5works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Exact and Approximate Algorithms for Polytree Learning

Polytrees are a subclass of Bayesian networks that seek to capture the conditional dependencies between a set of $n$ variables as a directed forest and are motivated by their more efficient inference and improved interpretability. Since the problem of learning the best polytree is NP-hard, we study which restrictions make it more tractable by considering for example in-degree bounds, properties of score functions measuring the quality of a polytree, and approximation algorithms. We devise an algorithm that finds the optimal polytree in time $O((2+ε)^n)$ for arbitrarily small $ε> 0$ and any constant in-degree bound $k$ , improving over the fastest previously known algorithm of time complexity $O(3^n)$ . We further give polynomial-time algorithms for finding a polytree whose score is within a factor of $k$ from the optimal one for arbitrary scores and a factor of $2$ for additive ones. Many of the results are complemented by (nearly) tight lower bounds for either the time complexity or the approximation factors.

preprint2022arXiv

Exploiting $\mathbf{c}$ -Closure in Kernelization Algorithms for Graph Problems

A graph is c-closed if every pair of vertices with at least c common neighbors is adjacent. The c-closure of a graph G is the smallest number such that G is c-closed. Fox et al. [ICALP '18] defined c-closure and investigated it in the context of clique enumeration. We show that c-closure can be applied in kernelization algorithms for several classic graph problems. We show that Dominating Set admits a kernel of size k^O(c), that Induced Matching admits a kernel with O(c^7*k^8) vertices, and that Irredundant Set admits a kernel with O(c^(5/2)*k^3) vertices. Our kernelization exploits the fact that c-closed graphs have polynomially-bounded Ramsey numbers, as we show.

preprint2022arXiv

Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge Periodic Temporal Graphs

We study the computational complexity of determining structural properties of edge periodic temporal graphs (EPGs). EPGs are time-varying graphs that compactly represent periodic behavior of components of a dynamic network, for example, train schedules on a rail network. In EPGs, for each edge $e$ of the graph, a binary string $s_e$ determines in which time steps the edge is present, namely $e$ is present in time step $t$ if and only if $s_e$ contains a $1$ at position $t \mod |s_e|$ . Due to this periodicity, EPGs serve as very compact representations of complex periodic systems and can even be exponentially smaller than classic temporal graphs representing one period of the same system, as the latter contain the whole sequence of graphs explicitly. In this paper, we study the computational complexity of fundamental questions of the new concept of EPGs such as what is the shortest traversal time between two vertices; is there a time step in which the graph (1) is minor-free; (2) contains a minor; (3) is subgraph-free; (4) contains a subgraph; with respect to a given minor or subgraph. We give a detailed parameterized analysis for multiple combinations of parameters for the problems stated above including several parameterized algorithms.

preprint2022arXiv

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

The s-Club problem asks, for a given undirected graph $G$ , whether $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.

preprint2021arXiv

Essentially Tight Kernels for (Weakly) Closed Graphs

We study kernelization of classic hard graph problems when the input graphs fulfill triadic closure properties. More precisely, we consider the recently introduced parameters closure number $c$ and the weak closure number $γ$ [Fox et al., SICOMP 2020] in addition to the standard parameter solution size $k$ . For Capacitated Vertex Cover, Connected Vertex Cover, and Induced Matching we obtain the first kernels of size $k^{\mathcal{O}(γ)}$ and $(γk)^{\mathcal{O}(γ)}$ , respectively, thus extending previous kernelization results on degenerate graphs. The kernels are essentially tight, since these problems are unlikely to admit kernels of size $k^{o(γ)}$ by previous results on their kernelization complexity in degenerate graphs [Cygan et al., ACM TALG 2017]. In addition, we provide lower bounds for the kernelization of Independent Set on graphs with constant closure number~ $c$ and kernels for Dominating Set on weakly closed split graphs and weakly closed bipartite graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Frank Sommer

Research overview

Is this your work?

5 publications

Exact and Approximate Algorithms for Polytree Learning

Exploiting $\mathbf{c}$ -Closure in Kernelization Algorithms for Graph Problems

Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge Periodic Temporal Graphs

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

Essentially Tight Kernels for (Weakly) Closed Graphs

See the researcher in context

Building this map preview

Frank Sommer

Research overview

Is this your work?

5 publications

Exact and Approximate Algorithms for Polytree Learning

Exploiting c\mathbf{c}c-Closure in Kernelization Algorithms for Graph Problems

Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge Periodic Temporal Graphs

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

Essentially Tight Kernels for (Weakly) Closed Graphs

See the researcher in context

Building this map preview

Exploiting $\mathbf{c}$ -Closure in Kernelization Algorithms for Graph Problems