Nikolaos Melissinos, Ph.D.

Publikace

Approximating subset sum ratio via partition computations

Autoři
Alonistiotis, G.; Antonopoulos, A.; Melissinos, N.; Pagourtzis, A.; Petsalakis, S.; Vasilakis, M.
Rok
2024
Publikováno
Acta Informatica. 2024, 61(2), 101-113. ISSN 1432-0525.
Typ
Článek
Anotace
We present a new FPTAS for the SUBSET SUM RATIO problem, which, given a set of integers, asks for two disjoint subsets such that the ratio of their sums is as close to 1 as possible. Our scheme makes use of exact and approximate algorithms for PARTITION, and clearly showcases the close relationship between the two algorithmic problems. Depending on the relationship between the size of the input set n and the error margin \espilon, we improve upon the best currently known algorithm of Melissinos and Pagourtzis [COCOON 2018] of complexity O(n^4/\espilon). In particular, the exponent of n in our proposed scheme may decrease down to 2, depending on the PARTITION algorithm used.

Average-case complexity of a branch-and-bound algorithm for MIN DOMINATING SET

Autoři
Denat, T.; Harutyunyan, A.; Melissinos, N.; Paschos, V. T..
Rok
2024
Publikováno
Discrete Applied Mathematics. 2024, 345 4-8. ISSN 0166-218X.
Typ
Článek
Anotace
The average-case complexity of a branch-and-bound algorithm for MIN DOMINATING SET problem in random graphs in the G(n, p) model is studied. We identify phase transitions between subexponential and exponential average-case complexities, depending on the growth of the probability p with respect to the number n of nodes. (c) 2023 Elsevier B.V. All rights reserved.

Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology

Rok
2024
Publikováno
Proceedings of the 38th AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2024. p. 17380-17388. vol. 38. ISSN 2159-5399.
Typ
Stať ve sborníku
Anotace
In the Multiagent Path Finding (MAPF for short) problem, we focus on efficiently finding non-colliding paths for a set of k agents on a given graph G, where each agent seeks a path from its source vertex to a target. An important measure of the quality of the solution is the length of the proposed schedule l, that is, the length of a longest path (including the waiting time). In this work, we propose a systematic study under the parameterized complexity framework. The hardness results we provide align with many heuristics used for this problem, whose running time could potentially be improved based on our Fixed-Parameter Tractability (FPT) results. We show that MAPF is W[1]-hard with respect to k (even if k is combined with the maximum degree of the input graph). The problem remains NP-hard in planar graphs even if the maximum degree and the makespan l are fixed constants. On the positive side, we show an FPT algorithm for k+l. As we continue, the structure of G comes into play. We give an FPT algorithm for parameter k plus the diameter of the graph G. The MAPF problem is W[1]-hard for cliquewidth of G plus l while it is FPT for treewidth of G plus l.

Bandwidth Parameterized by Cluster Vertex Deletion Number

Autoři
Gima, T.; Kim, E.J.; Köhler, N.; Melissinos, N.; Vasilakis, M.
Rok
2023
Publikováno
Proceedings of the 18th International Symposium on Parameterized and Exact Computation. Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2023. p. 21:1-21:15. vol. 285. ISSN 1868-8969. ISBN 978-3-95977-305-8.
Typ
Stať ve sborníku vyzvaná či oceněná
Anotace
Given a graph G and an integer b, Bandwidth asks whether there exists a bijection π from V(G) to {1, …, |V(G)|} such that max_{{u, v} ∈ E(G)} | π(u) - π(v) | ≤ b. This is a classical NP-complete problem, known to remain NP-complete even on very restricted classes of graphs, such as trees of maximum degree 3 and caterpillars of hair length 3. In the realm of parameterized complexity, these results imply that the problem remains NP-hard on graphs of bounded pathwidth, while it is additionally known to be W[1]-hard when parameterized by the treedepth of the input graph. In contrast, the problem does become FPT when parameterized by the vertex cover number of the input graph. In this paper, we make progress towards the parameterized (in)tractability of Bandwidth. We first show that it is FPT when parameterized by the cluster vertex deletion number cvd plus the clique number ω of the input graph, thus generalizing the previously mentioned result for vertex cover. On the other hand, we show that Bandwidth is W[1]-hard when parameterized only by cvd. Our results generalize some of the previous results and narrow some of the complexity gaps.

Odd Chromatic Number of Graph Classes

Autoři
Belmonte, R.; Harutyunyan, A.; Köhler, N.; Melissinos, N.
Rok
2023
Publikováno
Proceedings of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science. Cham: Springer, 2023. p. 44-58. Lecture Notes in Computer Science. vol. 14093. ISSN 0302-9743. ISBN 978-3-031-43379-5.
Typ
Stať ve sborníku
Anotace
A graph is called odd (respectively, even) if every vertex has odd (respectively, even) degree. Gallai proved that every graph can be partitioned into two even induced subgraphs, or into an odd and an even induced subgraph. We refer to a partition into odd subgraphs as an odd colouring of G. Scott [Graphs and Combinatorics, 2001] proved that a graph admits an odd colouring if and only if it has an even number of vertices. We say that a graph G is k-odd colourable if it can be partitioned into at most k odd induced subgraphs. We initiate the systematic study of odd colouring and odd chromatic number of graph classes. In particular, we consider for a number of classes whether they have bounded odd chromatic number. Our main results are that interval graphs, graphs of bounded modular-width and graphs of bounded maximum degree all have bounded odd chromatic number.

Parameterized Max Min Feedback Vertex Set

Autoři
Lampis, M.; Melissinos, N.; Vasilakis, M.
Rok
2023
Publikováno
Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science. Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2023. p. 62:1-62:15. vol. 272. ISSN 1868-8969. ISBN 978-3-95977-292-1.
Typ
Stať ve sborníku
Anotace
Given a graph G and an integer k, Max Min FVS asks whether there exists a minimal set of vertices of size at least k whose deletion destroys all cycles. We present several results that improve upon the state of the art of the parameterized complexity of this problem with respect to both structural and natural parameters. Using standard DP techniques, we first present an algorithm of time tw^O(tw) n^O(1), significantly generalizing a recent algorithm of Gaikwad et al. of time vc^O(vc) n^O(1), where tw, vc denote the input graph’s treewidth and vertex cover respectively. Subsequently, we show that both of these algorithms are essentially optimal, since a vc^o(vc) n^O(1) algorithm would refute the ETH. With respect to the natural parameter k, the aforementioned recent work by Gaikwad et al. claimed an FPT branching algorithm with complexity 10^k n^O(1). We point out that this algorithm is incorrect and present a branching algorithm of complexity 9.34^k n^O(1).