Combinatorial Reconfiguration (17w5066)

Arriving in Banff, Alberta Sunday, January 22 and departing Friday January 27, 2017

Organizers

(University of Waterloo)

(Tohoku University)

Amer Mouawad (University of Bergen)

Objectives

The objectives of the workshop can be summarized as follows, with indications of how each might be achieved:

• Providing an opportunity for joint discussion by researchers in reconfiguration from all over the world; the organizers alone represent Europe, Asia, and North America. (This will expand upon CoRe 2015, held in February 2015 in Sendai, Japan, with twenty participants.)

• Identifying future research directions. To support this objective, the workshop will include open problem sessions, in which participants will give short presentations on the background of such problems.

• Deepening the area by establishing a set of common methods and algorithmic techniques. Tutorials and invited lectures will serve this aim.

• Broadening the area by making connections to related areas and problems. We wish to emphasize questions that have received little study and stress application domains. To this end, our invitation list includes experts from related areas.

Below, we elaborate further on the last two objectives.

Techniques




Recent research has shown that solving a reconfiguration problem often requires solving the associated search problem along the way. For instance, successful algorithms for independent set reconfiguration implicitly solve the maximum independent set problem for the considered graph class [4, 2]. Hence one often needs to extend (classic) techniques that have been developed for solving these search problems.


Many of the studied reconfiguration problems involve solutions to graph problems, such as vertex colorings, independent sets, dominating sets, and matchings of graphs. For solving more traditional, NP-hard (optimization) graph problems, using various types of graph decompositions or graph representations has turned out to be a very succesful algorithmic method. Examples of decompositions are tree decompositions, $k$-expressions (related to cliquewidth), and modular decompositions. Examples of graph representations are geometric representations such as interval representations. Many graph problems can be solved efficiently using dynamic programming over these decompositions / representations [1]. The success of these approaches is illustrated for instance by various meta theorems that state that large classes of NP-hard graph problems can be solved this way [7]. Hence there is a significant interest in obtaining similar results for (PSPACE-hard) reconfiguration problems.


Recently, the first successful dynamic programming approaches for reconfiguration problems have been reported. In particular, a dynamic programming method over tree decompositions [14] was used to efficiently find shortest reconfiguration sequences for a wide variety of reconfiguration problems in which each solution is a subset of the vertices, and a meta theorem was obtained. Other recent dynamic programming algorithms have used layer decompositions of planar graphs [11] and modular decompositions [2].


In another category of problems, strong results have been obtained on the reconfiguration of Boolean satisfiability [8] and constraint satisfaction problems (CSPs) [5]. Such results are widely applicable since many other problems can be formulated as (Boolean) CSPs, including various of the aforementioned graph problems. During the workshop, we hope to establish a wider range of problems to which these concepts and techniques can be applied.


Related Areas and Applications




Various other research areas are concerned with searching through exponentially large solution spaces, using a variety of techniques. Local search is an important example, where many advanced techniques have been introduced [12, 16]. The main question studied in the literature is whether any local optimum can be found efficiently (not necessarily from an initial solution using reconfiguration rules). Although this is a different question than commonly studied in reconfiguration, it seems worthwhile to explore how techniques developed in either area can be used for the other.


Motivations for the study of reconfiguration problems stem from a wide range of application areas. For example, questions related to the reconfiguration of graph colorings have come up in the study of random sampling methods for graph coloring, in statistical physics, and by questions related to changing frequency assignments in wireless networks while maintaining functionality. See [9] for more information on these applications.


More generally, the question whether one can reach any desirable configuration from a given initial configuration, using clearly defined reconfiguration steps, occurs naturally in many application areas. Examples are the rearrangement of stacks in storage spaces, the rearrangement of trains in switchyards, planning the movement of robots, and so on. All of these questions have received considerable study in operations research, often in the form of computational studies where heuristics are implemented and compared.


In the workshop we plan to explore not only further domains in which reconfiguration naturally arises, but also how recent (theoretical) progress on reconfiguration can be applied to such domains, to obtain better practical solutions.


Bibliography



  1. Hans L Bodlaender. Dynamic programming on graphs with bounded treewidth. In ICALP 1988, volume 317 of LNCS, pages 105--118. Springer, 1988.

  2. Paul Bonsma. Independent set reconfiguration in cographs. arXiv:1402.1587. To appear in the proceedings of WG 2014, 2014.

  3. Paul Bonsma and Luis Cereceda. Finding paths between graph colourings: {PSPACE}-completeness and superpolynomial distances. Theor. Comput. Sci., 410(50):5215--5226, 2009.

  4. Paul Bonsma, Marcin Kamiński, and Marcin Wrochna. Reconfiguring independent sets in claw-free graphs. In SWAT 2014, volume 8503 of LNCS, pages 86--97. Springer, 2014.

  5. Paul Bonsma, Amer Mouawad, Naomi Nishimura, and Venkatesh Raman. The complexity of bounded length graph recoloring and {CSP] reconfiguration. To appear in the proceedings of IPEC 2014, 2014.

  6. Luis Cereceda, Jan van den Heuvel, and Matthew Johnson. Finding paths between 3-colorings. J. Graph Theory, 67(1):69--82, 2011.

  7. Bruno Courcelle. The monadic second-order logic of graphs. {I}. recognizable sets of finite graphs. Information and Computation, 85(1):12 -- 75, 1990.

  8. Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, and Christos H. Papadimitriou. The connectivity of boolean satisfiability: computational and structural dichotomies. SIAM J. Comput., 38(6):2330--2355, 2009.

  9. Jan van den Heuvel. The complexity of change. Surveys in Combinatorics 2013, pages 127--160, 2013.

  10. Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. On the complexity of reconfiguration problems. Theor. Comput. Sci., 412(12-14):1054--1065, 2011.

  11. Takehiro Ito, Marcin Kamiński, and Hirotaka Ono. Fixed-parameter tractability of token jumping on planar graphs. Accepted for ISAAC 2014, 2014.

  12. David S Johnson, Christos H Papadimitriou, and Mihalis Yannakakis. How easy is local search? Journal of computer and system sciences, 37(1):79--100, 1988.

  13. Marcin Kamiński, Paul Medvedev, and Martin Milanič. Complexity of independent set reconfigurability problems. Theor. Comput. Sci., 439:9--15, June 2012.

  14. Amer Mouawad, Naomi Nishimura, Venkatesh Raman, and Marcin Wrochna. Reconfiguration over tree decompositions. To appear in the proceedings of IPEC 2014, 2014.

  15. Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Narges Simjour, and Akira Suzuki. On the parameterized complexity of reconfiguration problems. In IPEC 2013, volume 8246 of LNCS, pages 281--294. Springer, 2013.

  16. Alejandro A Schäffer and Mihalis Yannakakis. Simple local search problems that are hard to solve. SIAM journal on Computing, 20(1):56--87, 1991.