3
3.0

Jun 30, 2018
06/18

by
Pål Grønås Drange; Michał Pilipczuk

texts

#
eye 3

#
favorite 0

#
comment 0

We give a kernel with $O(k^7)$ vertices for Trivially Perfect Editing, the problem of adding or removing at most $k$ edges in order to make a given graph trivially perfect. This answers in affirmative an open question posed by Nastos and Gao, and by Liu et al. Our general technique implies also the existence of kernels of the same size for the related problems Trivially Perfect Completion and Trivially Perfect Deletion. Whereas for the former an $O(k^3)$ kernel was given by Guo, for the latter...

Topics: Data Structures and Algorithms, Computing Research Repository

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

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

9
9.0

Jun 28, 2018
06/18

by
Pål Grønås Drange; Felix Reidl; Fernando Sánchez Villaamil; Somnath Sikdar

texts

#
eye 9

#
favorite 0

#
comment 0

We study two clustering problems, Starforest Editing, the problem of adding and deleting edges to obtain a disjoint union of stars, and the generalization Bicluster Editing. We show that, in addition to being NP-hard, none of the problems can be solved in subexponential time unless the exponential time hypothesis fails. Misra, Panolan, and Saurabh (MFCS 2013) argue that introducing a bound on the number of connected components in the solution should not make the problem easier: In particular,...

Topics: Computing Research Repository, Data Structures and Algorithms

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

5
5.0

Jun 30, 2018
06/18

by
Pål Grønås Drange; Markus S. Dregi; Fedor V. Fomin; Stephan Kreutzer; Daniel Lokshtanov; Marcin Pilipczuk; Michał Pilipczuk; Felix Reidl; Saket Saurabh; Fernando Sánchez Villaamil; Sebastian Siebertz; Somnath Sikdar

texts

#
eye 5

#
favorite 0

#
comment 0

We prove that for every positive integer $r$ and for every graph class $\mathcal G$ of bounded expansion, the $r$-Dominating Set problem admits a linear kernel on graphs from $\mathcal G$. Moreover, when $\mathcal G$ is only assumed to be nowhere dense, then we give an almost linear kernel on $\mathcal G$ for the classic Dominating Set problem, i.e., for the case $r=1$. These results generalize a line of previous research on finding linear kernels for Dominating Set and $r$-Dominating Set....

Topics: Data Structures and Algorithms, Computing Research Repository

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