31.05.2024

Two Papers accepted at SAND and IWOCA

We have more good paper acceptance news! Together with researchers from the University of Liverpool, George Skretas wrote the paper All for one and one for all: An O(1)-Musketeers Universal Transformation for Rotating Robots. It will appear at the Symposium on Algorithmic Foundations of Dynamic Networks (SAND) on 5-7 June in Patras, Greece. The paper asks what the family of two-dimensional geometric shapes is that can be transformed into each other by a sequence of rotation operations, none of which disconnects the shape. The model represents programmable matter systems consisting of \(n\) devices lying on the cells of a two-dimensional square grid, interconnected modules that perform the minimal mechanical operation of 90 degree rotations around each other. The goal is to transform an initial shape of modules A into a target shape B. The authors prove that any pair of such shapes can be transformed into each other within an optimal \(O(n^2)\) rotation operations none of which disconnects the shape.

The second paper was written by Shaily Verma together with coauthors from the Institute of Mathematical Sciences in Chennai, the University of Bergen and the University of Groningen. Titled Parameterized Complexity of Paired Domination, it was accepted at the International Workshop on Combinatorial Algorithms (IWOCA) taking place on 1-3 July in Ischia, Italy. The Dominating Set problem generally models a guarding problem in which one needs to use the smallest number of guards to protect a certain object. Under this model, it is natural to desire an additional property: each guard has a partner with whom they back up each other. The corresponding problem is called Paired Dominating Set. In the paper, the authors study the parameterized complexity of the problem with respect to different graph parameters. The main result is an FPT algorithm for the problem parameterized by the treewidth of the graph with best running time guarantee.

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" }]}

Clean Citation Style 005

Andreev, Nikita; Bliznets, Ivan; Kundu, Madhumita; Saurabh, Saket; Tripathi, Vikash; Verma, Shaily Parameterized Complexity of Paired DominationInternational Workshop on Combinatorial Algorithms (IWOCA) 2024: 523–536

[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]

@inproceedings{andreev2024parameterized,
  abstract = {The Paired Domination problem is one of the well-studied variants of the classical Dominating Set problem. In a graph \(G\) on \(n\) vertices, a dominating set \(D\) (set of vertices such that \(N[D]=V(G)\)) is called a paired dominating set of \(G\), if \(G[D]\) has perfect matching. In the Paired Domination problem, given a graph \(G\) and a positive integer \(k\), the task is to check whether \(G\) has a paired dominating set of size at most \(k\). The problem is a variant of the Dominating Set problem, and hence inherits most of the hardness of the Dominating Set problem; however, the same cannot be said about the algorithmic results. In this paper, we study the problem from the perspective of parameterized complexity, both from solution and structural parameterization, and obtain the following results. 1. We design an (non-trivial) exact exponential algorithm running in time \(1.7159^n\). 2. It admits Strong Exponential Time Hypothesis (SETH) optimal algorithm parameterized by the treewidth \(tw\) of the graph \(G\). The algorithm runs in time \(4^{tw}n^{O(1)}\) and unless SETH fails, there is no algorithm running in time \((4-\epsilon)^{tw}n^{O(1)}\) for any \(\epsilon >0\). 3. We design an algorithm parameterized by the distance to cluster graphs. We complement this result by proving that the problem does not admit a polynomial kernel under this parameterization and under parameterization by vertex cover number. 4. Paired Domination admits a polynomial kernel on graphs that exclude a biclique \(K_{i,j}\). 5. We also prove that one of the counting versions of Paired Domination parameterized by cliquewidth admits \(n^{2cw+O(1)}\) time algorithm parameterized by cliquewidth (\(cw\)). However, it does not admit an FPT algorithm unless #SETH is false.},
  author = {Andreev, Nikita and Bliznets, Ivan and Kundu, Madhumita and Saurabh, Saket and Tripathi, Vikash and Verma, Shaily},
  booktitle = {International Workshop on Combinatorial Algorithms (IWOCA)},
  keywords = {sys:relevantfor:ae iwoca shailyverma year2024},
  organization = {Springer},
  pages = {523&ndash;536},
  title = {Parameterized Complexity of Paired Domination},
  year = 2024
}