Combinatorics and Computing Weekly Seminar
Parameterized Algorithms and Price of Generality
Parameterized Algorithms and Price of Generality
Ramin Javadi, Isfahan University of Technology, IPM
15 MAY 2024
14:00 - 15:00
One approach toward dealing with intractable graph problems is structural parameterization which is defined as investigation of computational complexity of NP-hard graph problems measured as a function of the structural properties of the input graph. The structure of a graph can be measured using some well-known and well-studied parameters such as treewidth, tree-depth, clique-width, vertex cover and neighborhood diversity. The main question, here, is that, for an NP-hard problem, what is the algorithmic cost of generalizing a structural parameter of the input. In this talk, after introducing some of these parameters, we give a short (and not thorough) survey on the tools such as DP and ILP techniques using in investigation of the complexity of hard problems whose input space is confined on a class of graphs with a specified structure (e.g. bounded treewidth graphs). Moreover, we give a brief introduction to the theory of parameterized complexity and classifying NP-hard problems into classes such as FPT and W[1]-hard in terms of their tractability with respect to structural parameters of the input graph.
Zoom room information:
https://us06web.zoom.us/j/89600366073?pwd=RMHt0eGdvGtkaDBG1Me3y8bOLgooGh.1
Meeting ID : 896 0036 6073
Passcode : 290109
Venue: Niavaran, Lecture Hall 1