4
4.0

Jun 30, 2018
06/18

by
Markus Sortland Dregi; Daniel Lokshtanov

texts

#
eye 4

#
favorite 0

#
comment 0

The bandwidth of a $n$-vertex graph $G$ is the smallest integer $b$ such that there exists a bijective function $f : V(G) \rightarrow \{1,...,n\}$, called a layout of $G$, such that for every edge $uv \in E(G)$, $|f(u) - f(v)| \leq b$. In the {\sc Bandwidth} problem we are given as input a graph $G$ and integer $b$, and asked whether the bandwidth of $G$ is at most $b$. We present two results concerning the parameterized complexity of the {\sc Bandwidth} problem on trees. First we show that an...

Topics: Computational Complexity, Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1404.7810

6
6.0

Jun 30, 2018
06/18

by
Pål Grønås Drange; Markus Sortland Dregi; Pim van 't Hof

texts

#
eye 6

#
favorite 0

#
comment 0

The Weighted Vertex Integrity (wVI) problem takes as input an $n$-vertex graph $G$, a weight function $w:V(G)\to\mathbb{N}$, and an integer $p$. The task is to decide if there exists a set $X\subseteq V(G)$ such that the weight of $X$ plus the weight of a heaviest component of $G-X$ is at most $p$. Among other results, we prove that: (1) wVI is NP-complete on co-comparability graphs, even if each vertex has weight $1$; (2) wVI can be solved in $O(p^{p+1}n)$ time; (3) wVI admits a kernel with at...

Topics: Data Structures and Algorithms, Computing Research Repository

Source: http://arxiv.org/abs/1403.6331

7
7.0

Jun 27, 2018
06/18

by
Pål Grønås Drange; Markus Sortland Dregi; Daniel Lokshtanov; Blair D. Sullivan

texts

#
eye 7

#
favorite 0

#
comment 0

We study the computational complexity of the graph modification problems Threshold Editing and Chain Editing, adding and deleting as few edges as possible to transform the input into a threshold (or chain) graph. In this article, we show that both problems are NP-complete, resolving a conjecture by Natanzon, Shamir, and Sharan (Discrete Applied Mathematics, 113(1):109--128, 2001). On the positive side, we show the problem admits a quadratic vertex kernel. Furthermore, we give a subexponential...

Topics: Computational Complexity, Social and Information Networks, Computing Research Repository, Data...

Source: http://arxiv.org/abs/1505.00612