Tight Lower Bounds for Problems Parameterized by Rank-width
2025-05-06
0
0
1.02MB
19 页
10玖币
侵权投诉
Tight Lower Bounds for Problems Parameterized
by Rank-width
Benjamin Bergougnoux !
University of Warsaw, Poland
Tuukka Korhonen !
University of Bergen, Norway
Jesper Nederlof !
Utrecht University, The Netherlands
Abstract
We show that there is no 2
o(k2)nO(1)
time algorithm for Independent Set on
n
-vertex graphs with
rank-width
k
, unless the Exponential Time Hypothesis (ETH) fails. Our lower bound matches the
2
O(k2)nO(1)
time algorithm given by Bui-Xuan, Telle, and Vatshelle [Discret. Appl. Math., 2010]
and it answers the open question of Bergougnoux and Kanté [SIAM J. Discret. Math., 2021]. We
also show that the known 2
O(k2)nO(1)
time algorithms for Weighted Dominating Set,Maximum
Induced Matching and Feedback Vertex Set parameterized by rank-width
k
are optimal
assuming ETH. Our results are the first tight ETH lower bounds parameterized by rank-width that
do not follow directly from lower bounds for n-vertex graphs.
2012 ACM Subject Classification
Theory of computation
→
Parameterized complexity and exact
algorithms
Keywords and phrases
rank-width, exponential time hypothesis, Boolean-width, parameterized
algorithms, independent set, dominating set, maximum induced matching, feedback vertex set
Funding
Tuukka Korhonen: Supported by the Research Council of Norway via the project BWCA
(grant no. 314528).
Jesper Nederlof : Supported by the project CRACKNP that has received funding from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and innovation pro-
gramme (grant agreement No 853234)
Acknowledgements
This work was initiated while the authors attended the “2022 Advances in
Parameterized Graph Algorithms” workshop.
1 Introduction
Decompositions of graphs and their associated width parameters are a popular approach for
solving NP-hard graphs problems. Several fundamental graph problems, like Independent
Set, are known to be fixed-parameter tractable parameterized by width parameters like
the treewidth (
tw
) of the input graph [
1
]. While treewidth is the most prominent width
parameter, it has limited applicability as it can be bounded only for sparse graphs. To
capture the tractability of problems on structured dense graph classes, like cographs and
distance-hereditary graphs, the parameter clique-width (
cw
) was introduced by Courcelle,
Engelfriet, and Rozenberg [
9
]. Every graph with treewidth
tw
has clique-width
cw ≤O
(2
tw
),
and for example complete graphs have unbounded treewidth but constant clique-width. Many
fixed-parameter tractability results parameterized by treewidth generalize to parameterization
by clique-width [
10
], and in particular Independent Set can be solved in time 2
cwnO(1)
given a decomposition witnessing clique-width at most cw.
The width parameter rank-width (
rw
) was introduced by Oum and Seymour [
29
] in order
to obtain a fixed-parameter approximation algorithm for computing the clique-width. In
arXiv:2210.02117v2 [cs.DS] 8 Dec 2022
2 Tight Lower Bounds for Problems Parameterized by Rank-width
particular, they showed that
rw ≤cw ≤
2
rw+1 −
1and rank-width can be 3-approximated
in time 8
rwnO(1)
, implying an exponential 2
O(cw)
-approximation for clique-width within the
same time complexity. Even though multiple improvements for computing rank-width have
been given [
17
,
21
,
24
,
27
], the only known way to approximate clique-width remains via
computing rank-width.
In the past decade, the focus of the study of algorithms on graph decompositions has
shifted from complexity classification into establishing fine-grained bounds on the time
complexity as a function of the parameter [
4
,
5
,
11
,
12
,
15
,
16
,
20
,
23
,
25
,
26
,
28
], under
either the Exponential Time Hypothesis (ETH) or the Strong Exponential Time Hypothesis
(SETH) [
22
]. For example, Lokshtanov, Marx, and Saurabh [
26
] showed that assuming SETH,
Independent Set cannot be solved in time (2
−ε
)
pwnO(1)
parameterized by path-width
(
pw
)for any constant
ε >
0, which also translates into a tight lower bound of (2
−ε
)
cwnO(1)
parameterized by clique-width because of the relation
cw ≤pw
+ 2 [
14
]. Lampis [
25
] showed
that for every constant
k≥
3, the optimal time complexity of
k
-coloring parameterized by
clique-width is (2k−2)cwnO(1) assuming SETH.
Even though fine-grained lower bounds parameterized by clique-width have been intens-
ively studied [
4
,
5
,
15
,
16
,
25
], less attention has been given to fine-grained lower bounds
parameterized by rank-width. As the only known way to compute clique-width is via com-
puting rank-width and using the constructive version of the inequalities
rw ≤cw ≤
2
rw+1 −
1,
it could be argued that fine-grained bounds parameterized by rank-width have more signific-
ance than bounds parameterized by clique-width: In the end, the only known way to use
clique-width in its full generality is to actually use rank-width.
The lack of fine-grained lower bounds for parameterizations by rank-width in the literature
could be explained by the fact that the best known upper bounds appear to require more
complicated arguments than for other width parameters. In particular, while the translation
to clique-width or a straightforward dynamic programming leads to a double-exponential
2
2O(rw)nO(1)
time algorithm for Independent Set parameterized by rank-width, Bui-Xuan,
Telle, and Vatshelle showed in 2010 that surprisingly this is not optimal, giving a 2
O(rw2)nO(1)
time algorithm by exploiting the algebraic properties of rank-width [
6
]. It was asked by
Bergougnoux and Kanté [
3
] whether this algorithm could be shown to be optimal assuming
ETH, and by Vatshelle [30] whether a 2O(rw)nO(1) time algorithm exists.
In this paper, we show that assuming ETH, the 2
O(rw2)nO(1)
time algorithm for Inde-
pendent Set by Bui-Xuan, Telle, and Vatshelle is optimal. We show in fact a slightly more
general result, using parameterization by linear rank-width (
lrw
), which is a path-like version
of rank-width whose value is at least the rank-width, i.e., rw ≤lrw.
▶Theorem 1.1.
Unless ETH fails, there is no 2
o(lrw2)nO(1)
time algorithm for Independent
Set, where lrw is the linear rank-width of the input graphs.
Unlike for the fine-grained lower bounds parameterized by clique-width, for our result
the matching upper bound holds even without the assumption that the decomposition is
given because rank-width can be 3-approximated in time O(8rwn4)[27].
Theorem 1.1 is the first ETH-tight lower bound parameterized by rank-width that does
not follow directly from a lower bound for
n
-vertex graphs and the relation
rw ≤n
. Tight
bounds of the latter type are known for the problems of finding a largest induced subgraph
with odd vertex degrees and for partitioning a graph into a constant number of such induced
subgraphs. In particular, these problems admit 2
O(rw)nO(1)
time algorithms but cannot be
solved in time 2o(n)unless ETH fails [2].
Algorithms with time complexity 2
O(rw2)nO(1)
were given for Dominating Set and
Maximum Induced Matching by Bui-Xuan, Telle, and Vatshelle [
6
,
8
] and for Feedback
B. Bergougnoux, T. Korhonen and J. Nederlof 3
Vertex Set by Ganian and Hlinený [
18
]. We extend our lower bound construction to show
that these algorithms for Maximum Induced Matching and Feedback Vertex Set and
a weighted variant of the algorithm for Dominating Set are optimal assuming ETH.
▶Theorem 1.2. Unless ETH fails, there is no 2o(lrw2)nO(1) time algorithm for Weighted
Dominating Set,Maximum Induced Matching, or Feedback Vertex Set, where
lrw
is the linear rank-width of the input graphs.
Boolean-width.
Boolean-width (
boolw
) is a width-parameter introduced by Bui-Xuan, Telle,
and Vatshelle [
7
]. It is defined on branch decompositions over the vertex set
V
(
G
)with the cut
function
boolw
(
A, B
) =
log2|{N
(
X
)
∩B
:
X⊆A}|
, which naturally leads to algorithms with
time complexity 2
O(boolw)nO(1)
for local problems when a branch decomposition with Boolean-
width
boolw
is given. Bui-Xuan, Telle, and Vatshelle proved that
log2rw ⩽boolw ⩽O
(
rw2
)
and asked as an open question whether the upper bound
boolw ⩽O
(
rw2
)is tight [
7
]. Since
Independent Set can be solved in time 2
O(boolw)nO(1)
given a branch decomposition with
Boolean-width
boolw
, Theorem 1.1 gives evidence that there are graphs whose Boolean-width
is quadratic in rank-width. We show that indeed a small variant of a construction used
for Theorem 1.1 can be used to give a quadratic separation between Boolean-width and
rank-width, answering the question of Bui-Xuan, Telle, and Vatshelle.
▶Theorem 1.3.
There are graphs with rank-width
k
and Boolean-width Ω(
k2
)for arbitrarily
large k.
Our Method.
We briefly describe our main technical ideas for Theorem 1.1, as the other
ideas are similar.
Our starting point is the 2
O(rw2)nO(1)
time algorithm for Independent Set from [
6
].
Intuitively, the algorithm can be thought of as normal dynamic programming over tree
decompositions where we have table entries for each subset of a bag of the tree-decomposition
(which is a separator in the graph). The twist however is that the size of the separator
may be large, but instead we are only guaranteed that the rank (over
F2
) of the incidence
matrix of the cut between the separator and the remainder of the graph is small. The crucial
observation from [
6
] is that we do not need to know the exact subset of the separator of
vertices selected in the independent set, but only its set of neighbors across the cut, and that
such a neighborhood can be described by a (row- or column-) subspace of the mentioned
incidence matrix. Since there are only 2O(rw2)such subspaces, the runtime follows.
To turn this encoding idea into a reduction from 3-CNF-SAT to Independent Set on
graphs of rank-width
rw
(and get an ETH-tight lower bound), we first show this description
cannot be further shortened: Two vertex sets of the separator that describe different subspaces
in fact will have different sets of neighbors accross the cut. This allows us to design a “copy
gadget”: Once locally a certain vertex subset is chosen to be in the independent set, this is
has to be copied in various places throughout the graph (such that we can check a clause of
the 3-CNF per one such location). Furthermore, there is a simple inductive construction of
subspaces that enables us to directly encode assignments of Ω(
rw2
)variables of an 3-CNF
formula into a subspace of Frw
2. This allows us to get a tight bound.
Organization.
The rest of this paper is organized as follows. In Section 2 we set up notation.
In Section 3 we present structural results on the maximal unique cut with rank-width
k
(that we call “the universal k-rank cut”). Subsequently, Section 4 builds upon these results
to prove Theorem 1.1. In Section 5 we prove the lower bounds for Maximum Induced
4 Tight Lower Bounds for Problems Parameterized by Rank-width
Matching and Feedback Vertex Set. We prove the lower bound for Weighted
Dominating Set in Section 6 and we prove Theorem 1.3 in Section 7. We provide a brief
conclusion in Section 8.
2 Notation
Given two integers
i, j
such that 1
⩽i⩽j
, we denote by [
i, j
]the set of integer
{i, i
+1
, . . . , j}
and by [
i
]the set
{
1
,
2
, . . . , i}
. The size of a set
V
is denoted by
|V|
and its power set is
denoted by 2V.
Graphs.
Our graph terminology is standard and we refer to [
13
]. The vertex set of a graph
G
is denoted by
V
(
G
)and its edge set by
E
(
G
). For every vertex set
X⊆V
(
G
), when
the underlying graph is clear from context, we denote by
X
the set
V
(
G
)
\X
. An edge
between two vertices
x
and
y
is denoted by
xy
or
yx
. The set of vertices that are adjacent
to
x
is denoted by
NG
(
x
). For a set
U⊆V
(
G
), we define
NG
(
U
) :=
Sx∈UNG
(
x
)
\U
. If the
underlying graph is clear, then we may remove
G
from the subscript. Two distinct vertices
u, v ∈V
(
G
)are twins if
N
(
v
)
\ {u}
=
N
(
u
)
\ {v}
. They are true twins if
uv ∈E
(
G
)and
false twins if uv /∈E(G).
The subgraph of
G
induced by a subset
X
of its vertex set is denoted by
G
[
X
]. For two
disjoint subsets
X
and
Y
of
V
(
G
), we denote by
G
[
X, Y
]the bipartite graph with vertex set
X∪Yand edge set {xy ∈E(G) : x∈Xand y∈Y}.
Problem Statements.
An independent set is a set of vertices that induces an edgeless
graph. A matching is a set of edges having no common endpoint and an induced matching is
a matching
M
where every pair of edges of
M
do not have a common adjacent edge in
G
.
Given a graph, the problems Independent Set and Maximum Induced Matching ask
for respectively an independent set and an induced matching of maximum size.
Afeedback vertex set is the complement of a set of vertices inducing a forest (i.e. acyclic
graph). A set
D⊆V
(
G
)dominates a set
U⊆V
(
G
)if every vertex in
U
is either in
D
or is
adjacent to a vertex in
D
. A dominating set of
G
is a set that dominates
V
(
G
). Given a
graph, the problems Dominating Set and Feedback Vertex Set ask respectively for a
dominating set and a feedback vertex set of minimum size.
Given a graph
G
with a weight function
w
:
V
(
G
)
→N
, the problem Weighted
Independent Set (resp. Weighted Dominating Set) asks for an independent set of
maximum weight (resp. dominating set of minimum weight), where the weight of a set
X⊆V(G)is Px∈Xw(x).
Width parameters.
Let
V
be a finite set with
|V| ≥
3, and
f
a function
f
: 2
V→Z≥0
so
that
f
(
∅
) = 0 and
f
(
A
) =
f
(
A
)for all
A⊆V
. A branch decomposition of
f
is a tree whose
all internal nodes have degree 3 and whose leaves are bijectively mapped to
V
. Observe that
every edge of a branch decomposition of
f
corresponds to a bipartition (
A, A
)of
V
given by
the leaves on different sides of the edge. The width of the decomposition is the maximum
value of
f
(
A
)over the bipartitions (
A, A
)corresponding to the edges, and the branch-width
of
f
is the minimum width of a branch decomposition of
f
. The width of a permutation
σ
of
V
is the maximum value of
f
(
A
)over prefixes
A
of the permutation. The linear branch-width
of
f
is the minimum width of a permutation of
V
. Notice that the branch-width of
f
is
always at most the linear branch-width of
f
, in particular linear branch-width corresponds
to a restriction of branch-width where we demand the tree to be a caterpillar.
摘要：
展开>>
收起<<
TightLowerBoundsforProblemsParameterizedbyRank-widthBenjaminBergougnoux!UniversityofWarsaw,PolandTuukkaKorhonen!UniversityofBergen,NorwayJesperNederlof!UtrechtUniversity,TheNetherlandsAbstractWeshowthatthereisno2o(k2)nO(1)timealgorithmforIndependentSetonn-vertexgraphswithrank-widthk,unlesstheExpo...
声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
相关推荐
-
Michael Moorcock - Elric 6 - StormbringerVIP免费
2024-12-08 6 -
Michael Crichton - PreyVIP免费
2024-12-08 11 -
Mercedes Lackey - WintermoonVIP免费
2024-12-08 7 -
Mercedes Lackey - SE 1- Born To RunVIP免费
2024-12-08 8 -
Mercedes Lackey - Heralds of Valdemar 1 - Arrows Of The QueeVIP免费
2024-12-08 10 -
Melville, Herman - TypeeVIP免费
2024-12-08 15 -
MaryJanice Davidson - [Betsy 5] - Undead and Unpopular (v1.0)VIP免费
2024-12-08 18 -
Marion Zimmer Bradley - Darkover - The Heirs of HammerfellVIP免费
2024-12-08 19 -
MacDonnell, J E - 096 - Execute!VIP免费
2024-12-08 15 -
Lovecraft, H P - The Dream Quest Of Unknown KadadthVIP免费
2024-12-08 21
分类：图书资源
价格：10玖币
属性：19 页
大小：1.02MB
格式：PDF
时间：2025-05-06
作者详情
-
VLC-BERT Visual Question Answering with Contextualized Commonsense Knowledge Sahithya Ravi12Aditya Chinchure12Leonid Sigal12Renjie Liao1Vered Shwartz1210 玖币0人下载
-
Volatility density estimation by multiplicative deconvolution Sergio Brenner Miguela aInstitut f ur angewandte Mathematik und Interdisciplinary Center for Scientic Computing10 玖币0人下载
相关内容
-
2015年6月英语四级真题答案及解析（卷二）
分类：外语学习
时间：2025-05-02
标签：无
格式：PDF
价格：5.8 玖币
-
2015年6月英语四级真题答案及解析（卷三）
分类：外语学习
时间：2025-05-02
标签：无
格式：PDF
价格：5.8 玖币
-
2016年12月六级（第二套）真题
分类：外语学习
时间：2025-05-02
标签：无
格式：PDF
价格：5.8 玖币
-
2016年12月六级（第三套）真题
分类：外语学习
时间：2025-05-02
标签：无
格式：PDF
价格：5.8 玖币
-
2016年12月六级（第一套）真题
分类：外语学习
时间：2025-05-02
标签：无
格式：PDF
价格：5.8 玖币
渝公网安备50010702506394
