13.09.2024

Best Paper awarded at IPEC

We are very happy to announce to accepted papers at the International Symposium on Parameterized and Exact Computation (IPEC) one of which was awarded as the best paper! The conference took place on 4-6 September in Egham, UK. The paper with the award was written by Katrin Casel, Tobias Friedrich, Aikaterini Niklanovits, Kirill Simonov, and Ziena Zeif, all members or former members of our group and is titled Combining Crown Structures for Vulnerability Measures. Over the past decades, various metrics have emerged in graph theory to grasp the complex nature of network vulnerability. The authors study two specific measures: (weighted) vertex integrity and (weighted) component order connectivity. They capitalize on the structural attributes inherent in different crown decompositions, strategically combining them to introduce novel kernelization algorithms that advance the current state of the field. In particular, the authors extend the scope of the balanced crown decomposition provided by Casel et al. [ESA 2021] and expand the applicability of crown decomposition techniques. There is also a post on LinkedIn about this achievement.

Furthermore, Kirill Simonov also collaborated with coauthors from various universities which resulted in Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs. It presents a subexponential algorithm for Clique Cover on unit disk graphs. On the other hand, it also shows that single-exponential time is necessary for unit ball graphs if the dimension is at least 5. This is in stark contrast to many other common NP-hard problems, where subexponential algorithms are known for unit ball graphs of any constant dimension.

Clean Citation Style 005

{ "authors" : [{ "lastname":"Bläsius" , "initial":"T" , "url":"https://hpi.de/friedrich/publications/people/thomas-blaesius.html" , "mail":"thomas.blasius(at)hpi.de" }, { "lastname":"Casel" , "initial":"K" , "url":"https://hpi.de/friedrich/publications/people/katrin-casel.html" , "mail":"katrin.casel(at)hpi.de" }, { "lastname":"Chauhan" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/ankit-chauhan.html" , "mail":"ankit.chauhan(at)hpi.de" }, { "lastname":"Cohen" , "initial":"S" , "url":"https://hpi.de/friedrich/publications/people/sarel-cohen.html" , "mail":"sarel.cohen(at)hpi.de" }, { "lastname":"Cseh" , "initial":"�" , "url":"https://hpi.de/friedrich/publications/people/agnes-cseh.html" , "mail":"agnes.cseh(at)hpi.de" }, { "lastname":"Doskoč" , "initial":"V" , "url":"https://hpi.de/friedrich/publications/people/vanja-doskoc.html" , "mail":"vanja.doskoc(at)hpi.de" }, { "lastname":"Elijazyfer" , "initial":"Z" , "url":"https://hpi.de/friedrich/people/ziena-elijazyfer.html" , "mail":"ziena.elijazyfer(at)hpi.de" }, { "lastname":"Fischbeck" , "initial":"P" , "url":"https://hpi.de/friedrich/publications/people/philipp-fischbeck.html" , "mail":"philipp.fischbeck(at)hpi.de" }, { "lastname":"Friedrich" , "initial":"T" , "url":"https://hpi.de/friedrich/publications/people/tobias-friedrich.html" , "mail":"friedrich(at)hpi.de" }, { "lastname":"Göbel" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/andreas-goebel.html" , "mail":"andreas.goebel(at)hpi.de" }, { "lastname":"Issac" , "initial":"D" , "url":"https://hpi.de/friedrich/publications/people/davis-issac.html" , "mail":"davis.issac(at)hpi.de" }, { "lastname":"Katzmann" , "initial":"M" , "url":"https://hpi.de/friedrich/publications/people/maximilian-katzmann.html" , "mail":"maximilian.katzmann(at)hpi.de" }, { "lastname":"Khazraei" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/ardalan-khazraei.html" , "mail":"ardalan.khazraei(at)hpi.de" }, { "lastname":"Kötzing" , "initial":"T" , "url":"https://hpi.de/friedrich/publications/people/timo-koetzing.html" , "mail":"timo.koetzing(at)hpi.de" }, { "lastname":"Krejca" , "initial":"M" , "url":"https://hpi.de/friedrich/publications/people/martin-krejca.html" , "mail":"martin.krejca(at)hpi.de" }, { "lastname":"Krogmann" , "initial":"S" , "url":"https://hpi.de/friedrich/publications/people/simon-krogmann.html" , "mail":"simon.krogmann(at)hpi.de" }, { "lastname":"Krohmer" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/anton-krohmer.html" , "mail":"none" }, { "lastname":"Kumar" , "initial":"N" , "url":"https://hpi.de/friedrich/publications/people/nikhil-kumar.html" , "mail":"nikhil.kumar(at)hpi.de" }, { "lastname":"Lagodzinski" , "initial":"G" , "url":"https://hpi.de/friedrich/publications/people/gregor-lagodzinski.html" , "mail":"gregor.lagodzinski(at)hpi.de" }, { "lastname":"Lenzner" , "initial":"P" , "url":"https://hpi.de/friedrich/publications/people/pascal-lenzner.html" , "mail":"pascal.lenzner(at)hpi.de" }, { "lastname":"Melnichenko" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/anna-melnichenko.html" , "mail":"anna.melnichenko(at)hpi.de" }, { "lastname":"Molitor" , "initial":"L" , "url":"https://hpi.de/friedrich/publications/people/louise-molitor.html" , "mail":"louise.molitor(at)hpi.de" }, { "lastname":"Neubert" , "initial":"S" , "url":"https://hpi.de/friedrich/publications/people/stefan-neubert.html" , "mail":"stefan.neubert(at)hpi.de" }, { "lastname":"Pappik" , "initial":"M" , "url":"https://hpi.de/friedrich/publications/people/marcus-pappik.html" , "mail":"marcus.pappik(at)hpi.de" }, { "lastname":"Quinzan" , "initial":"F" , "url":"https://hpi.de/friedrich/publications/people/francesco-quinzan.html" , "mail":"francesco.quinzan(at)hpi.de" }, { "lastname":"Rizzo" , "initial":"M" , "url":"https://hpi.de/friedrich/publications/people/manuel-rizzo.html" , "mail":"manuel.rizzo(at)hpi.de" }, { "lastname":"Rothenberger" , "initial":"R" , "url":"https://hpi.de/friedrich/publications/people/ralf-rothenberger.html" , "mail":"ralf.rothenberger(at)hpi.de" }, { "lastname":"Schirneck" , "initial":"M" , "url":"https://hpi.de/friedrich/publications/people/martin-schirneck.html" , "mail":"martin.schirneck(at)hpi.de" }, { "lastname":"Seidel" , "initial":"K" , "url":"https://hpi.de/friedrich/publications/people/karen-seidel.html" , "mail":"karen.seidel(at)hpi.de" }, { "lastname":"Sutton" , "initial":"A" , "url":"https://hpi.de/friedrich/publications/people/andrew-m-sutton.html" , "mail":"none" }, { "lastname":"Weyand" , "initial":"C" , "url":"https://hpi.de/friedrich/publications/people/christopher-weyand.html" , "mail":"none" }]}

Casel, Katrin; Friedrich, Tobias; Niklanovits, Aikaterini; Simonov, Kirill; Zeif, Ziena Combining Crown Structures for Vulnerability MeasuresInternational Symposium on Parameterized and Exact Computation (IPEC) 2024

[ Abstract ] [ BibTeX ]

@inproceedings{casel2024combining,
  abstract = {Over the past decades, various metrics have emerged in graph theory to grasp the complex nature of network vulnerability. In this paper, we study two specific measures: (weighted) vertex integrity (wVI) and (weighted) component order connectivity (wCOC). These measures not only evaluate the number of vertices required to decompose a graph into fragments, but also take into account the size of the largest remaining component. The main focus of our paper is on kernelization algorithms tailored to both measures. We capitalize on the structural attributes inherent in different crown decompositions, strategically combining them to introduce novel kernelization algorithms that advance the current state of the field. In particular, we extend the scope of the balanced crown decomposition provided by Casel et al.&nbsp;\cite{DBLP:conf/esa/Casel0INZ21} and expand the applicability of crown decomposition techniques. In summary, we improve the vertex kernel of VI from \(p^3\) to \(p^2\), and of wVI from \(p^3\) to \(3(p^2 + {p}^{1.5} p_{\ell})\), where \(p_{\ell} < p\) represents the weight of the heaviest component after removing a solution. For wCOC we improve the vertex kernel from \(\mathcal{O}(k^2W + kW^2)\) to \(3\mu(k + \sqrt{\mu}W)\), where \(\mu = \max(k,W)\). We also give a combinatorial algorithm that provides a \(2kW\) vertex kernel in fixed-parameter tractable time when parameterized by \(r\), where \(r \leq k\) is the size of a maximum \((W+1)\)-packing. We further show that the algorithm computing the \(2kW\) vertex kernel for COC can be transformed into a polynomial algorithm for two special cases, namely when \(W=1\), which corresponds to the well-known vertex cover problem, and for claw-free graphs. In particular, we show a new way to obtain a $2k$ vertex kernel (or to obtain a 2-approximation) for the vertex cover problem by only using crown structures.},
  author = {Casel, Katrin and Friedrich, Tobias and Niklanovits, Aikaterini and Simonov, Kirill and Zeif, Ziena},
  booktitle = {International Symposium on Parameterized and Exact Computation (IPEC)},
  keywords = {aikaterininiklanovits ipec katrincasel kirillsimonov tobiasfriedrich year2024 zienazeif},
  note = {Best Paper Award},
  title = {Combining Crown Structures for Vulnerability Measures},
  year = 2024
}