Incremental optimization of independent sets under the reconfiguration framework

Takehiro Ito (), Haruka Mizuta (), Naomi Nishimura () and Akira Suzuki ()
Additional contact information
Takehiro Ito: Tohoku University
Haruka Mizuta: Tohoku University
Naomi Nishimura: University of Waterloo
Akira Suzuki: Tohoku University

Journal of Combinatorial Optimization, 2022, vol. 43, issue 5, No 15, 1264-1279

Abstract: Abstract Suppose that we are given an independent set $$I_0$$ I 0 of a graph G, and an integer $$l\ge 0$$ l ≥ 0 . Then, we are asked to find an independent set of G having the maximum size among independent sets that are reachable from $$I_0$$ I 0 by either adding or removing a single vertex at a time such that all intermediate independent sets are of size at least $$l$$ 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$$ d of an input graph, a lower bound $$l$$ l on the size of independent sets, and a lower bound $$s$$ s on the size of a solution reachable from $$I_0$$ I 0 . We show that the problem is fixed-parameter intractable when only one of $$d$$ d , $$l$$ l , or $$s$$ s is taken as a parameter. On the other hand, we give a fixed-parameter algorithm when parameterized by $$s+d$$ s + d ; this result implies that the problem parameterized only by $$s$$ s is fixed-parameter tractable for planar graphs, and for bounded-treewidth graphs.

Keywords: Combinatorial reconfiguration; Graph algorithms; Independent set (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00630-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:43:y:2022:i:5:d:10.1007_s10878-020-00630-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00630-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().