We study the NP‐hard shortest path most vital edges problem arising in the context of analyzing network robustness. For an undirected graph with positive integer edge lengths and two designated vertices s and t, the goal is to delete as few edges as possible in order to increase the length of the (new) shortest st‐path as much as possible. This scenario has been studied from the viewpoint of parameterized complexity and approximation algorithms. We contribute to this line of research by providing refined computational tractability as well as hardness results. We achieve this by a systematic investigation of various problem‐specific parameters and their influence on the computational complexity. Charting the border between tractability and intractability, we also identify numerous challenges for future research.

In this paper, we consider the TARGET SET SELECTION problem: given a graph and a threshold value thr(v) for each vertex v of the graph, find a minimum size vertex-subset to “activate” such that all vertices of the graph are activated at the end of th

Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For m-edge and n-vertex graphs, it is well-known to be solvable in $$O(m\sqrt{n})$$O ( m n ) time; however, for several applications this running time is still too slow. We investigate how linear-time (and almost linear-time) data reduction (used as preprocessing) can alleviate the situation. More specifically, we focus on linear-time kernelization. We start a deeper and systematic study both for general graphs and for bipartite graphs. Our data reduction algorithms easily comply (in form of preprocessing) with every solution strategy (exact, approximate, heuristic), thus making them attractive in various settings.