2021 [ nach oben ]

• 
  Casel, Katrin; Fernau, Henning; Gaspers, Serge; Gras, Benjamin; Schmid, Markus L.On the Complexity of the Smallest Grammar Problem over Fixed Alphabets. Theory of Computing Systems 2021: 344–409
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  In the smallest grammar problem, we are given a word \(w\)and we want to compute a preferably small context-free grammar \(G\) for the singleton language \(\{w\}\) (where the size of a grammar is the sum of the sizes of its rules, and the size of a rule is measured by the length of its right side). It is known that, for unbounded alphabets, the decision variant of this problem is \(\mathsf{NP}\)-hard and the optimisation variant does not allow a polynomial-time approximation scheme, unless \(\mathsf{P}\) = \(\mathsf{NP}\). We settle the long-standing open problem whether these hardness results also hold for the more realistic case of a constant-size alphabet. More precisely, it is shown that the smallest grammar problem remains \(\mathsf{NP}\)-complete (and its optimisation version is \(\mathsf{APX}\)-hard), even if the alphabet is fixed and has size of at least 17. The corresponding reduction is robust in the sense that it also works for an alternative size-measure of grammars that is commonly used in the literature (i.e., a size measure also taking the number of rules into account), and it also allows to conclude that even computing the number of rules required by a smallest grammar is a hard problem. On the other hand, if the number of nonterminals (or, equivalently, the number of rules) is bounded by a constant, then the smallest grammar problem can be solved in polynomial time, which is shown by encoding it as a problem on graphs with interval structure. However, treating the number of rules as a parameter (in terms of parameterised complexity) yields \(\mathsf{W}\)[1]-hardness. Furthermore, we present an \(O(3^{|w|})\) exact exponential-time algorithm, based on dynamic programming. These three main questions are also investigated for 1-level grammars, i.e., grammars for which only the start rule contains nonterminals on the right side; thus, investigating the impact of the ``hierarchical depth'' of grammars on the complexity of the smallest grammar problem. In this regard, we obtain for 1-level grammars similar, but slightly stronger results.
  @article{casel2020article, abstract = {In the smallest grammar problem, we are given a word \(w\)and we want to compute a preferably small context-free grammar \(G\) for the singleton language \(\{w\}\) (where the size of a grammar is the sum of the sizes of its rules, and the size of a rule is measured by the length of its right side). It is known that, for unbounded alphabets, the decision variant of this problem is \(\mathsf{NP}\)-hard and the optimisation variant does not allow a polynomial-time approximation scheme, unless \(\mathsf{P}\) = \(\mathsf{NP}\). We settle the long-standing open problem whether these hardness results also hold for the more realistic case of a constant-size alphabet. More precisely, it is shown that the smallest grammar problem remains \(\mathsf{NP}\)-complete (and its optimisation version is \(\mathsf{APX}\)-hard), even if the alphabet is fixed and has size of at least 17. The corresponding reduction is robust in the sense that it also works for an alternative size-measure of grammars that is commonly used in the literature (i.e., a size measure also taking the number of rules into account), and it also allows to conclude that even computing the number of rules required by a smallest grammar is a hard problem. On the other hand, if the number of nonterminals (or, equivalently, the number of rules) is bounded by a constant, then the smallest grammar problem can be solved in polynomial time, which is shown by encoding it as a problem on graphs with interval structure. However, treating the number of rules as a parameter (in terms of parameterised complexity) yields \(\mathsf{W}\)[1]-hardness. Furthermore, we present an \(O(3^{|w|})\) exact exponential-time algorithm, based on dynamic programming. These three main questions are also investigated for 1-level grammars, i.e., grammars for which only the start rule contains nonterminals on the right side; thus, investigating the impact of the ``hierarchical depth'' of grammars on the complexity of the smallest grammar problem. In this regard, we obtain for 1-level grammars similar, but slightly stronger results.}, author = {Casel, Katrin and Fernau, Henning and Gaspers, Serge and Gras, Benjamin and Schmid, Markus L.}, editor = {Springer}, journal = {Theory of Computing Systems}, keywords = {markuslschmid katrincasel benjamingras sergegaspers tocs henningfernau year2020}, number = 2, pages = {344–409}, title = {On the Complexity of the Smallest Grammar Problem over Fixed Alphabets}, volume = 65, year = 2021 }
• 
  Casel, Katrin; Schmid, Markus L.Fine-Grained Complexity of Regular Path Queries. International Conference on Database Theory (ICDT) 2021
  [ Abstract ] [ BibTeX ] [ Download ]
   
  A regular path query (RPQ) is a regular expression \(q\) that returns all node pairs \((u, v)\) from a graph database that are connected by an arbitrary path labelled with a word from \(L(q)\). The obvious algorithmic approach to RPQ-evaluation (called PG-approach), i.e., constructing the product graph between an NFA for \(q\) and the graph database, is appealing due to its simplicity and also leads to efficient algorithms. However, it is unclear whether the PG-approach is optimal. We address this question by thoroughly investigating which upper complexity bounds can be achieved by the PG-approach, and we complement these with conditional lower bounds (in the sense of the fine-grained complexity framework). A special focus is put on enumeration and delay bounds, as well as the data complexity perspective. A main insight is that we can achieve optimal (or near optimal) algorithms with the PG-approach, but the delay for enumeration is rather high (linear in the database). We explore three successful approaches towards enumeration with sub-linear delay: super-linear preprocessing, approximations of the solution sets, and restricted classes of RPQs.
  @inproceedings{casel2021finegrained, abstract = {A regular path query (RPQ) is a regular expression \(q\) that returns all node pairs \((u, v)\) from a graph database that are connected by an arbitrary path labelled with a word from \(L(q)\). The obvious algorithmic approach to RPQ-evaluation (called PG-approach), i.e., constructing the product graph between an NFA for \(q\) and the graph database, is appealing due to its simplicity and also leads to efficient algorithms. However, it is unclear whether the PG-approach is optimal. We address this question by thoroughly investigating which upper complexity bounds can be achieved by the PG-approach, and we complement these with conditional lower bounds (in the sense of the fine-grained complexity framework). A special focus is put on enumeration and delay bounds, as well as the data complexity perspective. A main insight is that we can achieve optimal (or near optimal) algorithms with the PG-approach, but the delay for enumeration is rather high (linear in the database). We explore three successful approaches towards enumeration with sub-linear delay: super-linear preprocessing, approximations of the solution sets, and restricted classes of RPQs.}, author = {Casel, Katrin and Schmid, Markus L.}, booktitle = {International Conference on Database Theory (ICDT)}, keywords = {markuslschmid katrincasel icdt year2021}, title = {Fine-Grained Complexity of Regular Path Queries}, year = 2021 }

2020 [ nach oben ]

• 
  Casel, Katrin; Dreier, Jan; Fernau, Henning; Gobbert, Moritz; Kuinke, Philipp; Sanchez Villaamil, Fernando; Schmid, Markus L.; van Leeuwen, Erik JanComplexity of independency and cliquy trees. Discrete Applied Mathematics 2020: 2-15
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  An independency (cliquy) tree of an \(n\)-vertex graph \(G\) is a spanning tree of \(G\) in which the set of leaves induces an independent set (clique). We study the problems of minimizing or maximizing the number of leaves of such trees, and fully characterize their parameterized complexity. We show that all four variants of deciding if an independency/cliquy tree with at least/most \(\ell\) leaves exists parameterized by \(\ell\) are either para-NP- or W[1]-hard. We prove that minimizing the number of leaves of a cliquy tree parameterized by the number of internal vertices is para-NP-hard too. However, we show that minimizing the number of leaves of an independency tree parameterized by the number \(k\) of internal vertices has an \(O^*(4^k)\)-time algorithm and a \(2k\) vertex kernel. Moreover, we prove that maximizing the number of leaves of an independency/cliquy tree parameterized by the number \(k\) of internal vertices both have an \(O^*(18^k)\)-time algorithm and an \(O(k\, 2^k)\) vertex kernel, but no polynomial kernel unless the polynomial hierarchy collapses to the third level. Finally, we present an \(O(3^n f(n))\)-time algorithm to find a spanning tree where the leaf set has a property that can be decided in \(f(n)\) time and has minimum or maximum size.
  @article{casel2020cliquy, abstract = {An independency (cliquy) tree of an \(n\)-vertex graph \(G\) is a spanning tree of \(G\) in which the set of leaves induces an independent set (clique). We study the problems of minimizing or maximizing the number of leaves of such trees, and fully characterize their parameterized complexity. We show that all four variants of deciding if an independency/cliquy tree with at least/most \(\ell\) leaves exists parameterized by \(\ell\) are either para-NP- or W[1]-hard. We prove that minimizing the number of leaves of a cliquy tree parameterized by the number of internal vertices is para-NP-hard too. However, we show that minimizing the number of leaves of an independency tree parameterized by the number \(k\) of internal vertices has an \(O^*(4^k)\)-time algorithm and a \(2k\) vertex kernel. Moreover, we prove that maximizing the number of leaves of an independency/cliquy tree parameterized by the number \(k\) of internal vertices both have an \(O^*(18^k)\)-time algorithm and an \(O(k\, 2^k)\) vertex kernel, but no polynomial kernel unless the polynomial hierarchy collapses to the third level. Finally, we present an \(O(3^n f(n))\)-time algorithm to find a spanning tree where the leaf set has a property that can be decided in \(f(n)\) time and has minimum or maximum size.}, author = {Casel, Katrin and Dreier, Jan and Fernau, Henning and Gobbert, Moritz and Kuinke, Philipp and Sanchez Villaamil, Fernando and Schmid, Markus L. and van Leeuwen, Erik Jan}, journal = {Discrete Applied Mathematics}, keywords = {erikjanvanleeuwen markuslschmid katrincasel jandreier fernandosanchezvillaamil moritzgobbert philippkuinke dam henningfernau year2020}, pages = {2-15}, title = {Complexity of independency and cliquy trees}, volume = 272, year = 2020 }
• 
  Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, HenningDomination chain: Characterisation, classical complexity, parameterised complexity and approximability. Discrete Applied Mathematics 2020: 23-42
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We survey the most important results regarding the domination chain parameters, including the characterisation of the domination sequence, complexity of exact and parameterised algorithms, and approximation and inapproximability ratios. We provide a number of new results for the upper and lower irredundance and their complements, and a few results for other domination chain problems. In particular, we analyse the structure of maximum irredundant sets and we provide new bounds on the upper irredundance number. We show several approximability results for upper and lower irredundance and their complements on general graphs; all four problems remain NP-hard even on planar cubic graphs and APX-hard on cubic graphs. Finally, we give some results on everywhere dense graphs, and study some related extension problems.
  @article{bazgan2020domination, abstract = {We survey the most important results regarding the domination chain parameters, including the characterisation of the domination sequence, complexity of exact and parameterised algorithms, and approximation and inapproximability ratios. We provide a number of new results for the upper and lower irredundance and their complements, and a few results for other domination chain problems. In particular, we analyse the structure of maximum irredundant sets and we provide new bounds on the upper irredundance number. We show several approximability results for upper and lower irredundance and their complements on general graphs; all four problems remain NP-hard even on planar cubic graphs and APX-hard on cubic graphs. Finally, we give some results on everywhere dense graphs, and study some related extension problems.}, author = {Bazgan, Cristina and Brankovic, Ljiljana and Casel, Katrin and Fernau, Henning}, journal = {Discrete Applied Mathematics}, keywords = {christinabazgan katrincasel ljiljanabrankovic dam henningfernau year2020}, pages = {23-42}, title = {Domination chain: Characterisation, classical complexity, parameterised complexity and approximability}, volume = 280, year = 2020 }
• 
  Bossek, Jakob; Casel, Katrin; Kerschke, Pascal; Neumann, FrankThe Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics. Genetic and Evolutionary Computation Conference (GECCO) 2020: 1286-1294
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Several important optimization problems in the area of vehicle routing can be seen as a variant of the classical Traveling Salesperson Problem (TSP). In the area of evolutionary computation, the traveling thief problem (TTP) has gained increasing interest over the last 5 years. In this paper, we investigate the effect of weights on such problems, in the sense that the cost of traveling increases with respect to the weights of nodes already visited during a tour. This provides abstractions of important TSP variants such as the Traveling Thief Problem and time dependent TSP variants, and allows to study precisely the increase in difficulty caused by weight dependence. We provide a 3.59-approximation for this weight dependent version of TSP with metric distances and bounded positive weights. Furthermore, we conduct experimental investigations for simple randomized local search with classical mutation operators and two variants of the state-of-the-art evolutionary algorithm EAX adapted to the weighted TSP. Our results show the impact of the node weights on the position of the nodes in the resulting tour.
  @inproceedings{jakob2020weight, abstract = {Several important optimization problems in the area of vehicle routing can be seen as a variant of the classical Traveling Salesperson Problem (TSP). In the area of evolutionary computation, the traveling thief problem (TTP) has gained increasing interest over the last 5 years. In this paper, we investigate the effect of weights on such problems, in the sense that the cost of traveling increases with respect to the weights of nodes already visited during a tour. This provides abstractions of important TSP variants such as the Traveling Thief Problem and time dependent TSP variants, and allows to study precisely the increase in difficulty caused by weight dependence. We provide a 3.59-approximation for this weight dependent version of TSP with metric distances and bounded positive weights. Furthermore, we conduct experimental investigations for simple randomized local search with classical mutation operators and two variants of the state-of-the-art evolutionary algorithm EAX adapted to the weighted TSP. Our results show the impact of the node weights on the position of the nodes in the resulting tour.}, author = {Bossek, Jakob and Casel, Katrin and Kerschke, Pascal and Neumann, Frank}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {sys:relevantfor:ae katrincasel pascalkerschke gecco jakobbossek frankneumann year2020}, pages = {1286-1294}, publisher = {ACM}, title = {The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics}, year = 2020 }

2019 [ nach oben ]

• 
  Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jerome; Sikora, FlorianExtension of vertex cover and independent set in some classes of graphs and generalizations. International Conference on Algorithms and Complexity (CIAC) 2019: 124-136
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We study extension variants of the classical problems Vertex Cover and Independent Set. Given a graph \(G = (V, E)\) and a vertex set \(U \subseteq V\), it is asked if there exists a minimal vertex cover (resp. maximal independent set) \(S\) with \(U \subseteq S\) (resp. \(U \supseteq S\)). Possibly contradicting intuition, these problems tend to be NP-complete, even in graph classes where the classical problem can be solved efficiently. Yet, we exhibit some graph classes where the extension variant remains polynomial-time solvable. We also study the parameterized complexity of theses problems, with parameter \(|U|\), as well as the optimality of simple exact algorithms under ETH. All these complexity considerations are also carried out in very restricted scenarios, be it degree or topological restrictions (bipartite, planar or chordal graphs). This also motivates presenting some explicit branching algorithms for degree-bounded instances. We further discuss the price of extension, measuring the distance of \(U\) to the closest set that can be extended, which results in natural optimization problems related to extension problems for which we discuss polynomial-time approximability.
  @inproceedings{casel2019extensionCIAC, abstract = {We study extension variants of the classical problems Vertex Cover and Independent Set. Given a graph \(G = (V, E)\) and a vertex set \(U \subseteq V\), it is asked if there exists a minimal vertex cover (resp. maximal independent set) \(S\) with \(U \subseteq S\) (resp. \(U \supseteq S\)). Possibly contradicting intuition, these problems tend to be NP-complete, even in graph classes where the classical problem can be solved efficiently. Yet, we exhibit some graph classes where the extension variant remains polynomial-time solvable. We also study the parameterized complexity of theses problems, with parameter \(|U|\), as well as the optimality of simple exact algorithms under ETH. All these complexity considerations are also carried out in very restricted scenarios, be it degree or topological restrictions (bipartite, planar or chordal graphs). This also motivates presenting some explicit branching algorithms for degree-bounded instances. We further discuss the price of extension, measuring the distance of \(U\) to the closest set that can be extended, which results in natural optimization problems related to extension problems for which we discuss polynomial-time approximability.}, author = {Casel, Katrin and Fernau, Henning and Khosravian Ghadikolaei, Mehdi and Monnot, Jerome and Sikora, Florian}, booktitle = {International Conference on Algorithms and Complexity (CIAC)}, keywords = {katrincasel year2019 ciac}, pages = {124-136}, title = {Extension of vertex cover and independent set in some classes of graphs and generalizations}, year = 2019 }
• 
  Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jerome; Sikora, FlorianExtension of some edge graph problems: standard and parameterized complexity. Fundamentals of Computation Theory (FCT) 2019: 185-200
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We consider extension variants of some edge optimization problems in graphs containing the classical Edge Cover, Matching, and Edge Dominating Set problems. Given a graph \(G=(V,E)\) and an edge set \(U \subseteq E\), it is asked whether there exists an inclusion-wise minimal (resp., maximal) feasible solution \(E'\) which satisfies a given property, for instance, being an edge dominating set (resp., a matching) and containing the forced edge set \(U\) (resp., avoiding any edges from the forbidden edge set \(E U\)). We present hardness results for these problems, for restricted instances such as bipartite or planar graphs. We counter-balance these negative results with parameterized complexity results. We also consider the price of extension, a natural optimization problem variant of extension problems, leading to some approximation results.
  @inproceedings{casel2019extensionFCT, abstract = {We consider extension variants of some edge optimization problems in graphs containing the classical Edge Cover, Matching, and Edge Dominating Set problems. Given a graph \(G=(V,E)\) and an edge set \(U \subseteq E\), it is asked whether there exists an inclusion-wise minimal (resp., maximal) feasible solution \(E'\) which satisfies a given property, for instance, being an edge dominating set (resp., a matching) and containing the forced edge set \(U\) (resp., avoiding any edges from the forbidden edge set \(E U\)). We present hardness results for these problems, for restricted instances such as bipartite or planar graphs. We counter-balance these negative results with parameterized complexity results. We also consider the price of extension, a natural optimization problem variant of extension problems, leading to some approximation results.}, author = {Casel, Katrin and Fernau, Henning and Khosravian Ghadikolaei, Mehdi and Monnot, Jerome and Sikora, Florian}, booktitle = {Fundamentals of Computation Theory (FCT)}, keywords = {katrincasel year2019 fct}, pages = {185-200}, title = {Extension of some edge graph problems: standard and parameterized complexity}, year = 2019 }
• 
  Casel, Katrin; Day, Joel D.; Fleischmann, Pamela; Kociumaka, Tomasz; Manea, Florin; Schmid, Markus L.Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number. International Colloquium on Automata, Languages and Programming (ICALP) 2019: 109:1-109:16
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two important graph-parameters, cutwidth and pathwidth. These connections allow us to show that computing the locality number is NP-hard but fixed parameter tractable (when the locality number or the alphabet size is treated as a parameter), and can be approximated with ratio \(O(\sqrt{\log opt \log n)\). As a by-product, we also relate cutwidth via the locality number to pathwidth, which is of independent interest, since it improves the currently best known approximation algorithm for cutwidth. In addition to these main results, we also consider the possibility of greedy-based approximation algorithms for the locality number.
  @inproceedings{casel2019graph, abstract = {We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two important graph-parameters, cutwidth and pathwidth. These connections allow us to show that computing the locality number is NP-hard but fixed parameter tractable (when the locality number or the alphabet size is treated as a parameter), and can be approximated with ratio \(O(\sqrt{\log opt} \log n)\). As a by-product, we also relate cutwidth via the locality number to pathwidth, which is of independent interest, since it improves the currently best known approximation algorithm for cutwidth. In addition to these main results, we also consider the possibility of greedy-based approximation algorithms for the locality number.}, author = {Casel, Katrin and Day, Joel D. and Fleischmann, Pamela and Kociumaka, Tomasz and Manea, Florin and Schmid, Markus L.}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {katrincasel year2019 icalp}, pages = {109:1-109:16}, title = {Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number}, year = 2019 }

2018 [ nach oben ]

• 
  Abu-Khzam, Faisal N.; Bazgan, Cristina; Casel, Katrin; Fernau, HenningClustering with Lower-Bounded Sizes - A General Graph-Theoretic Framework. Algorithmica 2018: 2517-2550
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  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\).
  @article{abukhzam2018clustering, abstract = {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\).}, author = {Abu-Khzam, Faisal N. and Bazgan, Cristina and Casel, Katrin and Fernau, Henning}, journal = {Algorithmica}, keywords = {cristinabazgan algorithmica katrincasel year2018 faisalnabukhzam henningfernau}, number = 9, pages = {2517-2550}, title = {Clustering with Lower-Bounded Sizes - A General Graph-Theoretic Framework}, volume = 80, year = 2018 }
• 
  Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Klein, Kim-Manuel; Lampis, Michael; Liedloff, Mathieu; Monnot, Jérôme; Paschos, Vangelis Th.The many facets of upper domination. Theoretical Computer Science 2018: 2-25
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  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.
  @article{DBLP:journals/tcs/BazganBCFJKLLMP18, abstract = {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.}, author = {Bazgan, Cristina and Brankovic, Ljiljana and Casel, Katrin and Fernau, Henning and Jansen, Klaus and Klein, Kim{-}Manuel and Lampis, Michael and Liedloff, Mathieu and Monnot, J{{é}}r{{ô}}me and Paschos, Vangelis Th.}, journal = {Theoretical Computer Science}, keywords = {klausjansen michaellampis cristinabazgan vangelisthpaschos tcs katrincasel year2018 kimmanuelklein mathieuliedloff jeromemonnot ljiljanabrankovic henningfernau}, pages = {2-25}, title = {The many facets of upper domination}, volume = 717, year = 2018 }
• 
  Casel, KatrinResolving Conflicts for Lower-Bounded Clustering. International Symposium on Parameterized and Exact Computation (IPEC) 2018: 23:1-23:14
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  This paper considers the effect of non-metric distances for lower-bounded 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 lower-bounded clustering with the objective to minimise the maximum radius or diameter of the clusters. For these problems there exists a 2-approximation but only if the pairwise distance on the objects satisfies the triangle inequality, without this property no polynomial-time constant factor approximation is possible. We try to resolve or at least soften this effect of non-metric 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.
  @inproceedings{casel2018resolving, abstract = {This paper considers the effect of non-metric distances for lower-bounded 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 lower-bounded clustering with the objective to minimise the maximum radius or diameter of the clusters. For these problems there exists a 2-approximation but only if the pairwise distance on the objects satisfies the triangle inequality, without this property no polynomial-time constant factor approximation is possible. We try to resolve or at least soften this effect of non-metric 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.}, author = {Casel, Katrin}, booktitle = {International Symposium on Parameterized and Exact Computation (IPEC)}, keywords = {ipec katrincasel year2018}, pages = {23:1-23:14}, title = {Resolving Conflicts for Lower-Bounded Clustering}, year = 2018 }

2017 [ nach oben ]

• 
  Casel, Katrin; Fernau, Henning; Grigoriev, Alexander; Schmid, Markus L.; Whitesides, SueCombinatorial Properties and Recognition of Unit Square Visibility Graphs. International Symposium on Mathematical Foundations of Computer Science (MFCS) 2017: 30:1-30:15
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  Unit square (grid) visibility graphs (USV and USGV, resp.) are described by axis-parallel visibility between unit squares placed (on integer grid coordinates) in the plane. We investigate combinatorial properties of these graph classes and the hardness of variants of the recognition problem, i.e., the problem of representing USGV with fixed visibilities within small area and, for USV, the general recognition problem.
  @inproceedings{DBLP:conf/mfcs/CaselFGSW17, abstract = {Unit square (grid) visibility graphs (USV and USGV, resp.) are described by axis-parallel visibility between unit squares placed (on integer grid coordinates) in the plane. We investigate combinatorial properties of these graph classes and the hardness of variants of the recognition problem, i.e., the problem of representing USGV with fixed visibilities within small area and, for USV, the general recognition problem.}, author = {Casel, Katrin and Fernau, Henning and Grigoriev, Alexander and Schmid, Markus L. and Whitesides, Sue}, booktitle = {International Symposium on Mathematical Foundations of Computer Science (MFCS)}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean{-}Fran{\c{c}}ois}, keywords = {suewhitesides markuslschmid katrincasel alexandergrigoriev year2017 mfcs henningfernau}, pages = {30:1-30:15}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {LIPIcs}, title = {Combinatorial Properties and Recognition of Unit Square Visibility Graphs}, volume = 83, year = 2017 }

2016 [ nach oben ]

• 
  Casel, Katrin; Estrada-Moreno, Alejandro; Fernau, Henning; Rodríguez-Velázquez, Juan AlbertoWeak total resolvability in graphs. Discussiones Mathematicae Graph Theory 2016: 185-210
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  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 subset 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 2-domination. (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.
  @article{DBLP:journals/dmgt/CaselEFR16, abstract = {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 \subset 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 2-domination. (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.}, author = {Casel, Katrin and Estrada{-}Moreno, Alejandro and Fernau, Henning and Rodr{{í}}guez{-}Vel{{á}}zquez, Juan Alberto}, journal = {Discussiones Mathematicae Graph Theory}, keywords = {katrincasel year2016 dmgt alejandroestradamoreno henningfernau juanalbertorodriguezvelazquez}, number = 1, pages = {185-210}, title = {Weak total resolvability in graphs}, volume = 36, year = 2016 }
• 
  Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Klein, Kim-Manuel; 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: 113-124
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  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 Co-Upper 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.
  @inproceedings{DBLP:conf/aaim/BazganBCFJKLLMP16, abstract = {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 Co-Upper 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.}, author = {Bazgan, Cristina and Brankovic, Ljiljana and Casel, Katrin and Fernau, Henning and Jansen, Klaus and Klein, Kim{-}Manuel and Lampis, Michael and Liedloff, Mathieu and Monnot, J{{é}}r{{ô}}me and Paschos, Vangelis Th.}, booktitle = {Algorithmic Aspects in Information and Management (AAIM)}, editor = {Dondi, Riccardo and Fertin, Guillaume and Mauri, Giancarlo}, keywords = {klausjansen michaellampis cristinabazgan vangelisthpaschos katrincasel kimmanuelklein mathieuliedloff year2016 jeromemonnot ljiljanabrankovic aaim henningfernau}, pages = {113-124}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Algorithmic Aspects of Upper Domination: A Parameterised Perspective}, volume = 9778, year = 2016 }
• 
  Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, HenningOn the Complexity Landscape of the Domination Chain. Algorithms and Discrete Applied Mathematics (CALDAM) 2016: 61-72
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  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 NP-hard 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 constant-factor approximable in polynomial time. All these four versions are APX-hard even on cubic graphs.
  @inproceedings{DBLP:conf/caldam/BazganBCF16, abstract = {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 NP-hard 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 constant-factor approximable in polynomial time. All these four versions are APX-hard even on cubic graphs.}, author = {Bazgan, Cristina and Brankovic, Ljiljana and Casel, Katrin and Fernau, Henning}, booktitle = {Algorithms and Discrete Applied Mathematics (CALDAM)}, editor = {Govindarajan, Sathish and Maheshwari, Anil}, keywords = {cristinabazgan katrincasel year2016 caldam ljiljanabrankovic henningfernau}, pages = {61-72}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {On the Complexity Landscape of the Domination Chain}, volume = 9602, year = 2016 }
• 
  Casel, Katrin; Fernau, Henning; Gaspers, Serge; Gras, Benjamin; Schmid, Markus L.On the Complexity of Grammar-Based Compression over Fixed Alphabets. International Colloquium on Automata, Languages, and Programming (ICALP) 2016: 122:1-122:14
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  It is shown that the shortest-grammar problem remains NP-complete 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 polynomial-time, 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(3^n)\) exact exponential-time algorithm, based on dynamic programming. Similar results are also given for 1-level 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 shortest-grammar problem).
  @inproceedings{DBLP:conf/icalp/CaselFGGS16, abstract = {It is shown that the shortest-grammar problem remains NP-complete 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 polynomial-time, 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(3^n)\) exact exponential-time algorithm, based on dynamic programming. Similar results are also given for 1-level 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 shortest-grammar problem).}, author = {Casel, Katrin and Fernau, Henning and Gaspers, Serge and Gras, Benjamin and Schmid, Markus L.}, booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, keywords = {markuslschmid katrincasel year2016 benjamingras icalp sergegaspers henningfernau}, pages = {122:1-122:14}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {LIPIcs}, title = {On the Complexity of Grammar-Based Compression over Fixed Alphabets}, volume = 55, year = 2016 }
• 
  Abu-Khzam, Faisal N.; Bazgan, Cristina; Casel, Katrin; Fernau, HenningBuilding Clusters with Lower-Bounded Sizes. International Symposium on Algorithms and Computation (ISAAC) 2016: 4:1-4:13
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  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\).
  @inproceedings{DBLP:conf/isaac/Abu-KhzamBCF16, abstract = {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\).}, author = {Abu{-}Khzam, Faisal N. and Bazgan, Cristina and Casel, Katrin and Fernau, Henning}, booktitle = {International Symposium on Algorithms and Computation (ISAAC)}, editor = {Hong, Seok{-}Hee}, keywords = {hen cristinabazgan isaac katrincasel year2016 faisalnabukhzam}, pages = {4:1-4:13}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {LIPIcs}, title = {Building Clusters with Lower-Bounded Sizes}, volume = 64, year = 2016 }
• 
  Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Klein, Kim-Manuel; Lampis, Michael; Liedloff, Mathieu; Monnot, Jérôme; Paschos, Vangelis Th.Upper Domination: Complexity and Approximation. International Workshop on Combinatorial Algorithms (IWOCA) 2016: 241-252
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  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 (APX-hard), and planar subcubic graphs (NP-hard). We complement our negative results by showing that the problem admits an \(O(\Delta )\) approximation on graphs of maximum degree \(\Delta\) , 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 d-uniform hypergraphs, generalising known results for Maximum Minimal Vertex Cover.
  @inproceedings{DBLP:conf/iwoca/BazganBCFJKLLMP16, abstract = {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 (APX-hard), and planar subcubic graphs (NP-hard). We complement our negative results by showing that the problem admits an \(O(\Delta )\) approximation on graphs of maximum degree \(\Delta\) , 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 d-uniform hypergraphs, generalising known results for Maximum Minimal Vertex Cover.}, author = {Bazgan, Cristina and Brankovic, Ljiljana and Casel, Katrin and Fernau, Henning and Jansen, Klaus and Klein, Kim{-}Manuel and Lampis, Michael and Liedloff, Mathieu and Monnot, J{{é}}r{{ô}}me and Paschos, Vangelis Th.}, booktitle = {International Workshop on Combinatorial Algorithms (IWOCA)}, editor = {M{{ä}}kinen, Veli and Puglisi, Simon J. and Salmela, Leena}, keywords = {klausjansen michaellampis iwoca cristinabazgan vangelisthpaschos katrincasel kimmanuelklein mathieuliedloff year2016 jeromemonnot ljiljanabrankovic henningfernau}, pages = {241-252}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Upper Domination: Complexity and Approximation}, volume = 9843, year = 2016 }

2014 [ nach oben ]

• 
  Casel, KatrinA Fixed-Parameter Approach for Privacy-Protection with Global Recoding. Frontiers in Algorithmics (FAW) 2014: 25-35
  [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
   
  This paper discusses a problem arising in the field of privacy-protection in statistical databases: Given a \(n \times m\) \(\{0,1\}\)-matrix \(M\), is there a set of mergings which transforms \(M\) into a zero matrix and only affects a bounded number of rows/columns. “Merging” here refers to combining adjacent lines with a component-wise logical AND. This kind transformation models a generalization on OLAP-cubes also called global recoding. Counting the number of affected lines presents a new measure of information-loss for this method. Parameterized by the number of affected lines \(k\) we introduce reduction rules and an \(O^*(2.618^k)\)-algorithm for the new abstract combinatorial problem LMAL.
  @inproceedings{DBLP:conf/faw/Casel14, abstract = {This paper discusses a problem arising in the field of privacy-protection in statistical databases: Given a \(n \times m\) \(\{0,1\}\)-matrix \(M\), is there a set of mergings which transforms \(M\) into a zero matrix and only affects a bounded number of rows/columns. “Merging” here refers to combining adjacent lines with a component-wise logical AND. This kind transformation models a generalization on OLAP-cubes also called global recoding. Counting the number of affected lines presents a new measure of information-loss for this method. Parameterized by the number of affected lines \(k\) we introduce reduction rules and an \(O^*(2.618^k)\)-algorithm for the new abstract combinatorial problem LMAL.}, author = {Casel, Katrin}, booktitle = {Frontiers in Algorithmics (FAW)}, editor = {Chen, Jianer and Hopcroft, John E. and Wang, Jianxin}, keywords = {katrincasel year2014 faw}, pages = {25-35}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {A Fixed-Parameter Approach for Privacy-Protection with Global Recoding}, volume = 8497, year = 2014 }