Source author record

Ioannis Katsikarelis

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 math.CO

Catalog footprint

Research overview

2works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Parameterized Orientable Deletion

A graph is $d$ -orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most $d$ . $d$ -orientability is a well-studied concept with close connections to fundamental graph-theoretic notions and applications as a load balancing problem. In this paper we consider the d-ORIENTABLE DELETION problem: given a graph $G=(V,E)$ , delete the minimum number of vertices to make $G$ $d$ -orientable. We contribute a number of results that improve the state of the art on this problem. Specifically: - We show that the problem is W[2]-hard and $\log n$ -inapproximable with respect to $k$ , the number of deleted vertices. This closes the gap in the problem's approximability. - We completely characterize the parameterized complexity of the problem on chordal graphs: it is FPT parameterized by $d+k$ , but W-hard for each of the parameters $d,k$ separately. - We show that, under the SETH, for all $d,ε$ , the problem does not admit a $(d+2-ε)^{tw}$ , algorithm where $tw$ is the graph's treewidth, resolving as a special case an open problem on the complexity of PSEUDOFOREST DELETION. - We show that the problem is W-hard parameterized by the input graph's clique-width. Complementing this, we provide an algorithm running in time $d^{O(d\cdot cw)}$ , showing that the problem is FPT by $d+cw$ , and improving the previously best known algorithm for this case.

preprint2013arXiv

Computing bounded-width tree and branch decompositions of k-outerplanar graphs

By a well known result the treewidth of k-outerplanar graphs is at most 3k-1. This paper gives, besides a rigorous proof of this fact, an algorithmic implementation of the proof, i.e. it is shown that, given a k-outerplanar graph G, a tree decomposition of G of width at most 3k-1 can be found in O(kn) time and space. Similarly, a branch decomposition of a k-outerplanar graph of width at most 2k+1 can be also obtained in O(kn) time, the algorithm for which is also analyzed.

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.