2019 [ to top ]

• 
  Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jerome; Sikora, Florian Extension 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 = {ciac katrincasel year2019}, 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, Florian Extension 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 = {fct katrincasel year2019}, 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 = {icalp katrincasel year2019}, pages = {109:1-109:16}, title = {Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number}, year = 2019 }

2018 [ to top ]

• 
  Abu-Khzam, Faisal N.; Bazgan, Cristina; Casel, Katrin; Fernau, Henning Clustering 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 = {algorithmica cristinabazgan faisalnabukhzam henningfernau katrincasel year2018}, 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 = {cristinabazgan henningfernau jeromemonnot katrincasel kimmanuelklein klausjansen ljiljanabrankovic mathieuliedloff michaellampis tcs vangelisthpaschos year2018}, pages = {2-25}, title = {The many facets of upper domination}, volume = 717, year = 2018 }
• 
  Casel, Katrin Resolving 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 [ to top ]

• 
  Casel, Katrin; Fernau, Henning; Grigoriev, Alexander; Schmid, Markus L.; Whitesides, Sue Combinatorial 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 = {alexandergrigoriev henningfernau katrincasel markuslschmid mfcs suewhitesides year2017}, 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 [ to top ]

• 
  Casel, Katrin; Estrada-Moreno, Alejandro; Fernau, Henning; Rodríguez-Velázquez, Juan Alberto Weak 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 = {alejandroestradamoreno dmgt henningfernau juanalbertorodriguezvelazquez katrincasel year2016}, 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 = {aaim cristinabazgan henningfernau jeromemonnot katrincasel kimmanuelklein klausjansen ljiljanabrankovic mathieuliedloff michaellampis vangelisthpaschos year2016}, 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, Henning On 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 = {caldam cristinabazgan henningfernau katrincasel ljiljanabrankovic year2016}, 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 = {benjamingras henningfernau icalp katrincasel markuslschmid sergegaspers year2016}, 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, Henning Building 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 = {cristinabazgan faisalnabukhzam hen isaac katrincasel year2016}, 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 = {cristinabazgan henningfernau iwoca jeromemonnot katrincasel kimmanuelklein klausjansen ljiljanabrankovic mathieuliedloff michaellampis vangelisthpaschos year2016}, pages = {241-252}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Upper Domination: Complexity and Approximation}, volume = 9843, year = 2016 }

2014 [ to top ]

• 
  Casel, Katrin A 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 = {faw katrincasel year2014}, 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 }