Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

21.04.2023

Five Papers accepted at PODC, SEA, FORC and WADS

We are happy to announce five recently accepted papers: First, one paper will appear at the ACM Symposium on Principles of Distributed Computing on 19-23 June in Orlando, USA. The paper with the title The Impact of Cooperation in Bilateral Network Creation is based on the master thesis of Arthur Zahn and investigates the formation of bilateral networks among selfish agents (e.g. social networks) from a game-theoretic point of view. It focuses mainly on the trade-off between the amount of cooperation and the Price of Anarchy by analyzing different solution concepts that capture various degrees of cooperation among the agents.

A second paper titled Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover was accepted at the 21st Symposium on Experimental Algorithms (SEA) which will take place on 24-26 July in Barcelona, Spain. The paper was written by our students about the algorithm with which they also won the third place in the exact track of the PACE Challenge 2022. The algorithm is for the directed feedback vertex set problem using the idea of iterative reduction to vertex cover. They perform computational experiments showing that they outperform other approaches for those directed graphs having a low density of uni-directed edges.

Furthermore, the paper Fair Correlation Clustering in Forests was accepted at the Symposium on Foundations of Responsible Computing (FORC) on 7-9 June in Stanford, USA. The paper which is based on the master thesis of Simon Wietheger, studies the established Correlation Clustering problem under fairness constraints, i.e. requiring that in a vertex colored graph the color distribution in each computed cluster should match the color distribution of the complete vertex set. The authors demonstrate the NP-hardness of the problem even on restricted classes of forests and when relaxing the fairness constraint to only roughly match the color ratio as well as they provide polynomial time algortihms for forests under certain assumptions on the color distribution.

Finally at the Algorithms and Data Structures Symposium (WADS) which will take place on 31 July - 2 August in Montreal, Canada, two papers were accepted. In the first, Compact Distance Oracles with Large Sensitivity and Low Stretch, the authors present an \(f\)-edge fault-tolerant distance sensitivity oracle with large sensitivity, low stretch, and non-trivial query time. Such an oracle is a way of preprocessing a graph to efficiently answer distance queries approximately even when up to \(f\) edges are removed for the query.

In the second paper titled Socially Fair Matching: Exact and Approximation Algorithms, the authors introduce a variant of the Maximum Matching problem that models the social fairness objective: The goal is to find a perfect matching as well as an assignment that assigns the cost of each matched edge to one of its endpoints, such that the maximum of the total cost assigned to either of the two groups is minimized. They show that despite being weakly NP-hard, the problem admits a deterministic PTAS and a randomized FPTAS.

  • The Impact of Cooperation... - Download
    Friedrich, Tobias; Gawendowicz, Hans; Lenzner, Pascal; Zahn, Arthur The Impact of Cooperation in Bilateral Network CreationACM Symposium on Principles of Distributed Computing (PODC) 2023
     
  • Fair Correlation Clusteri... - Download
    Casel, Katrin; Friedrich, Tobias; Schirneck, Martin; Wietheger, Simon Fair Correlation Clustering in ForestsFoundations of Responsible Computing (FORC) 2023
     
  • Compact Distance Oracles ... - Download
    Bilò, Davide; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Krogmann, Simon; Schirneck, Martin Compact Distance Oracles with Large Sensitivity and Low StretchAlgorithms and Data Structures Symposium (WADS) 2023