Source author record

Markus Sortland Dregi

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Social and Information Networks

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

On the Threshold of Intractability

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 time parameterized algorithm solving Threshold Editing in $2^{O(\surd k \log k)} + \text{poly}(n)$ time, making it one of relatively few natural problems in this complexity class on general graphs. These results are of broader interest to the field of social network analysis, where recent work of Brandes (ISAAC, 2014) posits that the minimum edit distance to a threshold graph gives a good measure of consistency for node centralities. Finally, we show that all our positive results extend to the related problem of Chain Editing, as well as the completion and deletion variants of both problems.

preprint2014arXiv

On the Computational Complexity of Vertex Integrity and Component Order Connectivity

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 most $p^3$ vertices. Result (1) refutes a conjecture by Ray and Deogun and answers an open question by Ray et al. It also complements a result by Kratsch et al., stating that the unweighted version of the problem can be solved in polynomial time on co-comparability graphs of bounded dimension, provided that an intersection model of the input graph is given as part of the input. An instance of the Weighted Component Order Connectivity (wCOC) problem consists of an $n$ -vertex graph $G$ , a weight function $w:V(G)\to \mathbb{N}$ , and two integers $k$ and $l$ , and the task is to decide if there exists a set $X\subseteq V(G)$ such that the weight of $X$ is at most $k$ and the weight of a heaviest component of $G-X$ is at most $l$ . In some sense, the wCOC problem can be seen as a refined version of the wVI problem. We prove, among other results, that: (4) wCOC can be solved in $O(\min\{k,l\}\cdot n^3)$ time on interval graphs, while the unweighted version can be solved in $O(n^2)$ time on this graph class; (5) wCOC is W[1]-hard on split graphs when parameterized by $k$ or by $l$ ; (6) wCOC can be solved in $2^{O(k\log l)} n$ time; (7) wCOC admits a kernel with at most $kl(k+l)+k$ vertices. We also show that result (6) is essentially tight by proving that wCOC cannot be solved in $2^{o(k \log l)}n^{O(1)}$ time, unless the ETH fails.

preprint2014arXiv

Parameterized Complexity of Bandwidth on Trees

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 algorithm for {\sc Bandwidth} with running time $f(b)n^{o(b)}$ would violate the Exponential Time Hypothesis, even if the input graphs are restricted to be trees of pathwidth at most two. Our lower bound shows that the classical $2^{O(b)}n^{b+1}$ time algorithm by Saxe [SIAM Journal on Algebraic and Discrete Methods, 1980] is essentially optimal. Our second result is a polynomial time algorithm that given a tree $T$ and integer $b$ , either correctly concludes that the bandwidth of $T$ is more than $b$ or finds a layout of $T$ of bandwidth at most $b^{O(b)}$ . This is the first parameterized approximation algorithm for the bandwidth of trees.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.