# Program

Talks will start on Thursday 23rd at 9.00 and will end on Friday 24th at 18.20.

# Keynotes

# Ulrik Brandes

*ETH Zurich*

### Social Networks, First Principles, and Graph Modification

Social network analysis is an applied network science, so that graphs take center stage as a data representation. After a brief introduction to the field, I will develop some of the more common forms of analysis such as centrality, roles, and clustering from first principles, and highlight graph modification problems along the way.### Biography

Ulrik Brandes is Professor for Social Networks in the Department of Humanities, Social and Political Sciences at ETH Zurich. His background is in algorithmics, with special interests in graph algorithms and network visualization. After 15 years as a professor in computer science, also teaching courses such Theory of Computing and Algorithms and Data Structures, he finally gave himself up entirely to his passion for social network science. Methodology and method development in this area are complemented by a growing interest in societal challenges arising from the Digital Transformation.# Martin Milanič

*University of Primorska*

### Edge elimination schemes of weighted graph classes

In 2017, Laurent and Tanigawa extended to weighted graphs the classical notion of perfect elimination ordering for graphs, giving a framework capturing common vertex elimination orderings of families of chordal graphs, Robinsonian matrices, and ultrametrics. They show that an edge-weighted graph G has a perfect elimination ordering if and only if it has a vertex ordering that is a simultaneous perfect elimination ordering of all its level graphs, where the level graph of G is any graph obtained from G by removing all sufficiently light edges. In particular, this latter condition implies that all the level graphs must be chordal. We generalize this definition as follows. Given a graph class C, we say that an edge-weighted graph is level-C if all its level graphs are in C. A particularly nice situation occurs when all the edges of an edge-weighted level-C graph can be eliminated one at a time, from lightest to heaviest, so that all the intermediate graphs are in C. Such an edge elimination ordering is called a sorted perfect edge elimination ordering. We show that if C is the class of threshold graphs, split graphs, chordal graphs, or their complements, then every level-C edge-weighted graph has a sorted perfect edge elimination ordering. Our constructive proofs are based on a generalization of the concept of monotone graph classes. We say that a graph class C is gap monotone if for every two graphs G and G' in C such that G is a spanning subgraph of G', graph G can be obtained from G' by a sequence of edge deletions such that all intermediate graphs are in C. We show that, in contrast with many other well known classes of perfect graphs, the classes of threshold graphs, split graphs, and chordal graphs are gap monotone. This is a joint work with J. Beisegel, N. Chiarelli, E. Köhler, M. Krnc, N. Pivač, R. Scheffler, and M. Strehler.### Biography

Martin Milanič is a Full Professor at the University of Primorska in Koper, Slovenia. After getting his diploma at the University of Ljubljana in 2003, he went to Rutgers University in New Jersey, where he earned his PhD in 2007 with his thesis "Algorithmic Developments and Complexity Results for Finding Maximum and Exact Independent Sets in Graphs". Between 2007 and 2009, he was a postdoc researcher in Germany at Bielefeld University. In 2009, he became Assistant Professor and Research Fellow at the University of Primorska. Between 2013 and 2014, he was also a Research Fellow at the Institute of Mathematics, Physics and Mechanics (IMFM) in Ljubljana. Since 2019, he is a Full Professor at the Faculty of Mathematics, Natural Sciences and Information Technologies and a Research Counsellor at the Andrej Marušič Institute of the University of Primorska. His research interests lie in algorithmic graph theory, the study of independence and domination graph invariants, the structure and characterization of graphs in hereditary classes, and applications of combinatorial optimization and graph theory to computational biology. In 2017 he was awarded a Zois Certificate of Recognition for important achievements in scientific research work in the field of discrete mathematics. He is editorial board member of Discrete Applied Mathematics, Ars Mathematica Contemporanea, and The Art of Discrete and Applied Mathematics.# Program of the workshop

# Thursday 23rd January

### 8h30 -- REGISTRATION

### 9h00 -- Keynote : Ulrik Brandes, ETH Zurich

*Social Networks, First Principles, and Graph Modification* (Slides)

Abstract

### 10h00 -- Coffee break

### 10h20 -- Contributed talks (25 mn)

*Structural Rounding (Slides)*

Brian Lavallee*Enumeration of minimal completions and maximal induced subgraphs (Slides)*

Caroline Brosse*Switching checkerboards (Slides)*

David Ellison

### 11h50 -- Lunch break + free time

### 15h00 -- Contributed talks (25 mn)

*Kernelization for Paw-free Edge Modification (Slides)*

Yuping Ke*A Polynomial Kernel for Paw-Free Editing (Slides)*

William Lochet*Incompressibility of H-free edge modification problems: Towards a dichotomy (Slides)*

R. B. Sandeep

### 16h30 -- Break

### 16h50 -- Contributed talks (25 mn)

*Parameterized Aspects of Strong Subgraph Closure (Slides)*

Paloma Lima

### 17h20 -- Open problems session

### 18h20 -- End of the first day

# Friday 24th January

### 9h00 -- Keynote : Martin Milanič, University of Primorska

*Edge elimination schemes of weighted graph classes* (Slides)

Abstract

### 10h00 -- Coffee break

### 10h20 -- Contributed talks (25 mn)

*Preprocessing Vertex-Deletion Problems: Characterizing Graph Properties by Low-Rank Adjacencies (Slides)*

Jari de Kroon*Computing Independent Transversals for H-Free Graphs of Bounded Diameter (Slides)*

Siani Smith*Computing Subset Transversals in H-Free Graphs*

Nick Brettell

### 11h50 -- Lunch break + free time

### 15h30 -- Contributed talks (25 mn)

*Subgraph Complementation (Slides)*

Torstein Strømme*Building Large k-cores in Graphs of Small Degeneracy (Slides)*

Kirill Simonov*A Polynomial Kernel for Funnel Arc Deletion Set (Slides)*

Marcelo Milani

### 17h00 -- Break

### 17h20 -- Contributed talks (25 mn)

*A tool for minimal cograph modification problems (Slides)*

Christophe Crespelle*Structured Connectivity Augmentation (Slides)*

Petr Golovach

### 18h20 -- End of the workshop

# Sponsors

The workshop is funded by the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 749022, PROXNET project, and by the University of Bergen.