Workshop "Combinatorial Reconfiguration and Fixed-Parameter Tractability"
| Date and time: | 2022.12.12 Mon.
|
||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Venue: | Online (Free of charge) | ||||||||||||||
| Speaker: | |||||||||||||||
| Title: | |||||||||||||||
| Summary: | As a part of the research project "Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration" (head investigator: Takehiro Ito), we are going to organize Workshop "Combinatorial Reconfiguration and Fixed-Parameter Tractability" via Zoom on December 12, 2022 (based on European Timezone).
The objective is to learn recent developments of fixed-parameter (in)tractability and their relations with combinatorial reconfiguration. In her influential survey paper "Introduction to Combinatorial Reconfiguration" (Algorithms 2018), Naomi Nishimura dedicated one section to applications of the parameterized complexity methodology to problems on combinatorial reconfiguration. Indeed, several papers have been presented along this line of research. Furthermore, the research activity on fixed-parameter (in)tractability has been quite active, and there are a lot of recently introduced methods that are waiting for being applied to combinatorial reconfiguration. In this workshop, we will learn recent research trends of fixed-parameter tractability and combinatorial reconfiguration, and will discuss a new connection between these two fields of theoretical computer science. This workshop aims at the broad audience of discrete mathematics and theoretical computer science, who wish to learn and work on these active research areas.
The program will be exclusively composed of invited talks. Each talk is planned to span one hour, including discussion.
List of Confirmed Invited Speakers
Registration
Registration is free of charge, but please make your registration in advance.
Program
2022.12.12 Mon. CET (JST)
Talk Titles and Abstracts
Eun Jung Kim (Paris-Dauphine University, France)
Title: Twin-Width and Its Implications
Abstract: First Order Logic (FO logic) expresses many classic computational problems such as k-Independent Set problem with variables and logical connectives. First Order model checking is known to be fixed-parameter tractable on important classes such as nowhere dense classes, bounded rank-width graphs, unit interval graphs as well as strict hereditary classes of permutations. A notion called twin-width, introduced by Bonnet, Kim, Thomassé, Watrigant (FOCS 2020), elegantly captures vast swathes of such classes, and provides a new perspective to explain why so many computational problems are fixed-parameter tractable on graph classes seemlying so different. We will briefly sketch the new notion, and its rapidly developing impact in theoretical computer science with an emphasis on algorithm designs.
Moritz Mühlenthaler (Université Grenoble Alpes, France)
Title: Constraint Satisfaction Reconfiguration
Abstract: The constraint satisfaction problem (CSP) asks for an assignment of values to variables such that given constraints are satisfied. Special cases of the CSP are for example graph coloring and Boolean satisfiability. We consider the following reconfiguration variant of the CSP: given two feasible solutions of a CSP instance, can we transform one solution into the other by changing the value of a single variable at a time, such that in each step the constraints are satisfied? We give an overview of what is known about the complexity of this question and highlight the techniques behind recent algorithmic results.
Saket Saurabh (The Institute of Mathematical Sciences, India)
Title: FPT Approximation Schemes for the Maximum Coverage and MAX-SAT Problem
Abstract: Vertex Cover is a classical NP-hard problem. Partial Vertex Cover is a variant of the Vertex Cover problem where the goal is to maximize the number of edges covered, given a fixed number of vertices that can be used. Partial Vertex Cover is a W[1]-hard problem. There are FPT approximation schemes for Partial Vertex Cover parameterized by the solution size, i.e., there are $(1-\epsilon)$-factor approximation algorithms running in time $f(k,\epsilon) n^{O(1)}$ for all $0<\epsilon<1$. In this talk, we consider the Partial Vertex Cover problem and SAT problems in hypergraphs where there is no bound on the size of the hyperedges. We design an FPT approximation scheme for these problems on hypergraphs that satisfies the Kij-free property, i.e., no $i$ vertices are contained in $j$ common hyperedges.
Bart M. P. Jansen (Eindhoven University of Technology, the Netherlands)
Title: Search Space Reduction Beyond Kernelization
Abstract: The framework of kernelization gives a mathematical model for the rigorous analysis of preprocessing, aimed at showing that any instance with parameter k can efficiently be reduced to an equivalent one whose size depends only on k. Kernelization serves as a useful tool to obtain FPT algorithms, since any brute-force algorithm solves the reduced instance in time depending only on k. However, from the definition of kernelization it is not clear why kernelization would lead to significant speed-ups when the reduced instance is not solved by brute force, but by a fixed-parameter tractable algorithm whose running time is governed by the value of the parameter. To speed up such algorithms, it is the parameter controlling the size of the search space which should decrease, rather than the encoding size of the input. The discrepancy between reducing the instance size versus decreasing the search space is the focus of this talk. The quest for preprocessing algorithms that reduce the search space leads to a new type of algorithmic and graph-theoretical questions. The talk gives an introduction to this budding line of inquiry by presenting examples from recent work on the search for essential vertices and antler structures in graphs.
Based on joint work with Benjamin M. Bumpus, Huib Donkers, and Jari J.H. de Kroon.
Hans L. Bodlaender (Utrecht University, the Netherlands)
Title: Parameterized Complexity of Reconfiguration of Small Independent Sets and Dominating Sets
Abstract: In this talk, we look at the complexity of reconfiguring independent or dominating sets, where we assume that the size of the sets is a small parameter k, under different rules of moving the "tokens". It appears that the parameterized complexity depends on the assumption of how the number of moves that can be made is specified, but less on the type of moves.
Some related literature is also reviewed. Organizers
|
Update:2022.10.15