The Network Diversion Problem
Data Skeptic6 Jul 2025

The Network Diversion Problem

In this episode, Professor Pål Grønås Drange from the University of Bergen, introduces the field of Parameterized Complexity - a powerful framework for tackling hard computational problems by focusing on specific structural aspects of the input. This framework allows researchers to solve NP-complete problems more efficiently when certain parameters, like the structure of the graph, are "well-behaved".

At the center of the discussion is the network diversion problem, where the goal isn't to block all routes between two points in a network, but to force flow - such as traffic, electricity, or data - through a specific path. While this problem appears deceptively similar to the classic "Min.Cut/Max.Flow" algorithm, it turns out to be much harder and, in general, its complexity is still unknown. Parameterized complexity plays a key role here by offering ways to make the problem tractable under constraints like low treewidth or planarity, which often exist in real-world networks like road systems or utility grids.

Listeners will learn how vulnerability measures help identify weak points in networks, such as geopolitical infrastructure (e.g., gas pipelines like Nord Stream).

Follow out guest: Pål Grønås Drange

Denne episoden er hentet fra en åpen RSS-feed og er ikke publisert av Podme. Den kan derfor inneholde annonser.

Episoder(608)

Recommender Systems Today and Tomorrow

Recommender Systems Today and Tomorrow

In the final episode of our Recommender Systems season, we explore the growing questions of trust, manipulation, privacy, fairness, sustainability, and user control. From fake reviews and shilling att...

9 Sep 22min

Recommender Systems Optimization Goals

Recommender Systems Optimization Goals

In part two of the Data Skeptic Recommender Systems season finale, Kyle asks a deceptively difficult question: what should recommender systems actually optimize for? Drawing on conversations from acro...

1 Sep 31min

Recommender Systems Origin Story

Recommender Systems Origin Story

Where did recommender systems come from, and how do we know when they're actually working? In part one of Data Skeptic's three-part Recommender Systems finale, Kyle traces the field from collaborative...

18 Aug 25min

Social Choice for Fair Recommendations

Social Choice for Fair Recommendations

Recommender systems influence nearly every aspect of our digital lives—but what does it mean for those systems to be fair? Robin Burke joins Data Skeptic to discuss the history of recommender systems,...

27 Jul 42min

News Recommendations

News Recommendations

News recommendation algorithms influence far more than what stories we click—they can shape our understanding of the world. In this episode, Kyle Polich speaks with Andreea Iana about responsible AI, ...

2 Jul 46min

Give Users the Wheel

Give Users the Wheel

What if you could simply tell a recommendation system what you want instead of relying on likes, dislikes, and watch history? Kyle Polich talks with Fuyuan Lyu about the DPR framework, which combines ...

23 Jun 35min

AutoLike

AutoLike

How can researchers audit recommendation systems when the algorithms are hidden from view? Hieu Le joins Kyle Polich to discuss Auto-Like, a reinforcement learning framework that systematically explor...

17 Jun 35min

Student Spotlight: Aaron Payne, Data Analyst

Student Spotlight: Aaron Payne, Data Analyst

Aaron Payne, an MBA student at Georgia Tech studying business analytics and a Senior Insights Analyst at Chick-fil-A, joins Kyle Polich to talk about turning analytics into decisions that matter. They...

1 Mai 25min

Populært innen Vitenskap

fastlegen
romkapsel
tingenes-tilstand
jss
liberal-halvtime
forskningno
sinnsyn
rekommandert
villmarksliv
rss-paradigmepodden
fjellsportpodden
tomprat-med-gunnar-tjomlid
grunnstoffene
nordnorsk-historie
rss-nysgjerrige-norge
tidlose-historier
psykopoden
rss-rekommandert
rss-inn-til-kjernen-med-sunniva-rose
smart-forklart