For a fixed graph class Π, the goal of Π-Modification is to transform an input graph G into a graph H ∈ Π using at most k modifications. Vertex and edge deletions are common operations, and their (parameterized) complexity for various Π is well-studied. Classic graph modification operations such as edge deletion do not consider the geometric nature of intersection graphs such as (unit) disk graphs. This led Fomin et al. [ITCS' 25] to introduce scaling as a geometric graph modification operation for unit disk graphs: For a given radius r, each modified disk will be rescaled to radius r. In this paper, we generalize their model by allowing rescaled disks to choose a radius within a given interval [r_min, r_max] and study the (parameterized) complexity (with respect to k) of the corresponding problem Π-Scaling. We show that Π-Scaling is in XP for every graph class Π that can be recognized in polynomial time. Furthermore, we show that Π-Scaling: (1) is NP-hard and FPT for cluster graphs, (2) can be solved in polynomial time for complete graphs, and (3) is W[1]-hard for connected graphs. In particular, (1) and (2) answer open questions of Fomin et al. and (3) generalizes the hardness result for their variant where the set of scalable disks is restricted.

The minimum cut problem is one of the oldest and most fundamental optimization problems in operations research. In this problem, we are given a connected edge-weighted graph (G,ω) and have to find an edge set A (called edge-cut) of smallest total weight such that the removal of the edges of A disconnects G. The problem thus takes the view of an attacker that wants to destroy the global connectivity of the network. Bienstock and Diaz [SICOMP '93] introduced Global Cut Prevention, a two-player version of the minimum cut problem where a defender aims to protect edges to increase the weight of the minimum cut of the resulting graph. More precisely, the input contains an additional edge cost function c that is independent of the attacker weight ω and the defender aims to protect an edge set of total cost at most d such that every edge-cut consisting of unprotected edges has weight at least a+1. We initiate the study of the parameterized complexity of Global Cut Prevention. Here, we consider the most natural parameters such as the budgets d and a of the players, the vertex cover number and treewidth of the input graph, and combinations of these parameters. We show, for example, that the encoding of the costs and weights of the edges has a considerable influence on the problem complexity: If each edge has unit defender cost and unit attacker weight, then Global Cut Prevention is FPT for the vertex cover number. If the attacker weights are arbitrary and encoded in unary, then the problem is W[1]-hard for the vertex cover number but still admits an XP-algorithm. Finally, if the defender cost and the attacker weight are encoded in binary, then the problem becomes NP-hard even on graphs with a vertex cover of size 2.

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 τ ( e ) determines in which time steps the edge is present, namely e is present in time step t if and only if τ ( e ) contains a 1 at position t mod | τ ( 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 concept of EPGs such as : Is there a time step or a sliding window of size Δ in which the graph (1) is minor-free; (2) contains a minor; (3) is induced subgraph-free; (4) contains an induced 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 algorithms. Additionally, we study the parameterized complexity of the short traversal problem in EPGs. In this problem, one asks whether there exists a time step t such that one can reach a vertex b from a vertex a at time step at most t + k for given k .

We study the Temporal Dominating Set problem, in which one asks whether a temporal graph G = ( G 1 , ⋯ , G T ) given as a sequence of snapshot graphs over the same vertex set V has a set S of at most k temporal vertices such that each vertex v of V is dominated by some w ∈ S in the snapshot that contains w . Additionally, we consider Temporal Partial Dominating Set , where one asks whether at least t (and not necessarily all) vertices of V can be dominated by S and a further generalization in which the solution may only contain a bounded number of temporal vertices from each snapshot. We analyze how the complexity of Temporal (Partial) Dominating Set is influenced by the maximum snapshot degree and the structure of the underlying graph, the graph with vertex set V whose edge set is the union of all snapshot edge sets. For example, we obtain a complexity dichotomy for the maximum snapshot degree and show that Temporal Partial Dominating Set is fixed-parameter tractable for tw + Δ , where tw and Δ denote the treewidth and the maximum degree of the underlying graph of G , respectively. We also study which of our results transfer to the well-studied Temporal Vertex Cover problem. For example, we show that Temporal Vertex Cover is also fixed-parameter tractable for tw + Δ which substantially extends the previously known polynomial-time algorithms for the case that the underlying graph is a path or cycle.

Decision trees are a classic model for summarizing and classifying data. To enhance interpretability and generalization properties, it has been proposed to favor small decision trees. Accordingly, in the minimum-size decision tree training problem (MSDT), the input is a set of training examples in $\mathbb{R}^d$ with class labels and we aim to find a decision tree that classifies all training examples correctly and has a minimum number of nodes. MSDT is NP-hard and therefore presumably not solvable in polynomial time. Nevertheless, a promising algorithmic paradigm called witness trees which solves MSDT efficiently if the solution tree is small has been developed. In this work, we test this paradigm empirically. We provide an implementation, augment it with extensive heuristic improvements, and scrutinize it on standard benchmark instances. The augmentations achieve a mean 324-fold (median 84-fold) speedup over the naive implementation. Compared to the state of the art they achieve a mean 32-fold (median 7-fold) speedup over the dynamic programming based MurTree solver and a mean 61-fold (median 25-fold) speedup over SAT-based implementations. As a theoretical result we obtain an improved worst-case running-time bound for MSDT.

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.

Binary decision diagrams (BDDs) are widely applied tools to compactly represent labeled data as directed acyclic graphs; for efficiency and interpretability reasons small BDDs are preferred. Given labeled data, minimizing BDDs is NP-complete and thus recent research focused on the influence of parameters such as the solution size $s$ on the complexity [Ordyniak et al., AAAI 2024]. Our main positive result is an algorithm that is efficient if in particular $s$, the domain size $D$, and the Hamming distance between any two data points is small, improving on previous running-time bounds. This algorithm is inspired by the witness-tree paradigm that was recently successful for computing decision trees [Komusiewicz et al., ICML 2023], whose extension to BDDs was open. We extend our algorithmic results to the case where we allow a small number of misclassified data points and complement them with lower bounds that show that the running times are tight from multiple points of view. We show that our main algorithm holds practical promise by providing a proof-of-concept implementation.

A temporal graph is a finite sequence of graphs, called snapshots, over the same vertex set. Many temporal graph problems turn out to be much more difficult than their static counterparts. One such problem is Timeline Vertex Cover (also known as MinTimeline_∞), a temporal analogue to the classical Vertex Cover problem. In this problem, one is given a temporal graph 𝒢 and two integers k and 𝓁, and the goal is to cover each edge of each snapshot by selecting for each vertex at most k activity intervals of length at most 𝓁 each. Here, an edge uv in the ith snapshot is covered, if an activity interval of u or v is active at time i. In this work, we continue the algorithmic study of Timeline Vertex Cover and introduce the Timeline Dominating Set problem where we want to dominate all vertices in each snapshot by the selected activity intervals. We analyze both problems from a classical and parameterized point of view and also consider partial problem versions, where the goal is to cover (dominate) at least t edges (vertices) of the snapshots. With respect to the parameterized complexity, we consider the temporal graph parameters vertex-interval-membership-width (vimw) and interval-membership-width (imw). We show that all considered problems admit FPT-algorithms when parameterized by vimw+k+𝓁. This provides a smaller parameter combination than the ones used for previously known FPT-algorithms for Timeline Vertex Cover. Surprisingly, for imw+k+𝓁, Timeline Dominating Set turns out to be easier than Timeline Vertex Cover, by also admitting an FPT-algorithm, whereas the vertex cover version is NP-hard even if imw+k+𝓁 is constant. We also consider parameterization by combinations of n, the vertex set size, with k or 𝓁 and parameterization by t. Here, we show for example that both partial problems are fixed-parameter tractable for t which significantly improves and generalizes a previous result for a special case of Partial Timeline Vertex Cover with k = 1.

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 |\mathcal{I}|^{O(1)}$ time, where $|\mathcal{I}|$ is the size of the input. We also provide a proof-of-concept implementation of this algorithm and report on empirical results.

32:1

We show that the simplest local search heuristics for two natural Euclidean clustering problems are PLS-complete. First, we show that the Hartigan--Wong method for $k$-Means clustering is PLS-complete, even when $k = 2$. Second, we show the same result for the Flip heuristic for Max Cut, even when the edge weights are given by the (squared) Euclidean distances between the points in some set $\mathcal{X} \subseteq \mathbb{R}^d$; a problem which is equivalent to Min Sum 2-Clustering.

In the NP-hard Π-Network Sparsification problem, we are given an edge-weighted graph G, a collection 𝒞 of c subsets of V(G), called communities, and two numbers 𝓁 and b, and the question is whether there exists a spanning subgraph G' of G with at most 𝓁 edges of total weight at most b such that G'[C] fulfills Π for each community C ∈ 𝒞. We study the fine-grained and parameterized complexity of two special cases of this problem: Connectivity NWS where Π is the connectivity property and Stars NWS, where Π is the property of having a spanning star. First, we provide a tight 2^Ω(n²+c)-time running time lower bound based on the ETH for both problems, where n is the number of vertices in G even if all communities have size at most 4, G is a clique, and every edge has unit weight. For the connectivity property, the unit weight case with G being a clique is the well-studied problem of computing a hypergraph support with a minimum number of edges. We then study the complexity of both problems parameterized by the feedback edge number t of the solution graph G'. For Stars NWS, we present an XP-algorithm for t answering an open question by Korach and Stern [Discret. Appl. Math. '08] who asked for the existence of polynomial-time algorithms for t = 0. In contrast, we show for Connectivity NWS that known polynomial-time algorithms for t = 0 [Korach and Stern, Math. Program. '03; Klemz et al., SWAT '14] cannot be extended to larger values of t by showing NP-hardness for t = 1.

Random forests and, more generally, (decision-)tree ensembles are widely used methods for classification and regression. Recent algorithmic advances allow to compute decision trees that are optimal for various measures such as their size or depth. We are not aware of such research for tree ensembles and aim to contribute to this area. Mainly, we provide two novel algorithms and corresponding lower bounds. First, we are able to carry over and substantially improve on tractability results for decision trees, obtaining a $(6\delta D S)^S \cdot \mathrm{poly}$-time algorithm, where $S$ is the number of cuts in the tree ensemble, $D$ the largest domain size, and $\delta$ is the largest number of features in which two examples differ. To achieve this, we introduce the witness-tree technique which also seems promising for practice. Second, we show that dynamic programming, which has been successful for decision trees, may also be viable for tree ensembles, providing an $\ell^n \cdot \mathrm{poly}$-time algorithm, where $\ell$ is the number of trees and $n$ the number of examples. Finally, we compare the number of cuts necessary to classify training data sets for decision trees and tree ensembles, showing that ensembles may need exponentially fewer cuts for increasing number of trees.

We study a generalization of the classic Spanning Tree problem that allows for a non-uniform failure model. More precisely, edges are either \emph{safe} or \emph{unsafe} and we assume that failures only affect unsafe edges. In Unweighted Flexible Graph Connectivity we are given an undirected graph $G = (V,E)$ in which the edge set $E$ is partitioned into a set $S$ of safe edges and a set $U$ of unsafe edges and the task is to find a set $T$ of at most $k$ edges such that $T - \{u\}$ is connected and spans $V$ for any unsafe edge $u \in T$. Unweighted Flexible Graph Connectivity generalizes both Spanning Tree and Hamiltonian Cycle. We study Unweighted Flexible Graph Connectivity in terms of fixed-parameter tractability (FPT). We show an almost complete dichotomy on which parameters lead to fixed-parameter tractability and which lead to hardness. To this end, we obtain FPT-time algorithms with respect to the vertex deletion distance to cluster graphs and with respect to the treewidth. By exploiting the close relationship to Hamiltonian Cycle, we show that FPT-time algorithms for many smaller parameters are unlikely under standard parameterized complexity assumptions. Regarding problem-specific parameters, we observe that Unweighted Flexible Graph Connectivity} admits an FPT-time algorithm when parameterized by the number of unsafe edges. Furthermore, we investigate a below-upper-bound parameter for the number of edges of a solution. We show that this parameter also leads to an FPT-time algorithm.

Abstract 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 weak closure number $$\gamma $$ γ (Fox et al. SIAM J Comput 49(2):448–464, 2020) in addition to the standard parameter solution size k. The weak closure number $$\gamma $$ γ of a graph is upper-bounded by the minimum of its closure number c and its degeneracy d. For Capacitated Vertex Cover, Connected Vertex Cover, and Induced Matching we obtain the first kernels of size $$k^{\mathcal {O}(\gamma )}$$ k O ( γ ) , $$k^{\mathcal {O}(\gamma )}$$ k O ( γ ) , and $$(\gamma k)^{\mathcal {O}(\gamma )}$$ ( γ k ) O ( γ ) , respectively. This extends previous results on the kernelization of these problems on degenerate graphs. These kernels are essentially tight as these problems are unlikely to admit kernels of size $$k^{o(\gamma )}$$ k o ( γ ) by previous results on their kernelization complexity on degenerate graphs (Cygan et al. ACM Trans Algorithms 13(3):43:1–43:22, 2017). For Capacitated Vertex Cover, we show that even a kernel of size $$k^{o(c)}$$ k o ( c ) is unlikely. In contrast, for Connected Vertex Cover, we obtain a kernel with $$\mathcal {O}(ck^2)$$ O ( c k 2 ) vertices. Moreover, we prove that searching for an induced subgraph of order at least k belonging to a hereditary graph class $$\mathcal {G}$$ G admits a kernel of size $$k^{\mathcal {O}(\gamma )}$$ k O ( γ ) when $$\mathcal {G}$$ G contains all complete and all edgeless graphs. Finally, 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.

Abstract 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.

Abstract 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.

We study the following two fixed-cardinality optimization problems (a maximization and a minimization variant). For a fixed $α$ between zero and one we are given a graph and two numbers $k \in \mathbb{N}$ and $t \in \mathbb{Q}$. The task is to find a vertex subset $S$ of exactly $k$ vertices that has value at least (resp. at most for minimization) $t$. Here, the value of a vertex set computes as $α$ times the number of edges with exactly one endpoint in $S$ plus $1-α$ times the number of edges with both endpoints in $S$. These two problems generalize many prominent graph problems, such as Densest $k$-Subgraph, Sparsest $k$-Subgraph, Partial Vertex Cover, and Max ($k$,$n-k$)-Cut. In this work, we complete the picture of their parameterized complexity on several types of sparse graphs that are described by structural parameters. In particular, we provide kernelization algorithms and kernel lower bounds for these problems. A somewhat surprising consequence of our kernelizations is that Partial Vertex Cover and Max $(k,n-k)$-Cut not only behave in the same way but that the kernels for both problems can be obtained by the same algorithms.

Abstract 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.

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 $c$ such that $G$ is $c$-closed. Fox et al. [ SIAM J. Comput., 49 (2020), pp. 448--464] 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^{\mathcal{O}(c)}$, that Induced Matching admits a kernel with $\mathcal{O}(c^7 k^{8})$ vertices, and that Irredundant Set admits a kernel with $\mathcal{O}(c^{5/2} k^3)$ vertices. As we show, our kernelizations exploit the fact that $c$-closed graphs have polynomially bounded Ramsey numbers.

In fixed-cardinality optimization problems in graphs, we are given a graph G = (V, E), an objective function f, and an integer k and search for a set S ⊆ V of k vertices that maximizes f (G[S]) where G[S] is the subgraph of G induced by S. We implement an enumeration-based algorithm for solving fixed-cardinality optimization problems when G[S] needs to be connected. To avoid enumerating all connected subgraphs of order k, we present several generic pruning rules and a generic heuristic for computing a lower bound for the objective value. We perform an experimental analysis of the performance of the algorithm and the usefulness of the pruning rules for eight example problems in which one aims to find dense, sparse, or degree-constrained connected subgraphs, respectively. Our experiments show that, when this generic solver is combined with problem-specific pruning rules, our algorithm is competitive with out-of-the-box ILP formulations for these 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 c such that G is c-closed. Fox et al. [SIAM J. Comput. '20] 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^𝒪(c), that Induced Matching admits a kernel with 𝒪(c⁷ k⁸) vertices, and that Irredundant Set admits a kernel with 𝒪(c^{5/2} k³) vertices. Our kernelization exploits the fact that c-closed graphs have polynomially-bounded Ramsey numbers, as we show.

A graph G is weakly γ-closed if every induced subgraph of G contains one vertex v such that for each non-neighbor u of v it holds that |N(u)∩ N(v)| < γ. The weak closure γ(G) of a graph, recently introduced by Fox et al. [SIAM J. Comp. 2020], is the smallest number such that G is weakly γ-closed. This graph parameter is never larger than the degeneracy (plus one) and can be significantly smaller. Extending the work of Fox et al. [SIAM J. Comp. 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 γ(G). Moreover, we show that the problem of determining whether a weakly γ-closed graph G has a subgraph on at least k vertices that belongs to a graph class 𝒢 which is closed under taking subgraphs admits a kernel with at most γ k² vertices. Finally, we provide fixed-parameter algorithms for Independent Dominating Set and Dominating Clique when parameterized by γ+k where k is the solution size.