
AbuKhzam, Faisal N.; Bazgan, Cristina; Casel, Katrin; Fernau, Henning Clustering with LowerBounded Sizes  A General GraphTheoretic Framework. Algorithmica 2018: 25172550
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 qualitymeasures and classify the complexity of the resulting problems with respect to \(k\). Further, we derive some polynomialtime solvable cases for \(k=2\) with connections to matchingtype problems which, among other graph problems, then are used to compute approximations for larger values of \(k\).

Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Klein, KimManuel; Lampis, Michael; Liedloff, Mathieu; Monnot, Jérôme; Paschos, Vangelis Th. The many facets of upper domination. Theoretical Computer Science 2018: 225
This paper studies Upper Domination, i.e., the problem of computing the maximum cardinality of a minimal dominating set in a graph with respect to classical and parameterised complexity as well as approximability.

Casel, Katrin Resolving Conflicts for LowerBounded Clustering. International Symposium on Parameterized and Exact Computation (IPEC) 2018
This paper considers the effect of nonmetric distances for lowerbounded clustering, i.e., the problem of computing a partition for a given set of objects with pairwise distance, such that each set has a certain minimum cardinality (as required for anonymisation or balanced facility location problems). We discuss lowerbounded clustering with the objective to minimise the maximum radius or diameter of the clusters. For these problems there exists a 2approximation but only if the pairwise distance on the objects satisfies the triangle inequality, without this property no polynomialtime constant factor approximation is possible. We try to resolve or at least soften this effect of nonmetric distances by devising particular strategies to deal with violations of the triangle inequality ("conflicts"). With parameterised algorithmics, we find that if the number of such conflicts is not too large, constant factor approximations can still be computed efficiently. In particular, we introduce parameterised approximations with respect to not just the number of conflicts but also for the vertex cover number of the "conflict graph" (graph induced by conflicts). Interestingly, we salvage the approximation ratio of 2 for diameter while for radius it is only possible to show a ratio of 3. For the parameter vertex cover number of the conflict graph this worsening in ratio is shown to be unavoidable, unless FPT=W[2]. We further discuss improvements for diameter by choosing the (induced) \(P_3\)cover number of the conflict graph as parameter and complement these by showing that, unless FPT=W[1], there exists no constant factor parameterised approximation with respect to the parameter split vertex deletion set.

Casel, Katrin; EstradaMoreno, Alejandro; Fernau, Henning; RodríguezVelázquez, Juan Alberto Weak total resolvability in graphs. Discussiones Mathematicae Graph Theory 2016: 185210
A vertex \(v in V (G)\) is said to distinguish two vertices \(x, y in V (G)\) of a graph \(G\) if the distance from \(v\) to \(x\) is different from the distance from \(v\) to \(y\). A set \(W subseteq V (G)\) is a total resolving set for a graph \(G\) if for every pair of vertices \(x, y in V (G)\), there exists some vertex \(w \in W  \x, y\}\) which distinguishes \(x\) and \(y\), while \(W\) is a weak total resolving set if for every \(x in V (G)  W\) and \(y \in W\), there exists some \(w \in W \{y\}\) which distinguishes \(x\) and \(y\). A weak total resolving set of minimum cardinality is called a weak total metric basis of \(G\) and its cardinality the weak total metric dimension of \(G\). Our main contributions are the following ones: (a) Graphs with small and large weak total metric bases are characterised. (b) We explore the (tight) relation to independent 2domination. (c) We introduce a new graph parameter, called weak total adjacency dimension and present results that are analogous to those presented for weak total dimension. (d) For trees, we derive a characterisation of the weak total (adjacency) metric dimension. Also, exact figures for our parameters are presented for (generalised) fans and wheels. (e) We show that for Cartesian product graphs, the weak total (adjacency) metric dimension is usually pretty small. (f) The weak total (adjacency) dimension is studied for lexicographic products of graphs.

Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Klein, KimManuel; Lampis, Michael; Liedloff, Mathieu; Monnot, Jérôme; Paschos, Vangelis Th. Algorithmic Aspects of Upper Domination: A Parameterised Perspective. Algorithmic Aspects in Information and Management (AAIM) 2016: 113124
This paper studies Upper Domination, i.e., the problem of computing the maximum cardinality of a minimal dominating set in a graph, with a focus on parameterised complexity. Our main results include W[1]hardness for Upper Domination, contrasting FPT membership for the parameterised dual CoUpper Domination. The study of structural properties also yields some insight into Upper Total Domination. We further consider graphs of bounded degree and derive upper and lower bounds for kernelisation.

Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning On the Complexity Landscape of the Domination Chain. Algorithms and Discrete Applied Mathematics (CALDAM) 2016: 6172
In this paper, we survey and supplement the complexity landscape of the domination chain parameters as a whole, including classifications according to approximability and parameterised complexity. Moreover, we provide clear pointers to yet open questions. As this posed the majority of hitherto unsettled problems, we focus on Upper Irredundance and Lower Irredundance that correspond to finding the largest irredundant set and resp. the smallest maximal irredundant set. The problems are proved NPhard even for planar cubic graphs. While Lower Irredundance is proved not \(c \log(n)\)approximable in polynomial time unless \(NP subseteq DTIME(n^\log \log n})\), no such result is known for Upper Irredundance. Their complementary versions are constantfactor approximable in polynomial time. All these four versions are APXhard even on cubic graphs.

Casel, Katrin; Fernau, Henning; Gaspers, Serge; Gras, Benjamin; Schmid, Markus L. On the Complexity of GrammarBased Compression over Fixed Alphabets. International Colloquium on Automata, Languages, and Programming (ICALP) 2016: 122:1122:14
It is shown that the shortestgrammar problem remains NPcomplete if the alphabet is fixed and has a size of at least 24 (which settles an open question). On the other hand, this problem can be solved in polynomialtime, if the number of nonterminals is bounded, which is shown by encoding the problem as a problem on graphs with interval structure. Furthermore, we present an O(3n) exact exponentialtime algorithm, based on dynamic programming. Similar results are also given for 1level grammars, i.e., grammars for which only the start rule contains nonterminals on the right side (thus, investigating the impact of the "hierarchical depth" on the complexity of the shortestgrammar problem).

AbuKhzam, Faisal N.; Bazgan, Cristina; Casel, Katrin; Fernau, Henning Building Clusters with LowerBounded Sizes. International Symposium on Algorithms and Computation (ISAAC) 2016: 4:14:13
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 qualitymeasures and classify the complexity of the resulting problems with respect to \(k\). Further, we derive some polynomialtime solvable cases for \(k = 2\) with connections to matchingtype problems which, among other graph problems, then are used to compute approximations for larger values of \(k\).

Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Klein, KimManuel; Lampis, Michael; Liedloff, Mathieu; Monnot, Jérôme; Paschos, Vangelis Th. Upper Domination: Complexity and Approximation. Combinatorial Algorithms (IWOCA) 2016: 241252
We consider Upper Domination, the problem of finding a maximum cardinality minimal dominating set in a graph. We show that this problem does not admit an \(n^{1\epsilon }\) approximation for any \(\epsilon >0\), making it significantly harder than Dominating Set, while it remains hard even on severely restricted special cases, such as cubic graphs (APXhard), and planar subcubic graphs (NPhard). We complement our negative results by showing that the problem admits an \(O(\varDelta )\) approximation on graphs of maximum degree \(\varDelta\) , as well as an EPTAS on planar graphs. Along the way, we also derive essentially tight \(n^{1\frac{1}{d}}\) upper and lower bounds on the approximability of the related problem Maximum Minimal Hitting Set on duniform hypergraphs, generalising known results for Maximum Minimal Vertex Cover.