Incremental optimization of independent sets under the reconfiguration framework
- PDF / 478,457 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 48 Downloads / 192 Views
Incremental optimization of independent sets under the reconfiguration framework Takehiro Ito1 · Haruka Mizuta1 · Naomi Nishimura2 · Akira Suzuki1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Suppose that we are given an independent set I0 of a graph G, and an integer l ≥ 0. Then, we are asked to find an independent set of G having the maximum size among independent sets that are reachable from I0 by either adding or removing a single vertex at a time such that all intermediate independent sets are of size at least l. We show that this problem is PSPACE-hard even for bounded-pathwidth graphs, and remains NP-hard for planar graphs. On the other hand, we give a linear-time algorithm to solve the problem for chordal graphs. We also study the parameterized complexity of the problem with respect to the following three parameters: the degeneracy d of an input graph, a lower bound l on the size of independent sets, and a lower bound s on the size of a solution reachable from I0 . We show that the problem is fixed-parameter intractable when only one of d, l, or s is taken as a parameter. On the other hand, we give a fixed-parameter algorithm when parameterized by s + d; this result implies that the problem parameterized only by s is fixed-parameter tractable for planar graphs, and for bounded-treewidth graphs. Keywords Combinatorial reconfiguration · Graph algorithms · Independent set
A preliminary version of the paper has been presented at the 25th International Computing and Combinatorics Conference (COCOON 2019) (Ito et al. 2019).
B
Haruka Mizuta [email protected] Takehiro Ito [email protected] Naomi Nishimura [email protected] Akira Suzuki [email protected]
1
Tohoku University, Sendai, Japan
2
University of Waterloo, Waterloo, Canada
123
Journal of Combinatorial Optimization
1 Introduction Recently, the reconfiguration framework (Ito et al. 2011) has been intensively applied to a variety of search problems, as detailed in surveys on the topic (van den Heuvel 2013; Nishimura 2018). For example, the independent set reconfiguration problem is one of the most well-studied reconfiguration problems (Bonamy and Bousquet 2017; Bousquet et al. 2017; Hoang and Uehara 2016; Ito et al. 2014a, b; Kami´nski et al. 2012; Lokshtanov and Mouawad 2018; Lokshtanov et al. 2018; Mouawad et al. 2017; Wrochna 2018). For a graph G, a vertex subset I ⊆ V (G) is an independent set of G if no two vertices in I are adjacent in G. Suppose that we are given two independent sets I0 and Ir of G, and imagine that a token is placed on each vertex in I0 . Then, for an integer lower bound l ≥ 0, independent set reconfiguration under the TAR rule is the problem of determining whether we can transform I0 into Ir via independent sets of size at least l such that each intermediate independent set can be obtained from the previous one by either adding or removing a single token.1 In the example of Fig. 1, I0 can be transformed into Ir = I3 via the sequence I0 , I1 , I2 , I3 , but not
Data Loading...
