LFCS Seminar: Tuesday, 19 November: Jiaheng Wang Title: Can you link up with treewidth (to prove tight lower bounds for subgraph detection problem)? Abstract: A central result of Marx [FOCS'07, ToC'10], titled "Can you beat treewidth?", proves that there are k-vertex graphs H of maximum degree 3 such that any n^{o(k/log k)} algorithm for detecting colourful H-subgraphs would refute the Exponential-Time Hypothesis (ETH). This result has been widely used to obtain almost-tight lower boundsfor parameterised problems under ETH. Unfortunately, the original proof is highly non-trivial: it not only requires the readers to be familiar with treewidth, linear programming duality, graph embedding and multicommodity flow, but also the proof is based on some black-boxed results. A very recent SOSA'24 paper simplifies the proof, but still requires the knowledge of random graphs, the construction of expanders, and flows in expanders, and again, black-boxed. This means that we cannot expect an average 4th-year undergraduate student to understand either reduction. (Note that "SOSA" is the abbreviation for "Symposium on *Simplicity* in Algorithms".) For the sake of a proof that can be fit into an undergraduate algorithms and complexity textbook, we introduce a novel graph parameter that characterises how well vertices can "communicate" with each other without too much network congestion. From this new perspective, we discover that the desired "almost-tight" hard instances have already been cooked 60 years ago at Bell Labs, but for the purpose of communication networks and parallel computing: the Beneš network. This construction is merely an elementary divide-and-conquer argument that is featured in a 1st-year introductory course at MIT OpenCourseWare. Additionally, our new perspective also yields some new tight lower bounds for some certain classes of graphs, including random graphs, dense graphs, H-minor-free graphs, and most generally, all graphs when parameterised by treewidth. Joint work with Radu Curticapean (Regensburg, ITU Copenhagen), Simon Döring (MPI, Saarland) and Daniel Neuen (Regensburg, MPI). Nov 19 2024 16.10 - 17.10 LFCS Seminar: Tuesday, 19 November: Jiaheng Wang Jiaheng Wang, University of Regensburg https://pw384.github.io/ G.03, IF
LFCS Seminar: Tuesday, 19 November: Jiaheng Wang Title: Can you link up with treewidth (to prove tight lower bounds for subgraph detection problem)? Abstract: A central result of Marx [FOCS'07, ToC'10], titled "Can you beat treewidth?", proves that there are k-vertex graphs H of maximum degree 3 such that any n^{o(k/log k)} algorithm for detecting colourful H-subgraphs would refute the Exponential-Time Hypothesis (ETH). This result has been widely used to obtain almost-tight lower boundsfor parameterised problems under ETH. Unfortunately, the original proof is highly non-trivial: it not only requires the readers to be familiar with treewidth, linear programming duality, graph embedding and multicommodity flow, but also the proof is based on some black-boxed results. A very recent SOSA'24 paper simplifies the proof, but still requires the knowledge of random graphs, the construction of expanders, and flows in expanders, and again, black-boxed. This means that we cannot expect an average 4th-year undergraduate student to understand either reduction. (Note that "SOSA" is the abbreviation for "Symposium on *Simplicity* in Algorithms".) For the sake of a proof that can be fit into an undergraduate algorithms and complexity textbook, we introduce a novel graph parameter that characterises how well vertices can "communicate" with each other without too much network congestion. From this new perspective, we discover that the desired "almost-tight" hard instances have already been cooked 60 years ago at Bell Labs, but for the purpose of communication networks and parallel computing: the Beneš network. This construction is merely an elementary divide-and-conquer argument that is featured in a 1st-year introductory course at MIT OpenCourseWare. Additionally, our new perspective also yields some new tight lower bounds for some certain classes of graphs, including random graphs, dense graphs, H-minor-free graphs, and most generally, all graphs when parameterised by treewidth. Joint work with Radu Curticapean (Regensburg, ITU Copenhagen), Simon Döring (MPI, Saarland) and Daniel Neuen (Regensburg, MPI). Nov 19 2024 16.10 - 17.10 LFCS Seminar: Tuesday, 19 November: Jiaheng Wang Jiaheng Wang, University of Regensburg https://pw384.github.io/ G.03, IF
Nov 19 2024 16.10 - 17.10 LFCS Seminar: Tuesday, 19 November: Jiaheng Wang Jiaheng Wang, University of Regensburg https://pw384.github.io/
