2024 [ nach oben ]

Casel, Katrin; Friedrich, Tobias; Neubert, Stefan; Schmid, Markus L. Shortest distances as enumeration problemDiscrete Applied Mathematics 2024: 89–103
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We investigate the single source shortest distance (SSSD) and all pairs shortest distance (APSD) problems as enumeration problems (on unweighted and integer weighted graphs), meaning that the elements (u,v,d(u,v)) – where u and v are vertices with shortest distance d(u,v) – are produced and listed one by one without repetition. The performance is measured in the RAM model of computation with respect to preprocessing time and delay, i.e., the maximum time that elapses between two consecutive outputs. This point of view reveals that specific types of output (e.g., excluding the non-reachable pairs (u,v,∞), or excluding the self-distances (u,u,0)) and the order of enumeration (e.g., sorted by distance, sorted row-wise with respect to the distance matrix) have a huge impact on the complexity of APSD while they appear to have no effect on SSSD. In particular, we show for APSD that enumeration without output restrictions is possible with delay in the order of the average degree. Excluding non-reachable pairs, or requesting the output to be sorted by distance, increases this delay to the order of the maximum degree. Further, for weighted graphs, a delay in the order of the average degree is also not possible without preprocessing or considering self-distances as output. In contrast, for SSSD we find that a delay in the order of the maximum degree without preprocessing is attainable and unavoidable for any of these requirements.
@article{casel2024shortest, abstract = {We investigate the single source shortest distance (SSSD) and all pairs shortest distance (APSD) problems as enumeration problems (on unweighted and integer weighted graphs), meaning that the elements (u,v,d(u,v)) – where u and v are vertices with shortest distance d(u,v) – are produced and listed one by one without repetition. The performance is measured in the RAM model of computation with respect to preprocessing time and delay, i.e., the maximum time that elapses between two consecutive outputs. This point of view reveals that specific types of output (e.g., excluding the non-reachable pairs (u,v,∞), or excluding the self-distances (u,u,0)) and the order of enumeration (e.g., sorted by distance, sorted row-wise with respect to the distance matrix) have a huge impact on the complexity of APSD while they appear to have no effect on SSSD. In particular, we show for APSD that enumeration without output restrictions is possible with delay in the order of the average degree. Excluding non-reachable pairs, or requesting the output to be sorted by distance, increases this delay to the order of the maximum degree. Further, for weighted graphs, a delay in the order of the average degree is also not possible without preprocessing or considering self-distances as output. In contrast, for SSSD we find that a delay in the order of the maximum degree without preprocessing is attainable and unavoidable for any of these requirements.}, author = {Casel, Katrin and Friedrich, Tobias and Neubert, Stefan and Schmid, Markus L.}, journal = {Discrete Applied Mathematics}, keywords = {sys:relevantfor:ae katrincasel tobiasfriedrich year2024 dam stefanneubert}, month = 1, pages = {89-103}, title = {Shortest distances as enumeration problem}, volume = 342, year = 2024 }

2023 [ nach oben ]

Behrendt, Lukas; Casel, Katrin; Friedrich, Tobias; Lagodzinski, J. A. Gregor; Löser, Alexander; Wilhelm, Marcus From symmetry to asymmetry: Generalizing TSP approximations by parametrizationJournal of Computer and System Sciences 2023: 157–170
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We generalize the tree doubling and Christofides algorithm to parameterized approximations for ATSP (constant factor approximations that invest more runtime with respect to a chosen parameter). The parameters we consider are upper bounded by the number of asymmetric distances, which yields algorithms to efficiently compute good approximations for moderately asymmetric TSP instances. As generalization of the Christofides algorithm, we derive a parameterized 2.5-approximation, with the size of a vertex cover for the subgraph induced by the edges with asymmetric distances as parameter. Our generalization of tree doubling gives a parameterized 3-approximation, where the parameter is the minimum number of asymmetric distances in a minimum spanning arborescence. Further, we combine these with a notion of symmetry relaxation which allows to trade approximation guarantee for runtime. Since the parameters we consider are theoretically incomparable, we present experimental results showing that generalized tree doubling frequently outperforms generalized Christofides with respect to parameter size.
@article{behrendt2023symmetry, abstract = {We generalize the tree doubling and Christofides algorithm to parameterized approximations for ATSP (constant factor approximations that invest more runtime with respect to a chosen parameter). The parameters we consider are upper bounded by the number of asymmetric distances, which yields algorithms to efficiently compute good approximations for moderately asymmetric TSP instances. As generalization of the Christofides algorithm, we derive a parameterized 2.5-approximation, with the size of a vertex cover for the subgraph induced by the edges with asymmetric distances as parameter. Our generalization of tree doubling gives a parameterized 3-approximation, where the parameter is the minimum number of asymmetric distances in a minimum spanning arborescence. Further, we combine these with a notion of symmetry relaxation which allows to trade approximation guarantee for runtime. Since the parameters we consider are theoretically incomparable, we present experimental results showing that generalized tree doubling frequently outperforms generalized Christofides with respect to parameter size.}, author = {Behrendt, Lukas and Casel, Katrin and Friedrich, Tobias and Lagodzinski, J. A. Gregor and Löser, Alexander and Wilhelm, Marcus}, journal = {Journal of Computer and System Sciences}, keywords = {gregorlagodzinski alexanderloeser lukasbehrend katrincasel jcss tobiasfriedrich year2023 marcuswilhelm}, pages = {157-170}, title = {From symmetry to asymmetry: Generalizing TSP approximations by parametrization}, volume = 136, year = 2023 }

Khomutovskiy, Ivan; Dunker, Rebekka; Dierking, Jessica; Egbert, Julian; Helms, Christian; Schöllkopf, Finn; Casel, Katrin; Fischbeck, Philipp; Friedrich, Tobias; Isaac, Davis; Krogmann, Simon; Lenzner, Pascal Applying Skeletons to Speed Up the Arc-Flags Routing AlgorithmSIAM Symposium on Algorithm Engineering and Experiments (ALENEX) 2023: 110–122
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The Single-Source Shortest Path problem is classically solved by applying Dijkstra's algorithm. However, the plain version of this algorithm is far too slow for real-world applications such as routing in large road networks. To amend this, many speed-up techniques have been developed that build on the idea of computing auxiliary data in a preprocessing phase, that is used to speed up the queries. One well-known example is the Arc-Flags algorithm that is based on the idea of precomputing edge flags to make the search more goal-directed. To explain the strong practical performance of such speed-up techniques, several graph parameters have been introduced. The skeleton dimension is one such parameter that has already been used to derive runtime bounds for some speed-up techniques. Moreover, it was experimentally shown to be low in real-world road networks. We introduce a method to incorporate skeletons, the underlying structure behind the skeleton dimension, to improve routing speed-up techniques even further. As a proof of concept, we develop new algorithms called SKARF and SKARF+ that combine skeletons with Arc-Flags, and demonstrate via extensive experiments on large real-world road networks that SKARF+ yields a significant reduction of the search space and the query time of about 30% to 40% over Arc-Flags. We also prove theoretical bounds on the query time of SKARF, which is the first time an Arc-Flags variant has been analyzed in terms of skeleton dimension.
@inproceedings{casel2023applying, abstract = {The Single-Source Shortest Path problem is classically solved by applying Dijkstra's algorithm. However, the plain version of this algorithm is far too slow for real-world applications such as routing in large road networks. To amend this, many speed-up techniques have been developed that build on the idea of computing auxiliary data in a preprocessing phase, that is used to speed up the queries. One well-known example is the Arc-Flags algorithm that is based on the idea of precomputing edge flags to make the search more goal-directed. To explain the strong practical performance of such speed-up techniques, several graph parameters have been introduced. The skeleton dimension is one such parameter that has already been used to derive runtime bounds for some speed-up techniques. Moreover, it was experimentally shown to be low in real-world road networks. We introduce a method to incorporate skeletons, the underlying structure behind the skeleton dimension, to improve routing speed-up techniques even further. As a proof of concept, we develop new algorithms called SKARF and SKARF+ that combine skeletons with Arc-Flags, and demonstrate via extensive experiments on large real-world road networks that SKARF+ yields a significant reduction of the search space and the query time of about 30\% to 40\% over Arc-Flags. We also prove theoretical bounds on the query time of SKARF, which is the first time an Arc-Flags variant has been analyzed in terms of skeleton dimension.}, author = {Khomutovskiy, Ivan and Dunker, Rebekka and Dierking, Jessica and Egbert, Julian and Helms, Christian and Schöllkopf, Finn and Casel, Katrin and Fischbeck, Philipp and Friedrich, Tobias and Isaac, Davis and Krogmann, Simon and Lenzner, Pascal}, booktitle = {SIAM Symposium on Algorithm Engineering and Experiments (ALENEX)}, keywords = {alenex philippfischbeck katrincasel davisissac tobiasfriedrich year2023 simonkrogmann pascallenzner}, pages = {110-122}, title = {Applying Skeletons to Speed Up the Arc-Flags Routing Algorithm}, year = 2023 }

Casel, Katrin; Friedrich, Tobias; Schirneck, Martin; Wietheger, Simon Fair Correlation Clustering in ForestsFoundations of Responsible Computing (FORC) 2023: 9:1–9:12
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The study of algorithmic fairness received growing attention recently. This stems from the awareness that bias in the input data for machine learning systems may result in discriminatory outputs. For clustering tasks, one of the most central notions of fairness is the formalization by Chierichetti, Kumar, Lattanzi, and Vassilvitskii [NeurIPS 2017]. A clustering is said to be fair, if each cluster has the same distribution of manifestations of a sensitive attribute as the whole input set. This is motivated by various applications where the objects to be clustered have sensitive attributes that should not be over- or underrepresented. Most research on this version of fair clustering has focused on centriod-based objectives. In contrast, we discuss the applicability of this fairness notion to Correlation Clustering. The existing literature on the resulting Fair Correlation Clustering problem either presents approximation algorithms with poor approximation guarantees or severely limits the possible distributions of the sensitive attribute (often only two manifestations with a 1:1 ratio are considered). Our goal is to understand if there is hope for better results in between these two extremes. To this end, we consider restricted graph classes which allow us to characterize the distributions of sensitive attributes for which this form of fairness is tractable from a complexity point of view. While existing work on Fair Correlation Clustering gives approximation algorithms, we focus on exact solutions and investigate whether there are efficiently solvable instances. The unfair version of Correlation Clustering is trivial on forests, but adding fairness creates a surprisingly rich picture of complexities. We give an overview of the distributions and types of forests where Fair Correlation Clustering turns from tractable to intractable. As the most surprising insight, we consider the fact that the cause of the hardness of Fair Correlation Clustering is not the strictness of the fairness condition. We lift most of our results to also hold for the relaxed version of the fairness condition. Instead, the source of hardness seems to be the distribution of the sensitive attribute. On the positive side, we identify some reasonable distributions that are indeed tractable. While this tractability is only shown for forests, it may open an avenue to design reasonable approximations for larger graph classes.
@inproceedings{case2023correlation, abstract = {The study of algorithmic fairness received growing attention recently. This stems from the awareness that bias in the input data for machine learning systems may result in discriminatory outputs. For clustering tasks, one of the most central notions of fairness is the formalization by Chierichetti, Kumar, Lattanzi, and Vassilvitskii [NeurIPS 2017]. A clustering is said to be fair, if each cluster has the same distribution of manifestations of a sensitive attribute as the whole input set. This is motivated by various applications where the objects to be clustered have sensitive attributes that should not be over- or underrepresented. Most research on this version of fair clustering has focused on centriod-based objectives. In contrast, we discuss the applicability of this fairness notion to Correlation Clustering. The existing literature on the resulting Fair Correlation Clustering problem either presents approximation algorithms with poor approximation guarantees or severely limits the possible distributions of the sensitive attribute (often only two manifestations with a 1:1 ratio are considered). Our goal is to understand if there is hope for better results in between these two extremes. To this end, we consider restricted graph classes which allow us to characterize the distributions of sensitive attributes for which this form of fairness is tractable from a complexity point of view. While existing work on Fair Correlation Clustering gives approximation algorithms, we focus on exact solutions and investigate whether there are efficiently solvable instances. The unfair version of Correlation Clustering is trivial on forests, but adding fairness creates a surprisingly rich picture of complexities. We give an overview of the distributions and types of forests where Fair Correlation Clustering turns from tractable to intractable. As the most surprising insight, we consider the fact that the cause of the hardness of Fair Correlation Clustering is not the strictness of the fairness condition. We lift most of our results to also hold for the relaxed version of the fairness condition. Instead, the source of hardness seems to be the distribution of the sensitive attribute. On the positive side, we identify some reasonable distributions that are indeed tractable. While this tractability is only shown for forests, it may open an avenue to design reasonable approximations for larger graph classes.}, author = {Casel, Katrin and Friedrich, Tobias and Schirneck, Martin and Wietheger, Simon}, booktitle = {Foundations of Responsible Computing (FORC)}, keywords = {katrincasel simonwietheger forc tobiasfriedrich year2023 martinschirneck}, pages = {9:1-9:12}, title = {Fair Correlation Clustering in Forests}, year = 2023 }

Casel, Katrin; Friedrich, Tobias; Issac, Davis; Niklanovits, Aikaterini; Zeif, Ziena Efficient Constructions for the Gyori-Lovasz Theorem on Almost Chordal GraphsWorkshop Graph-Theoretic Concepts in Computer Science (WG) 2023: 143–156
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In the 1970s, GyHo}ri and Lovász showed that for a \(k\)-connected \(n\)-vertex graph, a given set of terminal vertices \(t_1, \dots, t_k\) and natural numbers \(n_1, \dots, n_k\) satisfying \(\sum_{i=1^k n_i = n\), a connected vertex partition \(S_1, \dots, S_k\) satisfying \(t_i \in S_i\) and \(|S_i| = n_i\) exists. However, polynomial algorithms to actually compute such partitions are known so far only for \(k \leq 4\). This motivates us to take a new approach and constrain this problem to particular graph classes instead of restricting the values of \(k\). More precisely, we consider \(k\)-connected chordal graphs and a broader class of graphs related to them. For the first class, we give an algorithm with \(\mathcal{O(n^2)\) running time that solves the problem exactly, and for the second, an algorithm with \(\mathcal{O(n^4)\) running time that deviates on at most one vertex from the required vertex partition sizes.
@inproceedings{casel2023efficient, abstract = {In the 1970s, Gy\H{o}ri and Lov{á}sz showed that for a \(k\)-connected \(n\)-vertex graph, a given set of terminal vertices \(t_1, \dots, t_k\) and natural numbers \(n_1, \dots, n_k\) satisfying \(\sum_{i=1}^{k} n_i = n\), a connected vertex partition \(S_1, \dots, S_k\) satisfying \(t_i \in S_i\) and \(|S_i| = n_i\) exists. However, polynomial algorithms to actually compute such partitions are known so far only for \(k \leq 4\). This motivates us to take a new approach and constrain this problem to particular graph classes instead of restricting the values of \(k\). More precisely, we consider \(k\)-connected chordal graphs and a broader class of graphs related to them. For the first class, we give an algorithm with \(\mathcal{O}(n^2)\) running time that solves the problem exactly, and for the second, an algorithm with \(\mathcal{O}(n^4)\) running time that deviates on at most one vertex from the required vertex partition sizes.}, author = {Casel, Katrin and Friedrich, Tobias and Issac, Davis and Niklanovits, Aikaterini and Zeif, Ziena}, booktitle = {Workshop Graph-Theoretic Concepts in Computer Science (WG)}, keywords = {sys:relevantfor:ae zienazeif katrincasel davisissac aikaterininiklanovits tobiasfriedrich year2023 wg}, pages = {143–156}, title = {Efficient Constructions for the Gyori-Lovasz Theorem on Almost Chordal Graphs}, year = 2023 }

2022 [ nach oben ]

Casel, Katrin; Fischbeck, Philipp; Friedrich, Tobias; Göbel, Andreas; Lagodzinski, J. A. Gregor Zeros and approximations of Holant polynomials on the complex planeComputational Complexity 2022: 11
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We present fully polynomial time approximation schemesfor a broad class of Holant problems with complex edge weights, which we call Holant polynomials. We transform these problems into partition functions of abstract combinatorial structures known as polymers in statistical physics. Our method involves establishing zero-free regions for the partition functions of polymer models and using the mostsignificant terms of the cluster expansion to approximate them. Results of our technique include new approximation and sampling algorithms for a diverse class of Holant polynomials in the low-temperature regime (i.e. small external field) and approximation algorithms for general Holant problems with small signature weights. Additionally, we give randomised approximation and sampling algorithms with faster running times for more restrictive classes. Finally, we improve the known zero-free regions for a perfect matching polynomial.
@article{casel2022zeros, abstract = {We present fully polynomial time approximation schemesfor a broad class of Holant problems with complex edge weights, which we call Holant polynomials. We transform these problems into partition functions of abstract combinatorial structures known as polymers in statistical physics. Our method involves establishing zero-free regions for the partition functions of polymer models and using the mostsignificant terms of the cluster expansion to approximate them. Results of our technique include new approximation and sampling algorithms for a diverse class of Holant polynomials in the low-temperature regime (i.e. small external field) and approximation algorithms for general Holant problems with small signature weights. Additionally, we give randomised approximation and sampling algorithms with faster running times for more restrictive classes. Finally, we improve the known zero-free regions for a perfect matching polynomial.}, author = {Casel, Katrin and Fischbeck, Philipp and Friedrich, Tobias and Göbel, Andreas and Lagodzinski, J. A. Gregor}, journal = {Computational Complexity}, keywords = {gregorlagodzinski philippfischbeck katrincasel andreasgoebel tobiasfriedrich year2022 cc}, number = 2, pages = 11, title = {Zeros and approximations of Holant polynomials on the complex plane}, volume = 31, year = 2022 }

Casel, Katrin; Fernau, Henning; Grigoriev, Alexander; Schmid, Markus L.; Whitesides, Sue Combinatorial Properties and Recognition of Unit Square Visibility GraphsDiscrete & Computational Geometry 2022
[ Abstract ] [ BibTeX ] [ Download ]
 
Unit square visibility graphs (USV) are described by axis-parallel visibility between unit squares placed in the plane. If the squares are required to be placed on integer grid coordinates, then USV become unit square grid visibility graphs (USGV), an alternative characterisation of the well-known rectilinear graphs. We extend known combinatorial results for USGV and we show that, in the weak case (i.e., visibilities do not necessarily translate into edges of the represented combinatorial graph), the area minimisation variant of their recognition problem is NP-hard. We also provide combinatorial insights with respect to USV, and as our main result, we prove their recognition problem to be \($\mathcal{NP}$\)-hard, which settles an open question.
@article{casel2022combinatorial, abstract = {Unit square visibility graphs (USV) are described by axis-parallel visibility between unit squares placed in the plane. If the squares are required to be placed on integer grid coordinates, then USV become unit square grid visibility graphs (USGV), an alternative characterisation of the well-known rectilinear graphs. We extend known combinatorial results for USGV and we show that, in the weak case (i.e., visibilities do not necessarily translate into edges of the represented combinatorial graph), the area minimisation variant of their recognition problem is NP-hard. We also provide combinatorial insights with respect to USV, and as our main result, we prove their recognition problem to be $\mathcal{NP}$-hard, which settles an open question.}, author = {Casel, Katrin and Fernau, Henning and Grigoriev, Alexander and Schmid, Markus L. and Whitesides, Sue}, journal = {Discrete \& Computational Geometry}, keywords = {katrincasel dcg year2022}, title = {Combinatorial Properties and Recognition of Unit Square Visibility Graphs}, year = 2022 }

Bilò, Davide; Casel, Katrin; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Lagodzinski, J.A. Gregor; Schirneck, Martin; Wietheger, Simon Fixed-Parameter Sensitivity OraclesInnovations in Theoretical Computer Science (ITCS) 2022: 23:1–23:18
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We combine ideas from distance sensitivity oracles (DSOs) and fixed-parameter tractability (FPT) to design sensitivity oracles for FPT graph problems. An oracle with sensitivity \(f\) for an FPT problem \(\Pi\) on a graph \(G\) with parameter \(k\) preprocesses \(G\) in time \(O(g(f,k) poly(n))\). When queried with a set \(F\) of at most \(f\) edges of \(G\), the oracle reports the answer to the \(\Pi\)-with the same parameter \(k\)-on the graph \(G-F\), i.e., \(G\) deprived of \(F\). The oracle should answer queries in a time that is significantly faster than merely running the best-known FPT algorithm on \(G-F\) from scratch. We design sensitivity oracles for the \(k\)-Path and the \(k\)-Vertex Cover problem. Our first oracle for \(k\)-Path has size \(O(k^{f+1})\) size and query time \(O(f \min\{f, log (f) + k\})\). We use a technique inspired by the work of Weimann and Yuster [FOCS 2010, TALG 2013] on distance sensitivity problems to reduce the space to \(O\big(\big(\frac{f+k}{f}\big)^f \big(\frac{f+k}{k}\big)^k fk \cdot \log n\big)\) at the expense of increasing the query time to \(O\big(\big(\frac{f+k}{f}\big)^f \big(\frac{f+k}{k}\big)^k f \min\{f,k\} \cdot \log n \big)\). Both oracles can be modified to handle vertex-failures, but we need to replace \(k\) with \(2k\) in all the claimed bounds. Regarding \(k\)-Vertex Cover, we design three oracles offering different trade-offs between the size and the query time. The first oracle takes \(O(3^{f+k})\) space and has \(O(2^f)\) query time, the second one has a size of \(O(2^{f+k^2+k})\) and a query time of \(O(f{+}k^2)\); finally, the third one takes \(O(fk+k^2)\) space and can be queried in time \(O(1.2738^k + fk^2)\). All our oracles are computable in time (at most) proportional to their size and the time needed to detect a \(k\)-path or \(k\)-vertex cover, respectively. We also provide an interesting connection between \(k\)-Vertex Cover and the fault-tolerant shortest path problem, by giving a DSO of size \(O(poly(f,k) \cdot n)\) with query time in \(O(poly(f,k))\), where \(k\) is the size of a vertex cover. Following our line of research connecting fault-tolerant FPT and shortest paths problems, we introduce parameterization to the computation of distance preservers. Given a graph with a fixed source \(s\) and parameters \(f\),\(k\), we study the problem of constructing polynomial-sized oracles that reports efficiently, for any target vertex \(v\) and set \(F\) of at most \(f\) edge failures, whether the distance from \(s\) to \(v\) increases at most by an additive term of \(k\) in \(G-F\). The oracle size is \(O(2^k k^2 \cdot n)\), while the time needed to answer a query is \(O(2^k f^\omega k^\omega)\), where \(\omega<2.373\) is the matrix multiplication exponent. The second problem we study is about the construction of bounded-stretch fault-tolerant preservers. We construct a subgraph with \(O(2^{fk+f+k k \cdot n)\) edges that preserves those \(s\)-\(v\)-distances that do not increase by more than \(k\) upon failure of \(F\). This improves significantly over the \( \tilde{O} (f n^{2-\frac{1}{2^f}}) \) bound in the unparameterized case by Bodwin et al. [ICALP 2017].
@inproceedings{bilo2022fixedparameter, abstract = {We combine ideas from distance sensitivity oracles (DSOs) and fixed-parameter tractability (FPT) to design sensitivity oracles for FPT graph problems. An oracle with sensitivity \(f\) for an FPT problem \(\Pi\) on a graph \(G\) with parameter \(k\) preprocesses \(G\) in time \(O(g(f,k) poly(n))\). When queried with a set \(F\) of at most \(f\) edges of \(G\), the oracle reports the answer to the \(\Pi\)-with the same parameter \(k\)-on the graph \(G-F\), i.e., \(G\) deprived of \(F\). The oracle should answer queries in a time that is significantly faster than merely running the best-known FPT algorithm on \(G-F\) from scratch. We design sensitivity oracles for the \(k\)-Path and the \(k\)-Vertex Cover problem. Our first oracle for \(k\)-Path has size \(O(k^{f+1})\) size and query time \(O(f \min\{f, \log (f) + k\})\). We use a technique inspired by the work of Weimann and Yuster [FOCS 2010, TALG 2013] on distance sensitivity problems to reduce the space to \(O\big(\big(\frac{f+k}{f}\big)^f \big(\frac{f+k}{k}\big)^k fk \cdot \log n\big)\) at the expense of increasing the query time to \(O\big(\big(\frac{f+k}{f}\big)^f \big(\frac{f+k}{k}\big)^k f \min\{f,k\} \cdot \log n \big)\). Both oracles can be modified to handle vertex-failures, but we need to replace \(k\) with \(2k\) in all the claimed bounds. Regarding \(k\)-Vertex Cover, we design three oracles offering different trade-offs between the size and the query time. The first oracle takes \(O(3^{f+k})\) space and has \(O(2^f)\) query time, the second one has a size of \(O(2^{f+k^2+k})\) and a query time of \(O(f{+}k^2)\); finally, the third one takes \(O(fk+k^2)\) space and can be queried in time \(O(1.2738^k + fk^2)\). All our oracles are computable in time (at most) proportional to their size and the time needed to detect a \(k\)-path or \(k\)-vertex cover, respectively. We also provide an interesting connection between \(k\)-Vertex Cover and the fault-tolerant shortest path problem, by giving a DSO of size \(O(poly(f,k) \cdot n)\) with query time in \(O(poly(f,k))\), where \(k\) is the size of a vertex cover. Following our line of research connecting fault-tolerant FPT and shortest paths problems, we introduce parameterization to the computation of distance preservers. Given a graph with a fixed source \(s\) and parameters \(f\),\(k\), we study the problem of constructing polynomial-sized oracles that reports efficiently, for any target vertex \(v\) and set \(F\) of at most \(f\) edge failures, whether the distance from \(s\) to \(v\) increases at most by an additive term of \(k\) in \(G-F\). The oracle size is \(O(2^k k^2 \cdot n)\), while the time needed to answer a query is \(O(2^k f^\omega k^\omega)\), where \(\omega<2.373\) is the matrix multiplication exponent. The second problem we study is about the construction of bounded-stretch fault-tolerant preservers. We construct a subgraph with \(O(2^{fk+f+k} k \cdot n)\) edges that preserves those \(s\)-\(v\)-distances that do not increase by more than \(k\) upon failure of \(F\). This improves significantly over the \( \tilde{O} (f n^{2-\frac{1}{2^f}}) \) bound in the unparameterized case by Bodwin et al. [ICALP 2017].}, author = {Bilò, Davide and Casel, Katrin and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Lagodzinski, J.A. Gregor and Schirneck, Martin and Wietheger, Simon}, booktitle = {Innovations in Theoretical Computer Science (ITCS)}, keywords = {sarelcohen gregorlagodzinski davidebilo katrincasel simonwietheger tobiasfriedrich itcs keertichoudhary year2022 martinschirneck}, pages = {23:1-23:18}, title = {Fixed-Parameter Sensitivity Oracles}, year = 2022 }

Bazgan, Cristina; Casel, Katrin; Cazals, Pierre Dense Graph Partitioning on sparse and dense graphs.Scandinavian Workshop Algorithm Theory (SWAT) 2022
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We consider the problem of partitioning a graph into a non-fixed number of non-overlapping subgraphs of maximum density. The density of a partition is the sum of the densities of the subgraphs, where the density of a subgraph is its average degree, that is, the ratio of its number of edges and its number of vertices. This problem, called Dense Graph Partition, is known to be NP-hard on general graphs and polynomial-time solvable on trees, and polynomial-time 2-approximable. In this paper we study the restriction of Dense Graph Partition to particular sparse and dense graph classes. In particular, we prove that it is NP-hard on dense bipartite graphs as well as on cubic graphs. On dense graphs on \(n\) vertices, it is polynomial-time solvable on graphs with minimum degree \(n-3\) and NP-hard on \((n-4)\)-regular graphs. We prove that it is polynomial-time 4/3-approximable on cubic graphs and admits an efficient polynomial-time approximation scheme on graphs of minimum degree \(n-t\) for any constant \(t\geq 4\).
@inproceedings{bazgan2022dense, abstract = {We consider the problem of partitioning a graph into a non-fixed number of non-overlapping subgraphs of maximum density. The density of a partition is the sum of the densities of the subgraphs, where the density of a subgraph is its average degree, that is, the ratio of its number of edges and its number of vertices. This problem, called Dense Graph Partition, is known to be NP-hard on general graphs and polynomial-time solvable on trees, and polynomial-time 2-approximable. In this paper we study the restriction of Dense Graph Partition to particular sparse and dense graph classes. In particular, we prove that it is NP-hard on dense bipartite graphs as well as on cubic graphs. On dense graphs on \(n\) vertices, it is polynomial-time solvable on graphs with minimum degree \(n-3\) and NP-hard on \((n-4)\)-regular graphs. We prove that it is polynomial-time 4/3-approximable on cubic graphs and admits an efficient polynomial-time approximation scheme on graphs of minimum degree \(n-t\) for any constant \(t\geq 4\).}, author = {Bazgan, Cristina and Casel, Katrin and Cazals, Pierre}, booktitle = {Scandinavian Workshop Algorithm Theory (SWAT)}, keywords = {swat katrincasel year2022}, title = {Dense Graph Partitioning on sparse and dense graphs.}, year = 2022 }

2021 [ nach oben ]

Casel, Katrin; Fernau, Henning; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Sikora, Florian On the Complexity of Solution Extension of Optimization ProblemsTheoretical Computer Science 2021
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating minimal vertex covers of a graph G=(V,E), one usually arrives at the problem to decide for a vertex set \(U \subseteq V\) (pre-solution), if there exists a minimal vertex cover S (i.e., a vertex cover \(S \subseteq V\) such that no proper subset of S is a vertex cover) with \(U \subseteq S\) (minimal extension of U). We propose a general, partial-order based formulation of such extension problems which allows to model parameterization and approximation aspects of extension, and also highlights relationships between extension tasks for different specific problems. As examples, we study a number of specific problems which can be expressed and related in this framework. In particular, we discuss extension variants of the problems dominating set and feedback vertex/edge set. All these problems are shown to be NP-complete even when restricted to bipartite graphs of bounded degree, with the exception of our extension version of feedback edge set on undirected graphs which is shown to be solvable in polynomial time. For the extension variants of dominating and feedback vertex set, we also show NP-completeness for the restriction to planar graphs of bounded degree. As non-graph problem, we also study an extension version of the bin packing problem. We further consider the parameterized complexity of all these extension variants, where the parameter is a measure of the pre-solution as defined by our framework.
@article{casel2021complexity, abstract = {The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating minimal vertex covers of a graph G=(V,E), one usually arrives at the problem to decide for a vertex set \(U \subseteq V\) (pre-solution), if there exists a minimal vertex cover S (i.e., a vertex cover \(S \subseteq V\) such that no proper subset of S is a vertex cover) with \(U \subseteq S\) (minimal extension of U). We propose a general, partial-order based formulation of such extension problems which allows to model parameterization and approximation aspects of extension, and also highlights relationships between extension tasks for different specific problems. As examples, we study a number of specific problems which can be expressed and related in this framework. In particular, we discuss extension variants of the problems dominating set and feedback vertex/edge set. All these problems are shown to be NP-complete even when restricted to bipartite graphs of bounded degree, with the exception of our extension version of feedback edge set on undirected graphs which is shown to be solvable in polynomial time. For the extension variants of dominating and feedback vertex set, we also show NP-completeness for the restriction to planar graphs of bounded degree. As non-graph problem, we also study an extension version of the bin packing problem. We further consider the parameterized complexity of all these extension variants, where the parameter is a measure of the pre-solution as defined by our framework.}, author = {Casel, Katrin and Fernau, Henning and Khosravian Ghadikolaei, Mehdi and Monnot, Jérôme and Sikora, Florian}, journal = {Theoretical Computer Science}, keywords = {tcs katrincasel year2021}, title = {On the Complexity of Solution Extension of Optimization Problems}, year = 2021 }

Casel, Katrin; Fernau, Henning; Gaspers, Serge; Gras, Benjamin; Schmid, Markus L. On the Complexity of the Smallest Grammar Problem over Fixed AlphabetsTheory 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 }

Borndörfer, Ralf; Casel, Katrin; Issac, Davis; Niklanovits, Aikaterini; Schwartz, Stephan; Zeif, Ziena Connected k-Partition of k-Connected Graphs and c-Claw-Free GraphsApproximation Algorithms for Combinatorial Optimization Problems (APPROX) 2021: 27:1–27:14
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
A connected partition is a partition of the vertices of a graph into sets that induce connected subgraphs. Such partitions naturally occur in many application areas such as road networks, and image processing. In these settings, it is often desirable to partition into a fixed number of parts of roughly of the same size or weight. The resulting computational problem is called Balanced Connected Partition (BCP). The two classical objectives for BCP are to maximize the weight of the smallest, or minimize the weight of the largest component. We study BCP on \(c\)-claw-free graphs, the class of graphs that do not have \(K_{1,c}\) as an induced subgraph, and present efficient \((c-1)\)-approximation algorithms for both objectives. In particular, for \(3\)-claw-free graphs, also simply known as claw-free graphs, we obtain a \(2\)-approximation. Due to the claw-freeness of line graphs, this also implies a \(2\)-approximation for the edge-partition version of BCP in general graphs. A harder connected partition problem arises from demanding a connected partition into k parts that have (possibly) heterogeneous target weights \(w_1, \dots, w_k\). In the 1970s Győri and Lovász showed that if \(G\) is \(k\)-connected and the target weights sum to the total size of \(G\), such a partition exists. However, to this day no polynomial algorithm to compute such partitions exists for \(k > 4\). Towards finding such a partition \(T_1, \dots, T_k\) in \(k\)-connected graphs for general \(k\), we show how to efficiently compute connected partitions that at least approximately meet the target weights, subject to the mild assumption that each \(w_i\) is greater than the weight of the heaviest vertex. In particular, we give a \(3\)-approximation for both the lower and the upper bounded version i.e. we guarantee that each \(T_i\) has weight at least \(\frac{w_i}{3}\) or that each \(T_i\) has weight most \(3 w_i\), respectively. Also, we present a both-side bounded version that produces a connected partition where each \(T_i\) has size at least \(\frac{w_i}{3}\) and at most \(\max(\{r, 3\}) w_i \), where \(r \geq 1\) is the ratio between the largest and smallest value in \(w_1, \dots, w_k\). In particular for the balanced version, i.e. \(w_1 = w_2 =, \dots , = w k\), this gives a partition with \(\frac{w_i3 leq w(T_i) \leq 3 w_i\).
@inproceedings{borndorfer2021connected, abstract = {A connected partition is a partition of the vertices of a graph into sets that induce connected subgraphs. Such partitions naturally occur in many application areas such as road networks, and image processing. In these settings, it is often desirable to partition into a fixed number of parts of roughly of the same size or weight. The resulting computational problem is called Balanced Connected Partition (BCP). The two classical objectives for BCP are to maximize the weight of the smallest, or minimize the weight of the largest component. We study BCP on \(c\)-claw-free graphs, the class of graphs that do not have \(K_{1,c}\) as an induced subgraph, and present efficient \((c-1)\)-approximation algorithms for both objectives. In particular, for \(3\)-claw-free graphs, also simply known as claw-free graphs, we obtain a \(2\)-approximation. Due to the claw-freeness of line graphs, this also implies a \(2\)-approximation for the edge-partition version of BCP in general graphs. A harder connected partition problem arises from demanding a connected partition into k parts that have (possibly) heterogeneous target weights \(w_1, \dots, w_k\). In the 1970s Győri and Lovász showed that if \(G\) is \(k\)-connected and the target weights sum to the total size of \(G\), such a partition exists. However, to this day no polynomial algorithm to compute such partitions exists for \(k > 4\). Towards finding such a partition \(T_1, \dots, T_k\) in \(k\)-connected graphs for general \(k\), we show how to efficiently compute connected partitions that at least approximately meet the target weights, subject to the mild assumption that each \(w_i\) is greater than the weight of the heaviest vertex. In particular, we give a \(3\)-approximation for both the lower and the upper bounded version i.e. we guarantee that each \(T_i\) has weight at least \(\frac{w_i}{3}\) or that each \(T_i\) has weight most \(3 w_i\), respectively. Also, we present a both-side bounded version that produces a connected partition where each \(T_i\) has size at least \(\frac{w_i}{3}\) and at most \(\max(\{r, 3\}) w_i \), where \(r \geq 1\) is the ratio between the largest and smallest value in \(w_1, \dots, w_k\). In particular for the balanced version, i.e. \(w_1 = w_2 =, \dots , = w k\), this gives a partition with \(\frac{w_i}{3} \leq w(T_i) \leq 3 w_i\).}, author = {Borndörfer, Ralf and Casel, Katrin and Issac, Davis and Niklanovits, Aikaterini and Schwartz, Stephan and Zeif, Ziena}, booktitle = {Approximation Algorithms for Combinatorial Optimization Problems (APPROX)}, keywords = {sys:relevantfor:ae zienazeif katrincasel davisissac aikaterininiklanovits approx year2021 ralfborndörfer stephanschwartz}, pages = {27:1-27:14}, title = {Connected k-Partition of k-Connected Graphs and c-Claw-Free Graphs}, year = 2021 }

Casel, Katrin; Friedrich, Tobias; Issac, Davis; Niklanovits, Aikaterini; Zeif, Ziena Balanced Crown Decomposition for Connectivity ConstraintsEuropean Symposium on Algorithms (ESA) 2021: 26:1–26:15
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We introduce the balanced crown decomposition that captures the structure imposed on graphs by their connected induced subgraphs of a given size. Such subgraphs are a popular modeling tool in various application areas, where the non-local nature of the connectivity condition usually results in very challenging algorithmic tasks. The balanced crown decomposition is a combination of a crown decomposition and a balanced partition which makes it applicable to graph editing as well as graph packing and partitioning problems. We illustrate this by deriving improved approximation algorithms and kernelization for a variety of such problems. In particular, through this structure, we obtain the first constant-factor approximation for the Balanced Connected Partition (BCP) problem, where the task is to partition a vertex-weighted graph into k connected components of approximately equal weight. We derive a \(3\)-approximation for the two most commonly used objectives of maximizing the weight of the lightest component or minimizing the weight of the heaviest component.
@inproceedings{casel2021balanced, abstract = {We introduce the balanced crown decomposition that captures the structure imposed on graphs by their connected induced subgraphs of a given size. Such subgraphs are a popular modeling tool in various application areas, where the non-local nature of the connectivity condition usually results in very challenging algorithmic tasks. The balanced crown decomposition is a combination of a crown decomposition and a balanced partition which makes it applicable to graph editing as well as graph packing and partitioning problems. We illustrate this by deriving improved approximation algorithms and kernelization for a variety of such problems. In particular, through this structure, we obtain the first constant-factor approximation for the Balanced Connected Partition (BCP) problem, where the task is to partition a vertex-weighted graph into k connected components of approximately equal weight. We derive a \(3\)-approximation for the two most commonly used objectives of maximizing the weight of the lightest component or minimizing the weight of the heaviest component.}, author = {Casel, Katrin and Friedrich, Tobias and Issac, Davis and Niklanovits, Aikaterini and Zeif, Ziena}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {sys:relevantfor:ae zienazeif esa katrincasel davisissac aikaterininiklanovits tobiasfriedrich year2021}, pages = {26:1&ndash;26:15}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {Balanced Crown Decomposition for Connectivity Constraints}, volume = 204, year = 2021 }

Behrendt, Lukas; Casel, Katrin; Friedrich, Tobias; Lagodzinski, J. A. Gregor; Löser, Alexander; Wilhelm, Marcus From Symmetry to Asymmetry: Generalizing TSP Approximations by ParametrizationFundamentals of Computation Theory (FCT) 2021: 53–66
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We generalize the tree doubling and Christofides algorithm to parameterized approximations for ATSP. The parameters we consider for the respective generalizations are upper bounded by the number of asymmetric distances, which yields algorithms to efficiently compute good approximations also for moderately asymmetric TSP instances. As generalization of the Christofides algorithm, we derive a parameterized 2.5-approximation, where the parameter is the size of a vertex cover for the subgraph induced by the asymmetric distances. Our generalization of the tree doubling algorithm gives a parameterized 3-approximation, where the parameter is the minimum number of asymmetric distances in a minimum spanning arborescence. Further, we combine these with a notion of symmetry relaxation which allows to trade approximation guarantee for runtime. Since the two parameters we consider are theoretically incomparable, we present experimental results which show that generalized tree doubling frequently outperforms generalized Christofides with respect to parameter size.
@inproceedings{behrendt2021symmetry, abstract = {We generalize the tree doubling and Christofides algorithm to parameterized approximations for ATSP. The parameters we consider for the respective generalizations are upper bounded by the number of asymmetric distances, which yields algorithms to efficiently compute good approximations also for moderately asymmetric TSP instances. As generalization of the Christofides algorithm, we derive a parameterized 2.5-approximation, where the parameter is the size of a vertex cover for the subgraph induced by the asymmetric distances. Our generalization of the tree doubling algorithm gives a parameterized 3-approximation, where the parameter is the minimum number of asymmetric distances in a minimum spanning arborescence. Further, we combine these with a notion of symmetry relaxation which allows to trade approximation guarantee for runtime. Since the two parameters we consider are theoretically incomparable, we present experimental results which show that generalized tree doubling frequently outperforms generalized Christofides with respect to parameter size.}, author = {Behrendt, Lukas and Casel, Katrin and Friedrich, Tobias and Lagodzinski, J. A. Gregor and Löser, Alexander and Wilhelm, Marcus}, booktitle = {Fundamentals of Computation Theory (FCT)}, editor = {Bampis, Evripidis and Pagourtzis, Aris}, keywords = {gregorlagodzinski alexanderloeser lukasbehrend katrincasel fct tobiasfriedrich year2021 marcuswilhelm}, pages = {53&ndash;66}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {From Symmetry to Asymmetry: Generalizing {TSP} Approximations by Parametrization}, volume = 12867, year = 2021 }

Lagodzinski, J. A. Gregor; Göbel, Andreas; Casel, Katrin; Friedrich, Tobias On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime OrderInternational Colloquium on Automata, Languages and Programming (ICALP) 2021: 91:1–91:15
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study the problem of counting the number of homomorphisms from an input graph \(G\) to a fixed (quantum) graph \(\bar{H}\) in any finite field of prime order \(\mathbb{Z}_p\). The subproblem with graph \(H\) was introduced by Faben and Jerrum [ToC'15] and its complexity is still uncharacterised despite active research, e.g. the very recent work of Focke, Goldberg, Roth, and Zivný [SODA'21]. Our contribution is threefold. First, we introduce the study of quantum graphs to the study of modular counting homomorphisms. We show that the complexity for a quantum graph \(\bar{H}\) collapses to the complexity criteria found at dimension 1: graphs. Second, in order to prove cases of intractability we establish a further reduction to the study of bipartite graphs. Lastly, we establish a dichotomy for all bipartite \( (K_3,3 \ e, domino) \)-free graphs by a thorough structural study incorporating both local and global arguments. This result subsumes all results on bipartite graphs known for all prime moduli and extends them significantly. Even for the subproblem with \(p=2\) this establishes new results.
@inproceedings{lagodzinski2021counting, abstract = {We study the problem of counting the number of homomorphisms from an input graph \(G\) to a fixed (quantum) graph \(\bar{H}\) in any finite field of prime order \(\mathbb{Z}_p\). The subproblem with graph \(H\) was introduced by Faben and Jerrum [ToC'15] and its complexity is still uncharacterised despite active research, e.g. the very recent work of Focke, Goldberg, Roth, and Zivný [SODA'21]. Our contribution is threefold. First, we introduce the study of quantum graphs to the study of modular counting homomorphisms. We show that the complexity for a quantum graph \(\bar{H}\) collapses to the complexity criteria found at dimension 1: graphs. Second, in order to prove cases of intractability we establish a further reduction to the study of bipartite graphs. Lastly, we establish a dichotomy for all bipartite \( (K_{3,3} \ {e}, domino) \)-free graphs by a thorough structural study incorporating both local and global arguments. This result subsumes all results on bipartite graphs known for all prime moduli and extends them significantly. Even for the subproblem with \(p=2\) this establishes new results.}, author = {Lagodzinski, J. A. Gregor and Göbel, Andreas and Casel, Katrin and Friedrich, Tobias}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, keywords = {gregorlagodzinski katrincasel andreasgoebel tobiasfriedrich icalp year2021}, pages = {91:1&ndash;91:15}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{{ü}}r Informatik}, series = {LIPIcs}, title = {On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order}, volume = 198, year = 2021 }

Casel, Katrin; Schmid, Markus L. Fine-Grained Complexity of Regular Path QueriesInternational Conference on Database Theory (ICDT) 2021: 19:1–19:20
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ 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}, pages = {19:1-19:20}, title = {Fine-Grained Complexity of Regular Path Queries}, year = 2021 }

Casel, Katrin; Friedrich, Tobias; Issac, Davis; Klodt, Nicolas; Seifert, Lars; Zahn, Arthur A Color-blind 3-Approximation for Chromatic Correlation Clustering and Improved HeuristicsKnowledge Discovery and Data Mining (KDD) 2021: 882–891
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Chromatic Correlation Clustering (CCC) models clustering of objects with categorical pairwise relationships. The model can be viewed as clustering the vertices of a graph with edge-labels (colors). Bonchi et al. [KDD 2012] introduced it as a natural generalization of the well studied problem Correlation Clustering (CC), motivated by real-world applications from data-mining, social networks and bioinformatics. We give theoretical as well as practical contributions to the study of CCC. Our main theoretical contribution is an alternative analysis of the famous Pivot algorithm for CC. We show that, when simply run color-blind, Pivot is also a linear time 3-approximation for CCC. The previous best theoretical results for CCC were a 4-approximation with a high-degree polynomial runtime and a linear time 11-approximation, both by Anava et al. [WWW 2015]. While this theoretical result justifies Pivot as a baseline comparison for other heuristics, its blunt color-blindness performs poorly in practice. We develop a color-sensitive, practical heuristic we call Greedy Expansion that empirically outperforms all heuristics proposed for CCC so far, both on real-world and synthetic instances. Further, we propose a novel generalization of CCC allowing for multi-labelled edges. We argue that it is more suitable for many of the real-world applications and extend our results to this model.
@inproceedings{casel2021colorblind, abstract = {Chromatic Correlation Clustering (CCC) models clustering of objects with categorical pairwise relationships. The model can be viewed as clustering the vertices of a graph with edge-labels (colors). Bonchi et al. [KDD 2012] introduced it as a natural generalization of the well studied problem Correlation Clustering (CC), motivated by real-world applications from data-mining, social networks and bioinformatics. We give theoretical as well as practical contributions to the study of CCC. Our main theoretical contribution is an alternative analysis of the famous Pivot algorithm for CC. We show that, when simply run color-blind, Pivot is also a linear time 3-approximation for CCC. The previous best theoretical results for CCC were a 4-approximation with a high-degree polynomial runtime and a linear time 11-approximation, both by Anava et al. [WWW 2015]. While this theoretical result justifies Pivot as a baseline comparison for other heuristics, its blunt color-blindness performs poorly in practice. We develop a color-sensitive, practical heuristic we call Greedy Expansion that empirically outperforms all heuristics proposed for CCC so far, both on real-world and synthetic instances. Further, we propose a novel generalization of CCC allowing for multi-labelled edges. We argue that it is more suitable for many of the real-world applications and extend our results to this model.}, author = {Casel, Katrin and Friedrich, Tobias and Issac, Davis and Klodt, Nicolas and Seifert, Lars and Zahn, Arthur}, booktitle = {Knowledge Discovery and Data Mining (KDD)}, keywords = {sys:relevantfor:ae nicolasklodt katrincasel davisissac tobiasfriedrich arthurzahn kdd larsseifert year2021}, pages = {882&ndash;891}, publisher = {ACM}, title = {A Color-blind 3-Approximation for Chromatic Correlation Clustering and Improved Heuristics}, year = 2021 }

2020 [ nach oben ]

Casel, Katrin; Dreier, Jan; Fernau, Henning; Gobbert, Moritz; Kuinke, Philipp; Sanchez Villaamil, Fernando; Schmid, Markus L.; van Leeuwen, Erik Jan Complexity of independency and cliquy treesDiscrete 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, Henning Domination chain: Characterisation, classical complexity, parameterised complexity and approximabilityDiscrete 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, Frank The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search HeuristicsGenetic 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, Florian Extension of vertex cover and independent set in some classes of graphs and generalizationsInternational 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, Florian Extension of some edge graph problems: standard and parameterized complexityFundamentals 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 \setminus 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 \setminus 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 NumberInternational 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, Henning Clustering with Lower-Bounded Sizes - A General Graph-Theoretic FrameworkAlgorithmica 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 dominationTheoretical 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, Katrin Resolving Conflicts for Lower-Bounded ClusteringInternational 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, Sue Combinatorial Properties and Recognition of Unit Square Visibility GraphsInternational 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ç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 Alberto Weak total resolvability in graphsDiscussiones 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 PerspectiveAlgorithmic 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, Henning On the Complexity Landscape of the Domination ChainAlgorithms 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 AlphabetsInternational 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, Henning Building Clusters with Lower-Bounded SizesInternational 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 ApproximationInternational 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, Katrin A Fixed-Parameter Approach for Privacy-Protection with Global RecodingFrontiers 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 }