How many friends do you have? Are you and I friends, or friends of common friends, or friends of friends of friends? What is the largest group of your friends that are also friends of each other? Well-known algorithms exist to efficiently compute the answer to the first two questions. Stunningly, no algorithm is likely to exist that efficiently answers the third question. A major caveat, however, is that this last observation assumes that we have no specific knowledge about the network.
In this talk, I will investigate how knowledge of the structure of a network can be exploited in the quest for efficient algorithms. I will also employ a novel paradigm in algorithm design and analysis called parameterized algorithms. In recent work, I combined this paradigm with structural properties of networks to achieve fine-grained dichotomies for the algorithmic complexity of many problems. In particular, I will take you on a journey from the Clique problem in social networks to the Dominating Set problem in an intriguing class of networks called t-claw-free graphs.