The concept of Roman domination has recently been studied concerning enumerating and counting in F. N. Abu-Khzam et al. (WG 2022). More technically speaking, a function that assigns 0,1,2 to the vertices of an undirected graph is called a Roman dominating function if each vertex assigned zero has a neighbor assigned two. Such a function is called minimal if decreasing any assignment to any vertex would yield a function that is no longer a Roman dominating function. It has been shown that minimal Roman dominating functions can be enumerated with polynomial delay, i.e., between any two outputs of a solution, no more than polynomial time will elapse. This contrasts what is known about minimal dominating sets, where the question whether or not these can be enumerated with polynomial delay is open for more than 40 years. This makes the concept of Roman domination rather special and interesting among the many variants of domination problems studied in the literature, as it has been shown for several of these variants that the question of enumerating minimal solutions is tightly linked to that of enumerating minimal dominating sets, see M. Kanté et al. in SIAM J. Disc. Math., 2014. The running time of the mentioned enumeration algorithm for minimal Roman dominating functions (Abu-Khzam et al., WG 2022) could be estimated as 𝒪(1.9332ⁿ) on general graphs of order n. Here, we focus on special graph classes, as has been also done for enumerating minimal dominating sets before. More specifically, for chordal graphs, we present an enumeration algorithm running in time 𝒪(1.8940ⁿ). It is unknown if this gives a tight bound on the maximum number of minimal Roman dominating functions in chordal graphs. For interval graphs, we can lower this time bound further to 𝒪(1.7321ⁿ), which also matches the known lower bound concerning the maximum number of minimal Roman dominating functions. We can also provide a matching lower and upper bound for forests, which is (incidentally) the same, namely 𝒪^*(√3ⁿ). Furthermore, we present an optimal enumeration algorithm running in time 𝒪^*(∛3ⁿ) for split graphs and for cobipartite graphs, i.e., we can also give a matching lower bound example for these graph classes. Hence, our enumeration algorithms for interval graphs, forests, split graphs and cobipartite graphs are all optimal. The importance of our results stems from the fact that, for other types of domination problems, optimal enumeration algorithms are not always found. Interestingly, we use a different form of analysis for the running times of our different algorithms, and the branchings had to be tailored and tweaked to obtain the intended optimality results. Our Roman dominating functions enumeration algorithm for trees and forests is distinctively different from the one for minimal dominating sets by Rote (SODA 2019).Our approach also allows to give concrete formulas for counting minimal Roman dominating functions on more concrete graph families like paths.

Abstract. The question to enumerate all (inclusionwise) minimal connected dominating sets in a graph of order [Formula: see text] in time significantly less than [Formula: see text] is an open question that was asked in many places. We answer this question affirmatively, by providing an enumeration algorithm that runs in time [Formula: see text], using polynomial space only. The key to this result is the consideration of this enumeration problem on 2-degenerate graphs, which is proven to be possible in time [Formula: see text]. Apart from solving this old open question, we also show new lower bound results. More precisely, we construct a family of graphs of order [Formula: see text] with [Formula: see text] many minimal connected dominating sets, while previous examples achieved [Formula: see text]. Our example happens to yield 4-degenerate graphs. Additionally, we give lower bounds for the previously not considered classes of 2-degenerate and of 3-degenerate graphs, which are [Formula: see text] and [Formula: see text], respectively. We also address essential questions concerning output-sensitive enumeration. Namely, we give reasons why our algorithm cannot be turned into an enumeration algorithm that guarantees polynomial delay without much effort. More precisely, we prove that it is NP -complete to decide, given a graph [Formula: see text] and a vertex set [Formula: see text], if there exists a minimal connected dominating set [Formula: see text] with [Formula: see text], even if [Formula: see text] is known to be 2-degenerate. Our reduction also shows that even any subexponential delay is not easy to achieve for enumerating minimal connected dominating sets. Another reduction shows that no FPT -algorithms can be expected for this extension problem concerning minimal connected dominating sets, parameterized by [Formula: see text]. This also adds one more problem to the still rather few natural parameterized problems that are complete for the parameterized complexity class W [3]. We also relate our enumeration problem to the famous Hitting Set Transversal problem, a problem open for more than four decades, which can be phrased in our context as the question to enumerate all minimal dominating sets of a graph with polynomial delay, by showing that a polynomial-delay enumeration algorithm for minimal connected dominating sets implies an affirmative algorithmic (polynomial-delay) solution to the Hitting Set Transversal problem.

Abstract Roman domination is one of the many variants of domination that keeps most of the complexity features of the classical domination problem. We prove that Roman domination behaves differently in two aspects: enumeration and extension. We develop non-trivial enumeration algorithms for minimal Roman dominating functions with polynomial delay and polynomial space. Recall that the existence of a similar enumeration result for minimal dominating sets is open for decades. Our result is based on a polynomial-time algorithm for Extension Roman Domination : Given a graph $$G=(V,E)$$ G = ( V , E ) and a function $$f:V\rightarrow \{0,1,2\}$$ f : V → { 0 , 1 , 2 } , is there a minimal Roman dominating function $$\tilde{f}$$ f ~ with $$f\le \tilde{f}$$ f ≤ f ~ ? Here, $$\le $$ ≤ lifts $$0< 1< 2$$ 0 < 1 < 2 pointwise; minimality is understood in this order. Our enumeration algorithm is also analyzed from an input-sensitive viewpoint, leading to a run-time estimate of $$\mathcal {O}(1.9332^n)$$ O ( 1 . 9332 n ) for graphs of order n ; this is complemented by a lower bound example of $$\Omega (1.7441^n)$$ Ω ( 1 . 7441 n ) .

The question to enumerate all (inclusion-wise) minimal connected dominating sets in a graph of order n in time significantly less than 2ⁿ is an open question that was asked in many places. We answer this question affirmatively, by providing an enumeration algorithm that runs in time 𝒪(1.9896ⁿ), using polynomial space only. The key to this result is the consideration of this enumeration problem on 2-degenerate graphs, which is proven to be possible in time 𝒪(1.9767ⁿ). Apart from solving this old open question, we also show new lower bound results. More precisely, we construct a family of graphs of order n with Ω(1.4890ⁿ) many minimal connected dominating sets, while previous examples achieved Ω(1.4422ⁿ). Our example happens to yield 4-degenerate graphs. Additionally, we give lower bounds for the previously not considered classes of 2-degenerate and of 3-degenerate graphs, which are Ω(1.3195ⁿ) and Ω(1.4723ⁿ), respectively. We also address essential questions concerning output-sensitive enumeration. Namely, we give reasons why our algorithm cannot be turned into an enumeration algorithm that guarantees polynomial delay without much efforts. More precisely, we prove that it is NP-complete to decide, given a graph G and a vertex set U, if there exists a minimal connected dominating set D with U ⊆ D, even if G is known to be 2-degenerate. Our reduction also shows that even any subexponential delay is not easy to achieve for enumerating minimal connected dominating sets. Another reduction shows that no FPT-algorithms can be expected for this extension problem concerning minimal connected dominating sets, parameterized by |U|. This also adds one more problem to the still rather few natural parameterized problems that are complete for the class W[3]. We also relate our enumeration problem to the famous open Hitting Set Transversal problem, which can be phrased in our context as the question to enumerate all minimal dominating sets of a graph with polynomial delay by showing that a polynomial-delay enumeration algorithm for minimal connected dominating sets implies an affirmative algorithmic solution to the Hitting Set Transversal problem.

We propose a lossy graph compression approach based on mapping the vertices of a graph to points in a k-dimensional space, where k is a fixed constant, with distances between them indicating their adjacency status.

Graphics Processing Units (GPUs) are gaining notable popularity due to their affordable high performance multi-core architecture. They are particularly useful for massive computations that involve large data sets. In this paper, we present a highly scalable approach for the NP-hard Vertex Cover problem. Our method is based on an advanced data structure to reduce memory usage for more parallelism and we propose a load balancing scheme that is effective for multiGPU architectures. Our parallel algorithm was implemented on multiple AMD GPUs using OpenCL. Experimental results show that our proposed approach can achieve significant speedups on the hard instances of the DIMACS benchmarks as well as the notoriously hard 120-Cell graph and its variants.

Classical clustering problems search for a partition of objects into a fixed number of clusters. In many scenarios however the number of clusters is not known or necessarily fixed. Further, clusters are sometimes only considered to be of significance if they have a certain size. We discuss clustering into sets of minimum cardinality k without a fixed number of sets and present a general model for these types of problems. This general framework allows the comparison of different measures to assess the quality of a clustering. We specifically consider nine quality-measures and classify the complexity of the resulting problems with respect to k. Further, we derive some polynomial-time solvable cases for k = 2 with connections to matching-type problems which, among other graph problems, then are used to compute approximations for larger values of k.

We introduce the notion of a virtual topology and explore the use of search-tree indexing to achieve highly scalable parallel search-tree algorithms for NP-hard problems. Vertex Cover and Cluster Editing are used as case studies.

Current generation supercomputers have over one million cores awaiting highly demanding computations and applications. An area that could largely benefit from such processing capabilities is naturally that of exact algorithms for NP-hard problems. We propose a general implementation framework that targets highly scalable parallel exact algorithms for NP-hard graph problems. We tackle the problems of efficiency and scalability by combining a fully decentralized dynamic load balancing strategy with special implementation techniques for exact graph algorithms. As a case-study, we use our framework to implement parallel algorithms for the VERTEX COVER and DOMINATING SET problems. We present experimental results that show notable improved running times on all types of input instances.

Proteins are initially linear chains of amino acids that fold, under the influence of several chemical and physical factors, into their 3-dimensional structures. Due to the importance of this problem and since laboratory techniques are not always feasible, computational methods for characterizing protein structures have been proposed. In this paper, we present a particle swarm optimization (PSO) based algorithm for predicting protein structures in the 3D HP model. Starting from a small set of potential solutions, our algorithm efficiently explores the search space of candidate solutions and returns 3D protein structures with minimal energy. To test our algorithm, we use two sets of benchmark sequences of different lengths. It is found that the results of the PSO algorithm are better than those of previous algorithms.

Practical methods are presented for computing exact solutions to the maximum clique problem on graphs that are too large to fit within core memory. These methods use a combination of in-core and out-of-core techniques, recursively dissecting large graphs into manageable components. A global solution to the maximum clique problem is derived from local solutions generated for each of the individual components. Parallelizing the search within these components is instrumental in improving the running times of the algorithms.

In the maximum common subgraph (MCS) problem, we are given a pair of graphs and asked to find the largest induced subgraph common to them both. With its plethora of applications, MCS is a familiar and challenging problem. Many algorithms exist that can deliver optimal MCS solutions, but whose asymptotic worst-case run times fail to do better than mere brute-force, which is exponential in the order of the smaller graph. In this paper, we present a faster solution to MCS. We transform an essential part of the search process into the task of enumerating maximal independent sets in only a part of only one of the input graphs. This is made possible by exploiting an efficient decomposition of a graph into a minimum vertex cover and the maximum independent set in its complement. The result is an algorithm whose run time is bounded by a function exponential in the order of the smaller cover rather than in the order of the smaller graph.

Summary form only given. Two kernelization methods for the vertex cover problem are investigated. The first, LP-kernelization has been in prior use and is known to produce predictable results. The second, crown reduction, is newer and faster but generates more variable results. Previously-unknown connections between these powerful methods are established. It is also shown that the problem of finding an induced crown-free subgraph in an arbitrary graph is decidable in polynomial time. Applications of crown structures are discussed.

Graph-theoretical approaches to biological network analysis have proven to be effective for small networks but are computationally infeasible for comprehensive genome-scale systems-level elucidation of these networks. The difficulty lies in the NP-hard nature of many global systems biology problems that, in practice, translates to exponential (or worse) run times for finding exact optimal solutions. Moreover, these problems, especially those of an enumerative flavor, are often memory-intensive and must share very large sets of data effectively across many processors. For example, the enumeration of maximal cliques - a core component in gene expression networks analysis, cis regulatory motif finding, and the study of quantitative trait loci for high-throughput molecular phenotypes can result in as many as 3^n/3 maximal cliques for a graph with n vertices. Memory requirements to store those cliques reach terabyte scales even on modest-sized genomes. Emerging hardware architectures with ultra-large globally addressable memory such as the SGI Altix and Cray X1 seem to be well suited for addressing these types of data-intensive problems in systems biology. This paper presents a novel framework that provides exact, parallel and scalable solutions to various graph-theoretical approaches to genome-scale elucidation of biological networks. This framework takes advantage of these large-memory architectures by creating globally addressable bitmap memory indices with potentially high compression rates, fast bitwise-logical operations, and reduced search space. Augmented with recent theoretical advancements based on fixed-parameter tractability, this framework produces computationally feasible performance for genome-scale combinatorial problems of systems biology.