It is known that problems like
Vertex Cover
,
Feedback Vertex Set
and
Odd Cycle Transversal
are polynomial time solvable in the class of chordal graphs. We consider these problems in a graph that has ...at most
k
vertices whose deletion results in a chordal graph when parameterized by
k
. While this investigation fits naturally into the recent trend of what is called ‘structural parameterizations’, here we assume that the deletion set is not given. One method to solve them is to compute a
k
-sized or an approximate (
f
(
k
) sized, for a function
f
) chordal vertex deletion set and then use the structural properties of the graph to design an algorithm. This method leads to at least
k
O
(
k
)
n
O
(
1
)
running time when we use the known parameterized or approximation algorithms for finding a
k
-sized chordal deletion set on an
n
vertex graph. In this work, we design
2
O
(
k
)
n
O
(
1
)
time algorithms for these problems. Our algorithms do not compute a chordal vertex deletion set (or even an approximate solution). Instead, we construct a tree decomposition of the given graph in
2
O
(
k
)
n
O
(
1
)
time where each bag is a union of four cliques and
O
(
k
)
vertices. We then apply standard dynamic programming algorithms over this special tree decomposition. This special tree decomposition can be of independent interest. Our algorithms are, what are sometimes called
permissive
in the sense that given an integer
k
, they detect whether the graph has no chordal vertex deletion set of size at most
k
or output the special tree decomposition and solve the problem. We also show lower bounds for the problems we deal with under the strong exponential time hypothesis.
Set Cover
is one of the well-known classical NP-hard problems. We study the
conflict-free
version of the
Set Cover
problem. Here we have a universe
U
, a family
F
of subsets of
U
and a graph
G
F
on ...the vertex set
F
and we look for a subfamily
F
′
⊆
F
of minimum size that covers
U
and also forms an independent set in
G
F
. We study conflict-free
Set Cover
in parameterized complexity by restricting the focus to the variants where
Set Cover
is fixed parameter tractable (FPT). We give upper bounds and lower bounds for the running time of conflict-free version of
Set Cover
with and without duplicate sets along with restrictions to the graph classes of
G
F
. For example, when pairs of sets in
F
intersect in at most one element, for a solution of size
k
, we give
an
f
(
k
)
|
F
|
o
(
k
)
lower bound for any computable function
f
assuming ETH even if
G
F
is bipartite, but
an
O
∗
(
3
k
2
)
FPT algorithm (
O
∗
notation ignores polynomial factors of input) when
G
F
is chordal.
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
+
ℓ
.
We consider the complexity of recognizing
k
-clique-extendible graphs (
k
-C-E graphs) introduced by Spinrad (Efficient Graph Representations, AMS 2003), which are generalizations of comparability ...graphs. A graph is
k
-clique-extendible if there is an ordering of the vertices such that whenever two overlapping
k
-cliques
A
and
B
have
k
-
1
common vertices, and these common vertices appear between the two vertices
a
,
b
∈
(
A
\
B
)
∪
(
B
\
A
)
in the ordering, there is an edge between
a
and
b
, implying that
A
∪
B
is a
(
k
+
1
)
-clique. Such an ordering is said to be a
k
-C-E ordering. These graphs arise in applications related to modelling preference relations. Recently, it has been shown that a maximum clique in such a graph can be found in
n
O
(
k
)
time Hamburger et al. 2017 when the ordering is given. When
k
is 2, such graphs are precisely the well-known class of comparability graphs and when
k
is 3 they are called triangle-extendible graphs. It has been shown that triangle-extendible graphs appear as induced subgraphs of visibility graphs of simple polygons, and the complexity of recognizing them has been mentioned as an open problem in the literature. While comparability graphs (i.e. 2-C-E graphs) can be recognized in polynomial time, we show that recognizing
k
-C-E graphs is NP-hard for any fixed
k
≥
3
and
co-NP
-hard when
k
is part of the input. While our NP-hardness reduction for
k
≥
4
is from the betweenness problem, for
k
=
3
, our reduction is an intricate one from the 3-colouring problem. We also show that the problems of determining whether a given ordering of the vertices of a graph is a
k
-C-E ordering, and that of finding a maximum clique in a
k
-C-E graph, given a
k
-C-E ordering, are hard for the parameterized complexity classes
co-W1
and
W1
respectively, when parameterized by
k
. However we show that the former is fixed-parameter tractable when parameterized by the treewidth of the graph. We also show that the dual parameterizations of all the problems that we study are fixed parameter tractable.
We develop new approximation algorithms for classical graph and set problems in the RAM model under space constraints. As one of our main results, we devise an algorithm for
d
-
H
I
T
T
I
N
G
S
E
T
...that runs in time
n
O
(
d
2
+
(
d
/
ϵ
)
)
, uses
O
(
(
d
2
+
(
d
/
ϵ
)
)
log
n
)
bits of space, and achieves an approximation ratio of
O
(
(
d
/
ϵ
)
n
ϵ
)
for any positive
ϵ
≤
1
and any
d
∈
N
. In particular, this yields a factor-
O
(
log
n
)
approximation algorithm which runs in time
n
O
(
log
n
)
and uses
O
(
log
2
n
)
bits of space (for constant
d
). As a corollary, we obtain similar bounds for
V
E
R
T
E
X
C
O
V
E
R
and several graph deletion problems. For bounded-multiplicity problem instances, one can do better. We devise a factor-2 approximation algorithm for
V
E
R
T
E
X
C
O
V
E
R
on graphs with maximum degree
Δ
, and an algorithm for computing maximal independent sets, both of which run in time
n
O
(
Δ
)
and use
O
(
Δ
log
n
)
bits of space. For the more general
d
-
H
I
T
T
I
N
G
S
E
T
problem, we devise a factor-
d
approximation algorithm which runs in time
n
O
(
d
δ
2
)
and uses
O
(
d
δ
2
log
n
)
bits of space on set families where each element appears in at most
δ
sets. For
I
N
D
E
P
E
N
D
E
N
T
S
E
T
restricted to graphs with average degree
d
, we give a factor-(2
d
) approximation algorithm which runs in polynomial time and uses
O
(
log
n
)
bits of space. We also devise a factor-
O
(
d
2
)
approximation algorithm for
D
O
M
I
N
A
T
I
N
G
S
E
T
on
d
-degenerate graphs which runs in time
n
O
(
log
n
)
and uses
O
(
log
2
n
)
bits of space. For
d
-regular graphs, we show how a known randomized factor-
O
(
log
d
)
approximation algorithm can be derandomized to run in time
n
O
(
1
)
and use
O
(
log
n
)
bits of space. Our results use a combination of ideas from the theory of kernelization, distributed algorithms and randomized algorithms.
We consider space efficient implementations of some classical applications of DFS including the problem of testing biconnectivity and 2-edge connectivity, finding cut vertices and cut edges, ...computing chain decomposition and st-numbering of a given undirected graph G on n vertices and m edges. Classical algorithms for them typically use DFS and some Ω(lgn) bits1of information at each vertex. Building on a recent O(n)-bits implementation of DFS due to Elmasry et al. (STACS 2015) we provide O(n)-bit implementations for all these applications of DFS. Our algorithms take O(mlgcnlglgn) time for some small constant c (where c≤2). Central to our implementation is a succinct representation of the DFS tree and a space efficient partitioning of the DFS tree into connected subtrees, which maybe of independent interest for designing other space efficient graph algorithms.
•We consider space efficient implementations of some classical applications of DFS including testing biconnectivity and/or 2-edge connectivity, producing a sparse spanning biconnected subgraph of a given biconnected graph, computing chain decomposition and st-numbering, and computing topological sort and strongly connected components etc.•Classical linear time algorithms for these problems typically use Ω(nlgn) bits. We improve the space bound by providing O(n)-bit implementations for all these applications. Our algorithms take O(mlgcnlglgn) time for some small constant c (where c≤2).•Central to our implementation is a succinct representation of the DFS tree and a space efficient partitioning of the DFS tree into connected subtrees, which could find possible other applications for designing other space efficient graph algorithms.
In parameterized complexity, it is well-known that a parameterized problem is fixed-parameter tractable if and only if it has a kernel—an instance equivalent to the input instance, whose size is just ...a function of the parameter. The size of the kernel can be exponential or worse, resulting in a quest for fixed-parameter tractable problems with polynomial-sized kernels. The developments in machinery (showing lower bounds for the sizes of the kernels) have led researchers to question what are the asymptotically optimum sizes for the kernels of fixed-parameter tractable problems. In this article, we surveyed a tool called expansion lemma that helps in reducing the size of the kernel. Its early origin was in the form of crown decomposition, i.e., to obtain the linear kernel for the Vertex Cover problem; the specific lemma was identified as the tool behind the optimal O(k2) kernel for the undirected feedback vertex set problem. Since then, several variations and extensions of the tool have been discovered. We surveyed them along with their applications in this article.
•Changes in thermal stresses quantified by SkyHelios simulations.•TMRT reduction by trees is higher, with larger size and at lower wind speeds.•Cumulative mean rise in TMRT is 1.9 °C at wind speed ...0.5 m/s due to de-vegetation.•TMRT/PET rise up to 18.3 /12.9 °C at erstwhile tree- shades at wind speed 0.5 m/s.•Unshaded areas closer to the trees are hotter than the distant/treeless areas.
This study attempts to quantify thermal-stress abatement by tress, using the example of Bihar Museum at Patna, Bihar, India, where around 200 trees, though known as great solar heat attenuators, were felled to accommodate the newly-built museum. The study, with a focus on sensitivity analysis, compares two tree scenarios, at two input wind-speeds and seeks to identify the individual/synergetic effects of physical attributes of tree-morphology, background wind, etc., on cooling by trees, through simulations, using freely available model SkyHelios Pro. SkyHelios allows for the spatial/temporal analysis of the thermal changes at a point of time and space. The ‘area-mean’ rise in mean radiant temperature (TMRT) is found 1.9 °C and in physiological equivalent temperature (PET) 1.1 °C, by 28 % trees-removal (area-wise), at noon at 0.5 m/s input wind-speed. TMRT reduction by trees is found directly related to their canopy-size/cluster-density, and inversely to background wind-speed. PET reduction is directly related to the canopy-size/ cluster-density at lower wind-speeds and inversely at higher. The study is limited to daytime (noon) hours. Based on the detailed outputs from SkyHelios simulations, recommendations for passive cooling of urban outdoors in terms of tree size, layout-density, built-up morphology, and background wind-speed are formulated.
We investigate a generalization of the classical Feedback Vertex Set (FVS) problem from the point of view of parameterized algorithms. Independent Feedback Vertex Set (IFVS) is the “independent” ...variant of the FVS problem and is defined as follows: given a graph G and an integer k, decide whether there exists F⊆V(G), |F|≤k, such that GV(G)∖F is a forest and GF is an independent set; the parameter is k. Note that the similarly parameterized version of the FVS problem–where there is no restriction on the graph GF–has been extensively studied in the literature. The connected variant CFVS–where GF is required to be connected–has received some attention as well. The FVS problem easily reduces to the IFVS problem in a manner that preserves the solution size, and so any algorithmic result for IFVS directly carries over to FVS. We show that IFVS can be solved in O(5knO(1)) time, where n is the number of vertices in the input graph G, and obtain a cubic (O(k3)) kernel for the problem. Note the contrast with the CFVS problem, which does not admit a polynomial kernel unless CoNP⊆NP/Poly.
Background: There have been limited reports about brain activity during cardiac arrest. Here we report 4 patients presenting with seizure who had cardiac arrest leading to their deaths while being on ...continuous video-EEG (cVEEG) monitoring and one-lead cardiac telemetry. Purpose: We illustrate characteristic stepwise EEG and EKG changes in these critically ill patients prior to their death. Research Design/Study Sample: All patients showed progressive broad spectrum of cardiac arrhythmias at or before the beginning of EEG suppression while there were no such changes seen in a control group of 4 randomly selected patients without cardiac arrest who had seizure on presentation and underwent cVEEG monitoring. Data Collection and Results: There was a progressive decline in EEG potentials associated with decreasing heart rate starting from the posterior region, more pronounced on the left, progressing to complete unilateral deactivation of the left fronto-central head regions while the right-sided networks became hyperactive before bilateral deactivation by the time of asystole. Conclusions: This case series provides a rare opportunity to compare EEG and EKG changes in patients who died while being on continuous EEG and EKG monitoring from hours to minutes prior to cardiac arrest and death.
PDF
