5 papers
Playing Sudoku on random 3-regular graphs
Jack Dippel, Austin Eide, Pawel Pralat +1
The Sudoku number of graph with chromatic number is the smallest partial -colouring of that determines a unique -colouring of the entire graph. We…
Eliminating Majority Illusion is Easy
Jack Dippel, Max Dupré la Tour, April Niu +2
Majority Illusion is a phenomenon in social networks wherein the decision by the majority of the network is not the same as one's personal social circle's majority, leading to an i…
Gerrymandering Planar Graphs
Jack Dippel, Max Dupré la Tour, April Niu +2
We study the computational complexity of the map redistricting problem (gerrymandering). Mathematically, the electoral district designer (gerrymanderer) attempts to partition a wei…
One n Remains to Settle the Tree Conjecture
Jack Dippel, Adrian Vetta
In the famous network creation game of Fabrikant et al. a set of agents play a game to build a connected graph. The agents form the vertex set of the graph and each vertex…
An Improved Approximation Algorithm for the Matching Augmentation Problem
J. Cheriyan, R. Cummings, J. Dippel +1
We present a -approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost ze…