Structural parameters, tight bounds, and parameterized approximation

Abstract

This thesis studies NP-hard graph problems through structural parameterization andfine-grained analysis. For our problems of study we (i) locate the boundary betweenfixed-parameter tractability and W[1]-hardness, by giving improved hardness reductionsand designing new FPT algorithms; (ii) match natural DP algorithms with tight SETHor pw-SETH-lower bounds; (iii) obtain tight ETH-lower bounds for parameterizationsbeyond treewidth; and (iv) show that adding approximation into the mix can in somecases overcome exact barriers, yet in some other cases it cannot. On our way to theseresults we develop new techniques for both hardness reductions and algorithm designthat may be of independent interest. In particular, we introduce (i) a new variant ofUnary Bin Packing that allows for improved W[1]-hardness results; (ii) techniques forobtaining improved lower bounds for problems parameterized by tree-depth and vertexcover; and (iii) a simple construction for designing FPT approximation schemes. Weleverage these techniques to obtain a number of new results for several well-studiedNP-hard graph problems.

Η παρούσα διατριβή μελετά NP-δύσκολα προβλήματα γράφων μέσω της δομικής παραμετροποίησης και της ανάλυσης λεπτής κλίμακας. Για τα προβλήματα που εξετάζουμε: (i) εντοπίζουμε το όριο μεταξύ FPT και W[1]-δυσκολίας, δίνοντας βελτιωμένες αναγωγές και σχεδιάζοντας νέους FPT αλγορίθμους, (ii) αντιστοιχίζουμε φυσικούς αλγορίθμους δυναμικού προγραμματισμού με βέλτιστα κάτω φράγματα υπό τις υποθέσεις SETH ή pw-SETH, (iii) αποδεικνύουμε βέλτιστα κάτω φράγματα υπό την ETH για παραμετροποιήσεις πέρα από το δενδροπλάτος, και (iv) δείχνουμε ότι η χρήση προσεγγιστικών αλγορίθμων μπορεί, σε ορισμένες περιπτώσεις, να υπερβεί τα εμπόδια της ακριβούς επίλυσης, ενώ σε άλλες περιπτώσεις αυτό δεν είναι δυνατό. Στην πορεία προς την επίτευξη αυτών των αποτελεσμάτων, αναπτύσσουμε νέες τεχνικές τόσο για αναγωγές όσο και για τον σχεδιασμό αλγορίθμων, οι οποίες ενδέχεται να παρουσιάζουν αυτοτελές ενδιαφέρον. Ειδικότερα, εισάγουμε: (i) μια νέα παραλλαγή του προβλήματος Unary Bin Packing, η οποία επιτρέπει την απόδειξη βελτιωμένων αποτελεσμάτων W[1]-δυσκολίας, (ii) τεχνικές για την απόδειξη ισχυρότερων κάτω φραγμάτων για προβλήματα παραμετροποιημένα ως προς το δενδροβάθος και το μέγεθος ενός καλύμματος κορυφών, και (iii) μια απλή κατασκευή για τον σχεδιασμό σχημάτων προσέγγισης FPT. Αξιοποιούμε αυτές τις τεχνικές για να αποδείξουμε μια σειρά νέων αποτελεσμάτων για αρκετά ευρέως μελετημένα NP-δύσκολα προβλήματα γράφων.