Source author record

Nikolaos Melissinos

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

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms

Catalog footprint

Research overview

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Digraph Coloring and Distance to Acyclicity

In $k$ -Digraph Coloring we are given a digraph and are asked to partition its vertices into at most $k$ sets, so that each set induces a DAG. This well-known problem is NP-hard, as it generalizes (undirected) $k$ -Coloring, but becomes trivial if the input digraph is acyclic. This poses the natural parameterized complexity question what happens when the input is "almost" acyclic. In this paper we study this question using parameters that measure the input's distance to acyclicity in either the directed or the undirected sense. It is already known that, for all $k\ge 2$ , $k$ -Digraph Coloring is NP-hard on digraphs of DFVS at most $k+4$ . We strengthen this result to show that, for all $k\ge 2$ , $k$ -Digraph Coloring is NP-hard for DFVS $k$ . Refining our reduction we obtain two further consequences: (i) for all $k\ge 2$ , $k$ -Digraph Coloring is NP-hard for graphs of feedback arc set (FAS) at most $k^2$ ; interestingly, this leads to a dichotomy, as we show that the problem is FPT by $k$ if FAS is at most $k^2-1$ ; (ii) $k$ -Digraph Coloring is NP-hard for graphs of DFVS $k$ , even if the maximum degree $Δ$ is at most $4k-1$ ; we show that this is also almost tight, as the problem becomes FPT for DFVS $k$ and $Δ\le 4k-3$ . We then consider parameters that measure the distance from acyclicity of the underlying graph. We show that $k$ -Digraph Coloring admits an FPT algorithm parameterized by treewidth, whose parameter dependence is $(tw!)k^{tw}$ . Then, we pose the question of whether the $tw!$ factor can be eliminated. Our main contribution in this part is to settle this question in the negative and show that our algorithm is essentially optimal, even for the much more restricted parameter treedepth and for $k=2$ . Specifically, we show that an FPT algorithm solving $2$ -Digraph Coloring with dependence $td^{o(td)}$ would contradict the ETH.

preprint2021arXiv

(In)approximability of Maximum Minimal FVS

We study the approximability of the NP-complete \textsc{Maximum Minimal Feedback Vertex Set} problem. Informally, this natural problem seems to lie in an intermediate space between two more well-studied problems of this type: \textsc{Maximum Minimal Vertex Cover}, for which the best achievable approximation ratio is $\sqrt{n}$ , and \textsc{Upper Dominating Set}, which does not admit any $n^{1-ε}$ approximation. We confirm and quantify this intuition by showing the first non-trivial polynomial time approximation for \textsc{Max Min FVS} with a ratio of $O(n^{2/3})$ , as well as a matching hardness of approximation bound of $n^{2/3-ε}$ , improving the previous known hardness of $n^{1/2-ε}$ . The approximation algorithm also gives a cubic kernel when parameterized by the solution size. Along the way, we also obtain an $O(Δ)$ -approximation and show that this is asymptotically best possible, and we improve the bound for which the problem is NP-hard from $Δ\ge 9$ to $Δ\ge 6$ . Having settled the problem's approximability in polynomial time, we move to the context of super-polynomial time. We devise a generalization of our approximation algorithm which, for any desired approximation ratio $r$ , produces an $r$ -approximate solution in time $n^{O(n/r^{3/2})}$ . This time-approximation trade-off is essentially tight: we show that under the ETH, for any ratio $r$ and $ε>0$ , no algorithm can $r$ -approximate this problem in time $n^{O((n/r^{3/2})^{1-ε})}$ , hence we precisely characterize the approximability of the problem for the whole spectrum between polynomial and sub-exponential time, up to an arbitrarily small constant in the second exponent.

preprint2020arXiv

Approximation Schemes for Subset Sum Ratio Problems

We consider the Subset Sum Ratio Problem ( $SSR$ ), in which given a set of integers the goal is to find two subsets such that the ratio of their sums is as close to~1 as possible, and introduce a family of variations that capture additional meaningful requirements. Our main contribution is a generic framework that yields fully polynomial time approximation schemes (FPTAS) for problems in this family that meet certain conditions. We use our framework to design explicit FPTASs for two such problems, namely Two-Set Subset-Sum Ratio and Factor- $r$ Subset-Sum Ratio, with running time $\mathcal{O}(n^4/\varepsilon)$ , which coincides with the best known running time for the original $SSR$ problem [15].

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.