Christian Komusiewicz

ICML Conference 2025 Conference Paper

Learning Minimum-Size BDDs: Towards Efficient Exact Algorithms

• Christian Komusiewicz
• André Schidler
• Frank Sommer
• Manuel Sorge
• Luca Pascal Staus

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.

AAAI Conference 2025 Conference Paper

Witty: An Efficient Solver for Computing Minimum-Size Decision Trees

• Luca Pascal Staus
• Christian Komusiewicz
• Frank Sommer
• Manuel Sorge

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.

MFCS Conference 2024 Conference Paper

On the Complexity of Community-Aware Network Sparsification

• Emanuel Herrendorf
• Christian Komusiewicz
• Nils Morawietz
• Frank Sommer

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.

ICML Conference 2023 Conference Paper

On Computing Optimal Tree Ensembles

• Christian Komusiewicz
• Pascal Kunz 0001
• Frank Sommer
• Manuel Sorge

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.

MFCS Conference 2023 Conference Paper

On the Complexity of Computing Time Series Medians Under the Move-Split-Merge Metric

• Jana Holznigenkemper
• Christian Komusiewicz
• Nils Morawietz
• Bernhard Seeger

We initiate a study of the complexity of MSM-Median, the problem of computing a median of a set of k real-valued time series under the move-split-merge distance. This distance measure is based on three operations: moves, which may shift a data point in a time series; splits, which replace one data point in a time series by two consecutive data points of the same value; and merges, which replace two consecutive data points of equal value by a single data point of the same value. The cost of a move operation is the difference of the data point value before and after the operation, the cost of split and merge operations is defined via a given constant c. Our main results are as follows. First, we show that MSM-Median is NP-hard and W[1]-hard with respect to k for time series with at most three distinct values. Under the Exponential Time Hypothesis (ETH) our reduction implies that a previous dynamic programming algorithm with running time |I|^𝒪(k) [Holznigenkemper et al. , Data Min. Knowl. Discov. '23] is essentially optimal. Here, |I| denotes the total input size. Second, we show that MSM-Median can be solved in 2^𝒪(d/c)⋅|I|^𝒪(1) time where d is the total distance of the median to the input time series.

IJCAI Conference 2023 Conference Paper

Parameterized Local Search for Max c-Cut

• Jaroslav Garvardt
• Niels Grüttemeier
• Christian Komusiewicz
• Nils Morawietz

In the NP-hard Max c-Cut problem, one is given an undirected edge-weighted graph G and wants 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 additionally given a vertex coloring f and an integer k and the task is to find a better coloring f' that differs from f in at most k entries, if such a coloring exists; otherwise, f is k-optimal. We show that LS-Max c-Cut presumably cannot be solved in g(k) · nᴼ⁽¹⁾ time even on bipartite graphs, for all c ≥ 2. We then show an algorithm for LS-Max c-Cut with running time O((3eΔ)ᵏ · c · k³ · Δ · n), where Δ 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 state-of-the-art heuristics for Max c-Cut. We show that using parameterized local search, the results of this heuristic can be further improved on a set of standard benchmark instances.

TCS Journal 2022 Journal Article

Colored cut games

• Nils Morawietz
• Niels Grüttemeier
• Christian Komusiewicz
• Frank Sommer

In a graph G = ( V, E ) with an edge coloring ℓ: E → C and two distinguished vertices s and t, a colored ( s, t ) -cut is a set C ˜ ⊆ C such that deleting all edges with some color c ∈ C ˜ from G disconnects s and t. Motivated by applications in the design of robust networks, we introduce colored cut games. In these games, an attacker and a defender choose colors to delete and to protect, respectively, in an alternating fashion. The attacker wants to achieve a colored ( s, t ) -cut and the defender wants to prevent this. First, we show that for an unbounded number of alternations, colored cut games are PSPACE-complete even on subcubic graphs. We then show that, even on subcubic graphs, colored cut games with i alternations are complete for classes in the polynomial hierarchy whose level depends on i. To complete the dichotomy, we show that all colored cut games are polynomial-time solvable on graphs with maximum degree at most 2. Next, we show that all colored cut games admit a polynomial kernel for the parameter k + κ r where k denotes the total attacker budget and, for any constant r, κ r is the number of vertex deletions that are necessary to transform G into a graph where the longest path has length at most r. For κ 1, which is the vertex cover number vc of the input graph, the kernel has size O ( vc 2 k 2 ). Moreover, we introduce an algorithm solving the most basic colored cut game, Colored ( s, t ) -Cut, in 2 vc + k n O ( 1 ) time.

MFCS Conference 2022 Conference Paper

Finding 3-Swap-Optimal Independent Sets and Dominating Sets Is Hard

• Christian Komusiewicz
• Nils Morawietz

For PLS-complete local search problems, there is presumably no polynomial-time algorithm which finds a locally optimal solution, even though determining whether a solution is locally optimal and replacing it by a better one if this is not the case can be done in polynomial time. We study local search for Weighted Independent Set and Weighted Dominating Set with the 3-swap neighborhood. The 3-swap neighborhood of a vertex set S in G is the set of vertex sets which can be obtained from S by exchanging at most three vertices. We prove the following dichotomy: On the negative side, the problem of finding a 3-swap-optimal independent set or dominating set is PLS-complete. On the positive side, locally optimal independent sets or dominating sets can be found in polynomial time when allowing all 3-swaps except a) the swaps that remove two vertices from the current solution and add one vertex to the solution or b) the swaps that remove one vertex from the current solution and add two vertices to the solution.

JAIR Journal 2022 Journal Article

Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis

• Niels Grüttemeier
• Christian Komusiewicz

We study the problem of learning the structure of an optimal Bayesian network when additional constraints are posed on the network or on its moralized graph. More precisely, we consider the constraint that the network or its moralized graph are close, in terms of vertex or edge deletions, to a sparse graph class Π. For example, we show that learning an optimal network whose moralized graph has vertex deletion distance at most k from a graph with maximum degree 1 can be computed in polynomial time when k is constant. This extends previous work that gave an algorithm with such a running time for the vertex deletion distance to edgeless graphs. We then show that further extensions or improvements are presumably impossible. For example, we show that learning optimal networks where the network or its moralized graph have maximum degree 2 or connected components of size at most c, c ≥ 3, is NP-hard. Finally, we show that learning an optimal network with at most k edges in the moralized graph presumably has no f(k) · |I|O(1)-time algorithm and that, in contrast, an optimal network with at most k arcs can be computed in 2O(k) · |I|O(1) time where |I| is the total input size.

AAAI Conference 2021 Conference Paper

Efficient Bayesian Network Structure Learning via Parameterized Local Search on Topological Orderings

• Niels Grüttemeier
• Christian Komusiewicz
• Nils Morawietz

In Bayesian Network Structure Learning (BNSL), we are given a variable set and parent scores for each variable and aim to compute a DAG, called Bayesian network, that maximizes the sum of parent scores, possibly under some structural constraints. Even very restricted special cases of BNSL are computationally hard, and, thus, in practice heuristics such as local search are used. In a typical local search algorithm, we are given some BNSL solution and ask whether there is a better solution within some pre-defined neighborhood of the solution. We study ordering-based local search, where a solution is described via a topological ordering of the variables. We show that given such a topological ordering, we can compute an optimal DAG whose ordering is within inversion distance r in subexponential FPT time; the parameter r allows to balance between solution quality and running time of the local search algorithm. This running time bound can be achieved for BNSL without any structural constraints and for all structural constraints that can be expressed via a sum of weights that are associated with each parent set. We show that for other modification operations on the variable orderings, algorithms with an FPT time for r are unlikely. We also outline the limits of ordering-based local search by showing that it cannot be used for common structural constraints on the moralized graph of the network.

IJCAI Conference 2021 Conference Paper

On the Parameterized Complexity of Polytree Learning

• Niels Grüttemeier
• Christian Komusiewicz
• Nils Morawietz

A Bayesian network is a directed acyclic graph that represents statistical dependencies between variables of a joint probability distribution. A fundamental task in data science is to learn a Bayesian network from observed data. Polytree Learning is the problem of learning an optimal Bayesian network that fulfills the additional property that its underlying undirected graph is a forest. In this work, we revisit the complexity of Polytree Learning. We show that Polytree Learning can be solved in single-exponential FPT time for the number of variables. Moreover, we consider the influence of d, the number of variables that might receive a nonempty parent set in the final DAG on the complexity of Polytree Learning. We show that Polytree Learning is presumably not fixed-parameter tractable for d, unlike Bayesian network learning which is fixed-parameter tractable for d. Finally, we show that if d and the maximum parent set size are bounded, then we can obtain efficient algorithms.

IJCAI Conference 2020 Conference Paper

Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis

• Niels Grüttemeier
• Christian Komusiewicz

We study the problem of learning the structure of an optimal Bayesian network when additional structural constraints are posed on the network or on its moralized graph. More precisely, we consider the constraint that the moralized graph can be transformed to a graph from a sparse graph class Π by at most k vertex deletions. We show that for Π being the graphs with maximum degree 1, an optimal network can be computed in polynomial time when k is constant, extending previous work that gave an algorithm with such a running time for Π being the class of edgeless graphs [Korhonen & Parviainen, NIPS 2015]. We then show that further extensions or improvements are presumably impossible. For example, we show that when Π is the set of graphs in which each component has size at most three, then learning an optimal network is NP-hard even if k=0. Finally, we show that learning an optimal network with at most k edges in the moralized graph presumably is not fixed-parameter tractable with respect to k and that, in contrast, computing an optimal network with at most k arcs can be computed is fixed-parameter tractable in k.

TCS Journal 2020 Journal Article

Revisiting the parameterized complexity of Maximum-Duo Preservation String Mapping

• Christian Komusiewicz
• Mateus de Oliveira Oliveira
• Meirav Zehavi

In the Maximum-Duo Preservation String Mapping (Max-Duo PSM) problem, the input consists of two related strings A and B of length n and a nonnegative integer k. The objective is to determine whether there exists a mapping m from the set of positions of A to the set of positions of B that maps only to positions with the same character and preserves at least k duos, which are pairs of adjacent positions. We develop a randomized algorithm that solves Max-Duo PSM in 4 k ⋅ n O ( 1 ) time, and a deterministic algorithm that solves this problem in 6. 855 k ⋅ n O ( 1 ) time. The previous best known (deterministic) algorithm for this problem has ( 8 e ) 2 k + o ( k ) ⋅ n O ( 1 ) running time [Beretta et al. (2016) [1, 2]]. We also show that Max-Duo PSM admits a problem kernel of size O ( k 3 ), improving upon the previous best known problem kernel of size O ( k 6 ).

AAAI Conference 2017 Conference Paper

Systematic Exploration of Larger Local Search Neighborhoods for the Minimum Vertex Cover Problem

• Maximilian Katzmann
• Christian Komusiewicz

We investigate the potential of exhaustively exploring larger neighborhoods in local search algorithms for MINIMUM VER- TEX COVER. More precisely, we study whether, for moderate values of k, it is feasible and worthwhile to determine, given a graph G with vertex cover C, if there is a k-swap S such that (C \S)∪(S \C) is a smaller vertex cover of G. First, we describe an algorithm running in ΔO(k) · n time for searching the k-swap neighborhood on n-vertex graphs with maximum degree Δ. Then, we demonstrate that, by devising additional pruning rules that decrease the size of the search space, this algorithm can be implemented so that it solves the problem quickly for k ≈ 20. Finally, we show that it is worthwhile to consider moderately-sized k-swap neighborhoods. For our benchmark data set, we show that when combining our algorithm with a hill-climbing approach, the solution quality improves quickly with the radius k of the local search neighborhood and that in most cases optimal solutions can be found by setting k = 21.

AIJ Journal 2016 Journal Article

H-index manipulation by merging articles: Models, theory, and experiments

• René van Bevern
• Christian Komusiewicz
• Rolf Niedermeier
• Manuel Sorge
• Toby Walsh

An author's profile on Google Scholar consists of indexed articles and associated data, such as the number of citations and the H-index. The author is allowed to merge articles; this may affect the H-index. We analyze the (parameterized) computational complexity of maximizing the H-index using article merges. Herein, to model realistic manipulation scenarios, we define a compatibility graph whose edges correspond to plausible merges. Moreover, we consider several different measures for computing the citation count of a merged article. For the measure used by Google Scholar, we give an algorithm that maximizes the H-index in linear time if the compatibility graph has constant-size connected components. In contrast, if we allow to merge arbitrary articles (that is, for compatibility graphs that are cliques), then already increasing the H-index by one is NP-hard. Experiments on Google Scholar profiles of AI researchers show that the H-index can be manipulated substantially only if one merges articles with highly dissimilar titles.

ECAI Conference 2016 Conference Paper

h-Index Manipulation by Undoing Merges

• René van Bevern
• Christian Komusiewicz
• Hendrik Molter
• Rolf Niedermeier
• Manuel Sorge
• Toby Walsh

The h-index is an important bibliographic measure used to assess the performance of researchers. Van Bevern et al. [Artif. Intel. , to appear] showed that, despite computational worst-case hardness results, substantial manipulation of the h-index of Google Scholar author profiles is possible by merging articles. Complementing this work, we study the opposite operation, the splitting of articles, which is arguably the more natural operation for manipulation and which is also allowed within Google Scholar. We present numerous results on computational complexity (from linear-time algorithms to parameterized computational hardness results) and empirically indicate that at least small improvements of the h-index by splitting merged articles are easily achievable.

TCS Journal 2016 Journal Article

Parameterized complexity of critical node cuts

• Danny Hermelin
• Moshe Kaspi
• Christian Komusiewicz
• Barak Navon

We consider the following graph cut problem called Critical Node Cut (CNC): Given a graph G on n vertices, and two positive integers k and x, determine whether G has a set of k vertices whose removal leaves G with at most x connected pairs of vertices. We analyze this problem in the framework of parameterized complexity. That is, we are interested in whether or not this problem is solvable in f ( κ ) ⋅ n O ( 1 ) time (i. e. , whether or not it is fixed-parameter tractable), for various natural parameters κ. We consider four such parameters: • The size k of the required cut. • The upper bound x on the number of remaining connected pairs. • The lower bound y on the number of connected pairs to be removed. • The treewidth w of G. We determine whether or not CNC is fixed-parameter tractable for each of these parameters. We determine this also for all possible aggregations of these four parameters, apart from w + k. Moreover, we also determine whether or not CNC admits a polynomial kernel for all these parameterizations. That is, whether or not there is an algorithm that reduces each instance of CNC in polynomial time to an equivalent instance of size κ O ( 1 ), where κ is the given parameter.

IJCAI Conference 2015 Conference Paper

H-Index Manipulation by Merging Articles: Models, Theory, and Experiments

• Ren
• eacute; van Bevern
• Christian Komusiewicz
• Rolf Niedermeier
• Manuel Sorge
• Toby Walsh

An author’s profile on Google Scholar consists of indexed articles and associated data, such as the number of citations and the H-index. The author is allowed to merge articles, which may affect the H-index. We analyze the parameterized complexity of maximizing the H-index using article merges. Herein, to model realistic manipulation scenarios, we define a compatability graph whose edges correspond to plausible merges. Moreover, we consider multiple possible measures for computing the citation count of a merged article. For the measure used by Google Scholar, we give an algorithm that maximizes the H-index in linear time if the compatibility graph has constant-size connected components. In contrast, if we allow to merge arbitrary articles, then already increasing the H-index by one is NP-hard. Experiments on Google Scholar profiles of AI researchers show that the H-index can be manipulated substantially only by merging articles with highly dissimilar titles, which would be easy to discover.

TCS Journal 2015 Journal Article

Towards an algorithmic guide to Spiral Galaxies

• Guillaume Fertin
• Shahrad Jamshidi
• Christian Komusiewicz

We study the one-player game Spiral Galaxies from an algorithmic viewpoint. Spiral Galaxies has been shown to be NP-hard [6] more than a decade ago, but so far it seems that no one has dared exploring its algorithmic universe. We take this trip and visit some of its corners.

TCS Journal 2014 Journal Article

Local search for string problems: Brute-force is essentially optimal

• Jiong Guo
• Danny Hermelin
• Christian Komusiewicz

We address the problem of whether the brute-force procedure for the local improvement step in a local search algorithm can substantially be improved when applied to classical NP-hard string problems. We examine four of the more prominent problems in this domain: Closest String, Longest Common Subsequence, Shortest Common Supersequence, and Shortest Common Superstring. Herein, we consider arguably the most fundamental string distance measure, namely the Hamming distance, which has been applied in practical local search implementations for string problems. Our results indicate that for all four problems, the brute-force algorithm cannot be considerably improved.

SODA Conference 2014 Conference Paper

Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable

• Laurent Bulteau
• Christian Komusiewicz

TCS Journal 2014 Journal Article

On the parameterized complexity of consensus clustering

• Martin Dörnfelder
• Jiong Guo
• Christian Komusiewicz
• Mathias Weller

Given a collection C of partitions of a base set S, the NP-hard Consensus Clustering problem asks for a partition of S which has a total Mirkin distance of at most t to the partitions in C, where t is a nonnegative integer. We present a parameterized algorithm for Consensus Clustering with running time O ( 4. 24 k ⋅ k 3 + | C | ⋅ | S | 2 ), where k: = t / | C | is the average Mirkin distance of the solution partition to the partitions of C. Furthermore, we strengthen previous hardness results for Consensus Clustering, showing that Consensus Clustering remains NP-hard even when all input partitions contain at most two subsets. Finally, we study a local search variant of Consensus Clustering, showing W[1]-hardness for the parameter “radius of the Mirkin-distance neighborhood”. In the process, we also consider a local search variant of the related Cluster Editing problem, showing W[1]-hardness for the parameter “radius of the edge modification neighborhood”.

MFCS Conference 2012 Conference Paper

New Races in Parameterized Algorithmics

• Christian Komusiewicz
• Rolf Niedermeier

Abstract Once having classified an NP-hard problem fixed-parameter tractable with respect to a certain parameter, the race for the most efficient fixed-parameter algorithm starts. Herein, the attention usually focuses on improving the running time factor exponential in the considered parameter, and, in case of kernelization algorithms, to improve the bound on the kernel size. Both from a practical as well as a theoretical point of view, however, there are further aspects of efficiency that deserve attention. We discuss several of these aspects and particularly focus on the search for “stronger parameterizations” in developing fixed-parameter algorithms.

AAAI Conference 2010 Conference Paper

Exact Algorithms and Experiments for Hierarchical Tree Clustering

• Sepp Hartung
• Jiong Guo
• Christian Komusiewicz
• Rolf Niedermeier
• Johannes Uhlmann

We perform new theoretical as well as first-time experimental studies for the NP-hard problem to find a closest ultrametric for given dissimilarity data on pairs. This is a central problem in the area of hierarchical clustering, where so far only polynomial-time approximation algorithms were known. In contrast, we develop efficient preprocessing algorithms (known as kernelization in parameterized algorithmics) with provable performance guarantees and a simple search tree algorithm. These are used to find optimal solutions. Our experiments with synthetic and biological data show the effectiveness of our algorithms and demonstrate that an approximation algorithm due to Ailon and Charikar [FOCS 2005] often gives (almost) optimal solutions.

TCS Journal 2009 Journal Article

Isolation concepts for clique enumeration: Comparison and computational experiments

• Falk Hüffner
• Christian Komusiewicz
• Hannes Moser
• Rolf Niedermeier

We do computational studies concerning the enumeration of isolated cliques in graphs. Isolation, as recently introduced, measures the degree of connectedness of the cliques to the rest of the graph. Isolation helps both in getting faster algorithms for the enumeration of maximal general cliques and in filtering out cliques with special semantics. We compare three isolation concepts and their combination with two enumeration modi for maximal cliques (“isolated maximal” vs “maximal isolated”). All studied concepts exhibit the fixed-parameter tractability of the enumeration task with respect to the parameter “degree of isolation”. We provide a first systematic experimental study of the corresponding enumeration algorithms, using synthetic graphs (in the G n, m, p model), financial networks, and a music artist similarity network, proposing the enumeration of isolated cliques as a useful instrument in analyzing financial and social networks.

TCS Journal 2009 Journal Article

Isolation concepts for efficiently enumerating dense subgraphs

• Christian Komusiewicz
• Falk Hüffner
• Hannes Moser
• Rolf Niedermeier

In an undirected graph G = ( V, E ), a set of k vertices is called c -isolated if it has less than c ⋅ k outgoing edges. Ito and Iwama [H. Ito, K. Iwama, Enumeration of isolated cliques and pseudo-cliques, ACM Transactions on Algorithms (2008) (in press)] gave an algorithm to enumerate all c -isolated maximal cliques in O ( 4 c ⋅ c 4 ⋅ | E | ) time. We extend this to enumerating all maximal c -isolated cliques (which are a superset) and improve the running time bound to O ( 2. 8 9 c ⋅ c 2 ⋅ | E | ), using modifications which also facilitate parallelizing the enumeration. Moreover, we introduce a more restricted and a more general isolation concept and show that both lead to faster enumeration algorithms. Finally, we extend our considerations to s -plexes (a relaxation of the clique notion), providing a W[1]-hardness result when the size of the s -plex is the parameter and a fixed-parameter algorithm for enumerating isolated s -plexes when the parameter describes the degree of isolation.