Nikolaos Melissinos, Ph.D.

Stať ve sborníku

Katedra teoretické informatiky

Imagine we want to split a group of agents into teams in the most efficient way, considering that each agent has their own preferences about their teammates. This scenario is modeled by the extensively studied Coalition Formation problem. Here, we study a version of this problem where each team must additionally be of bounded size. We conduct a systematic algorithmic study, providing several intractability results as well as multiple exact algorithms that scale well as the input grows (FPT), which could prove useful in practice. Our main contribution is an algorithm that deals efficiently with tree-like structures (bounded treewidth) for "small" teams. We complement this result by proving that our algorithm is asymptotically optimal. Particularly, there can be no algorithm that vastly outperforms the one we present, under reasonable theoretical assumptions, even when considering star-like structures (bounded vertex cover number).

Článek

10.1007/s00236-023-00451-7

Katedra teoretické informatiky

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.

Článek

10.1016/j.dam.2023.11.021

Katedra teoretické informatiky

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.

Stať ve sborníku

10.1609/aaai.v38i16.29686

Katedra teoretické informatiky

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.

Stať ve sborníku

10.4230/LIPIcs.IPEC.2024.18

Katedra teoretické informatiky

A graph G is locally irregular if no two of its adjacent vertices have the same degree. The authors of [Fioravantes et al. Complexity of finding maximum locally irregular induced subgraph. SWAT, 2022] introduced and provided some initial algorithmic results on the problem of finding a locally irregular induced subgraph of a given graph G of maximum order, or, equivalently, computing a subset S of V(G) of minimum order, whose deletion from G results in a locally irregular graph; S is called an optimal vertex-irregulator of G. In this work we provide an in-depth analysis of the parameterised complexity of computing an optimal vertex-irregulator of a given graph G. Moreover, we introduce and study a variation of this problem, where S is a subset of the edges of G; in this case, S is denoted as an optimal edge-irregulator of G. We prove that computing an optimal vertex-irregulator of a graph G is in FPT when parameterised by various structural parameters of G, while it is W[1]-hard when parameterised by the feedback vertex set number or the treedepth of G. Moreover, computing an optimal edge-irregulator of a graph G is in FPT when parameterised by the vertex integrity of G, while it is NP-hard even if G is a planar bipartite graph of maximum degree 6, and W[1]-hard when parameterised by the size of the solution, the feedback vertex set or the treedepth of G. Our results paint a comprehensive picture of the tractability of both problems studied here.

Stať ve sborníku vyzvaná či oceněná

10.4230/LIPIcs.IPEC.2023.21

Katedra teoretické informatiky

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.

Stať ve sborníku

10.1007/978-3-031-43380-1_4

Katedra teoretické informatiky

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.

Stať ve sborníku

10.4230/LIPIcs.MFCS.2023.62

Katedra teoretické informatiky

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).