A set of vertices in a graph is c-colorable if the subgraph induced by the set has a proper c-coloring. In this paper, we study the problem of finding a step-by-step transformation (called a ...reconfiguration sequence) between two c-colorable sets in the same graph. This problem generalizes the well-studied Independent Set Reconfiguration problem. As the first step toward a systematic understanding of the complexity of this general problem, we study the problem on classes of perfect graphs. We first focus on interval graphs and give a combinatorial characterization of the distance between two c-colorable sets. This gives a linear-time algorithm for finding an actual shortest reconfiguration sequence for interval graphs. Since interval graphs are exactly the graphs that are simultaneously chordal and co-comparability, we then complement the positive result by showing that even deciding reachability is PSPACE-complete for chordal graphs and for co-comparability graphs. The hardness for chordal graphs holds even for split graphs. We also consider the case where c is a fixed constant and show that in such a case the reachability problem is polynomial-time solvable for split graphs but still PSPACE-complete for co-comparability graphs. The complexity of this case for chordal graphs remains unsettled. As by-products, our positive results give the first polynomial-time solvable cases (split graphs and interval graphs) for Feedback Vertex Set Reconfiguration.
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 investigate the complexity of the
Maximum Happy Set
problem on subclasses of co-comparability graphs. For a graph
G
and its vertex subset
S
, a vertex
v
∈
S
is happy if all
v
’s ...neighbors in
G
are contained in
S
. Given a graph
G
and a non-negative integer
k
,
Maximum Happy Set
is the problem of finding a vertex subset
S
of
G
such that
|
S
|
=
k
and the number of happy vertices in
S
is maximized. In this paper, we first show that
Maximum Happy Set
is NP-hard even for co-bipartite graphs. We then give an algorithm for
n
-vertex interval graphs whose running time is
O
(
n
2
+
k
3
n
)
; this improves the best known running time
O
(
k
n
8
)
for interval graphs. We also design algorithms for
n
-vertex permutation graphs and
d
-trapezoid graphs which run in
O
(
n
2
+
k
3
n
)
and
O
(
n
2
+
d
2
(
k
+
1
)
3
d
n
)
time, respectively. These algorithmic results provide a nice contrast to the fact that
Maximum Happy Set
remains NP-hard for chordal graphs, comparability graphs, and co-comparability graphs.
•We analyze the approximability of the independent feedback vertex set problem.•The problem is hard to approximate on planar bipartite graphs.•There is an efficient approximation algorithm for ...bipartite graphs of bounded maximum degree.•The problem is solvable in polynomial time if a given bipartite graph is of maximum degree three.
Given an undirected graph G with n vertices, the independent feedback vertex set problem is to find a vertex subset F of G with the minimum number of vertices such that F is both an independent set and a feedback vertex set of G, if it exists. This problem is known to be NP-hard for bipartite planar graphs of maximum degree four. In this paper, we study the approximability of the problem. We first show that, for any fixed ε>0, unless P=NP, there exists no polynomial-time n1−ε-approximation algorithm even for bipartite planar graphs. We then give an α(Δ−1)/2-approximation algorithm for bipartite graphs G of maximum degree Δ, which runs in t(α,G)+O(Δn) time, under the assumption that there is an α-approximation algorithm for the original feedback vertex set problem on bipartite graphs which runs in t(α,G) time. This algorithmic result also yields a polynomial-time (exact) algorithm for the independent feedback vertex set problem on bipartite graphs of maximum degree three.
The multi-service center problem is a variant of facility location problems. In the problem, we consider locating p facilities on a graph, each of which provides distinct service required by all ...vertices. Each vertex incurs the cost determined by the sum of the weighted distances to the p facilities. The aim of the problem is to minimize the maximum cost among all vertices. This problem is known to be NP-hard for general graphs, while it is solvable in polynomial time when p is a fixed constant. In this paper, we give sharp analyses for the complexity of the problem from the viewpoint of graph classes and weights on vertices. We first propose a polynomial-time algorithm for trees when p is a part of input. In contrast, we prove that the problem becomes strongly NP-hard even for cycles. We also show that when vertices are allowed to have negative weights, the problem becomes NP-hard for paths of only three vertices and strongly NP-hard for stars.
We investigate the complexity of finding a transformation from a given spanning tree in a graph to another given spanning tree in the same graph via a sequence of edge flips. The exchange property of ...the matroid bases immediately yields that such a transformation always exists if we have no constraints on spanning trees. In this paper, we wish to find a transformation which passes through only spanning trees satisfying some constraint. Our focus is bounding either the maximum degree or the diameter of spanning trees, and we give the following results. The problem with a lower bound on maximum degree is solvable in polynomial time, while the problem with an upper bound on maximum degree is PSPACE-complete. The problem with a lower bound on diameter is NP-hard, while the problem with an upper bound on diameter is solvable in polynomial time.
Background
Ablation index (AI) linearly correlates with lesion depth and may yield better therapeutic performance in pulmonary vein isolation (PVI) when tailored to a patient's wall thickness (WT) in ...the left atrium (LA).
Methods and results
First study: In paroxysmal atrial fibrillation patients (PAF; n = 20), the average LA WT (mm) in each anatomical segment for PVI was measured by intracardiac echocardiography (ICE) placed in the LA; the optimal AI for creating 1‐mm transmural lesion (AI/mm) was calculated. Second study: PAF (n = 80) patients were randomly assigned either to a force‐time integral protocol (FTI; 400 g·s, n = 40) or a tailored‐AI protocol (TAI; n = 40). In TAI, the LA WT in each segment was individually measured by ICE before starting ablation; a target AI was adjusted according to the individual WT in each segment (AI/mm × WT). The acute procedure outcomes and the 1‐year AF‐recurrence rate were compared between FTI and TAI. TAI had higher success rate of first‐pass isolation (88% vs. 65%) and had lower incidence of residual PV‐potentials/conduction‐gaps after a circular ablation than FTI (15% vs. 45%). The procedure time to complete PVI decreased in TAI compared to FTI (52 vs. 83 min), being attributed to the increased radiofrequency power and the decreased radiofrequency application time in each point in TAI. TAI had a lower 1‐year AF‐recurrence rate than FTI.
Conclusion
TAI increased acute procedure success, decreased time for PVI, and reduced the 1‐year AF‐recurrence rate, compared to FTI. Understanding the precise ablation target and tailoring AI would improve the efficacy of PVI.
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.
PDF
