Reconfiguration is concerned with relationships among solutions to a problem instance, where the reconfiguration of one solution to another is a sequence of steps such that each step produces an ...intermediate feasible solution. The solution space can be represented as a reconfiguration graph, where two vertices representing solutions are adjacent if one can be formed from the other in a single step. Work in the area encompasses both structural questions (Is the reconfiguration graph connected?) and algorithmic ones (How can one find the shortest sequence of steps between two solutions?) This survey discusses techniques, results, and future directions in the area.
Polymerised ionic liquids (PILs) have unique properties such as low glass transition temperature (Tg) in spite of very high charge density. Due to these advanced points, PILs have been prepared and ...initially evaluated as ion conductive polymers. Progress of low-Tg polyelectrolytes has been previously demonstrated with polyethers having charged end(s) as a kind of PILs. Then, imidazolium-type ionic liquids (ILs) were polymerised after introducing vinyl groups onto the imidazolium cation rings. It is reasonable that the ionic conductivity of thus prepared PILs decreased due to elevation of Tg and decrease of the number of mobile small ions. Efforts were then paid to suppress drop of ionic conductivity after polymerisation. Variety of PILs has been improved to show excellent ionic conductivity, selective ion transport, and other properties. With the progress of functional ILs, some functions were also added to PILs which cannot be realised with ordinary charged polymers. In the present mini-review, we briefly introduce history of a variety of polymerised ILs and some applications of these PILs.
Display omitted
A random copolymer consisting of ethylene carbonate (EC) and ethylene oxide (EO) units with allyl side groups is synthesized as a matrix for solid polymer electrolytes (SPE). By introducing ...crosslinking structure to the copolymer, creating a polymer matrix with superior mechanical strength while maintaining good ionic conductivity is being attempted. A tensile test indicates that introduction of the crosslinking structure improves the elastic modulus and maximum stress. When a lithium bis(fluorosulfonyl)imide is added to these polymers at 80 mol%, the conductivity of the crosslinked polymer‐based electrolyte increases slightly. Vogel–Tammann–Fulcher (VTF) analysis reveals that values of the activation energy for crosslinked polymer‐based electrolytes are clearly lower than those of the starting copolymer. The changes in the constant A with increasing salt concentration are very different, but the A values at 80 mol% are almost the same. This VTF behavior suggests that the crosslinking structure has a larger effect on the increase in the carrier ions and also on the decrease in the energy for ionic conduction with increasing salt concentration.
Creating a random copolymer consisting of ethylene carbonate and ethylene oxide units with superior mechanical strength while maintaining good ionic conductivity is attempted here. A tensile test indicates that introduction of the crosslinking structure improves the elastic modulus and maximum stress. When lithium bis(fluorosulfonyl)imide is added, the conductivity of the crosslinked polymer‐based electrolyte increases slightly.
We present the first results on the parameterized complexity of reconfiguration problems, where a reconfiguration variant of an optimization problem
Q
takes as input two feasible solutions
S
and
T
...and determines if there is a sequence of reconfiguration steps, i.e. a reconfiguration sequence, that can be applied to transform
S
into
T
such that each step results in a feasible solution to
Q
. For most of the results in this paper,
S
and
T
are sets of vertices of a given graph and a reconfiguration step adds or removes a vertex. Our study is motivated by results establishing that for many
NP
-hard problems, the classical complexity of reconfiguration is
PSPACE
-complete. We address the question for several important graph properties under two natural parameterizations:
k
, a bound on the size of solutions, and
ℓ
, a bound on the length of reconfiguration sequences. Our first general result is an algorithmic paradigm, the reconfiguration kernel, used to obtain fixed-parameter tractable algorithms for reconfiguration variants of
Vertex Cover
and, more generally,
Bounded Hitting Set
and
Feedback Vertex Set
, all parameterized by
k
. In contrast, we show that reconfiguring
Unbounded Hitting Set
is
W2
-hard when parameterized by
k
+
ℓ
. We also demonstrate the
W1
-hardness of reconfiguration variants of a large class of maximization problems parameterized by
k
+
ℓ
, and of their corresponding deletion problems parameterized by
ℓ
; in doing so, we show that there exist problems in
FPT
when parameterized by
k
, but whose reconfiguration variants are
W1
-hard when parameterized by
k
+
ℓ
.
Suppose that we are given two dominating sets Ds and Dt of a graph G whose cardinalities are at most a given threshold k. Then, we are asked whether there exists a sequence of dominating sets of G ...between Ds and Dt such that each dominating set in the sequence is of cardinality at most k and can be obtained from the previous one by either adding or deleting exactly one vertex. This decision problem is known to be PSPACE-complete in general. In this paper, we study the complexity of this problem from the viewpoint of graph classes. We first prove that the problem remains PSPACE-complete even for planar graphs, bounded bandwidth graphs, split graphs, and bipartite graphs. We then give a general scheme to construct linear-time algorithms and show that the problem can be solved in linear time for cographs, forests, and interval graphs. Furthermore, for these tractable cases, we can obtain a desired sequence if it exists such that the number of additions and deletions is bounded by O(n), where n is the number of vertices in the input graph.
Suppose that we are given an independent set
I
0
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
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
. 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
I
0
. 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.
In this paper, we study covering and domination problems on directed graphs. Although undirected Vertex Cover and Edge Dominating Set are well-studied classical graph problems, the directed versions ...have not been studied much due to the lack of clear definitions.
We give natural definitions for Directedr-In (Out) Vertex Cover and Directed(p,q)-Edge Dominating Set as directed generalizations of Vertex Cover and Edge Dominating Set. For these problems, we show that (1) Directedr-In (Out) Vertex Cover and Directed(p,q)-Edge Dominating Set are NP-complete on planar directed acyclic graphs except when r=1 or (p,q)=(0,0), (2) if r≥2, Directedr-In (Out) Vertex Cover is W2-hard and clnk-inapproximable on directed acyclic graphs, (3) if either p or q is greater than 1, Directed(p,q)-Edge Dominating Set is W2-hard and clnk-inapproximable on directed acyclic graphs, (4) all problems can be solved in polynomial time on trees, and (5) Directed(0,1)-Edge ((1,0)-Edge, (1,1)-Edge) Dominating Set is fixed-parameter tractable on general graphs.
The first result implies that Directedr-Dominating Set on directed line graphs is NP-complete even if r=1.
In the Vertex Cover Reconfiguration (VCR) problem, given a graph G, positive integers k and ℓ and two vertex covers S and T of G of size at most k, we determine whether S can be transformed into T by ...a sequence of at most ℓ vertex additions or removals such that every operation results in a vertex cover of size at most k. Motivated by results establishing the W1W1 -hardness of VCR when parameterized by ℓ, we delineate the complexity of the problem restricted to various graph classes. In particular, we show that VCR remains W1W1 -hard on bipartite graphs, is NPNP -hard, but fixed-parameter tractable on (regular) graphs of bounded degree and more generally on nowhere dense graphs and is solvable in polynomial time on trees and (with some additional restrictions) on cactus graphs.
PDF
