Source author record

Charis Papadopoulos

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

Catalog footprint

Research overview

3works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-width

The two weighted graph problems Node Multiway Cut (NMC) and Subset Feedback Vertex Set (SFVS) both ask for a vertex set of minimum total weight, that for NMC disconnects a given set of terminals, and for SFVS intersects all cycles containing a vertex of a given set. We design a meta-algorithm that allows to solve both problems in time $2^{O(rw^3)}\cdot n^{4}$ , $2^{O(q^2\log(q))}\cdot n^{4}$ , and $n^{O(k^2)}$ where $rw$ is the rank-width, $q$ the $\mathbb{Q}$ -rank-width, and $k$ the mim-width of a given decomposition. This answers in the affirmative an open question raised by Jaffke et al. (Algorithmica, 2019) concerning an XP algorithm for SFVS parameterized by mim-width. By a unified algorithm, this solves both problems in polynomial-time on the following graph classes: Interval, Permutation, and Bi-Interval graphs, Circular Arc and Circular Permutation graphs, Convex graphs, $k$ -Polygon, Dilworth- $k$ and Co- $k$ -Degenerate graphs for fixed $k$ ; and also on Leaf Power graphs if a leaf root is given as input, on $H$ -Graphs for fixed $H$ if an $H$ -representation is given as input, and on arbitrary powers of graphs in all the above classes. Prior to our results, only SFVS was known to be tractable restricted only on Interval and Permutation graphs, whereas all other results are new.

preprint2016arXiv

Maximizing the Strong Triadic Closure in Split Graphs and Proper Interval Graphs

In social networks the {\sc Strong Triadic Closure} is an assignment of the edges with strong or weak labels such that any two vertices that have a common neighbor with a strong edge are adjacent. The problem of maximizing the number of strong edges that satisfy the strong triadic closure was recently shown to be NP-complete for general graphs. Here we initiate the study of graph classes for which the problem is solvable. We show that the problem admits a polynomial-time algorithm for two unrelated classes of graphs: proper interval graphs and trivially-perfect graphs. To complement our result, we show that the problem remains NP-complete on split graphs, and consequently also on chordal graphs. Thus we contribute to define the first border between graph classes on which the problem is polynomially solvable and on which it remains NP-complete.

preprint2015arXiv

Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs

Let $G$ be a strongly connected directed graph. We consider the following three problems, where we wish to compute the smallest strongly connected spanning subgraph of $G$ that maintains respectively: the $2$ -edge-connected blocks of $G$ (\textsf{2EC-B}); the $2$ -edge-connected components of $G$ (\textsf{2EC-C}); both the $2$ -edge-connected blocks and the $2$ -edge-connected components of $G$ (\textsf{2EC-B-C}). All three problems are NP-hard, and thus we are interested in efficient approximation algorithms. For \textsf{2EC-C} we can obtain a $3/2$ -approximation by combining previously known results. For \textsf{2EC-B} and \textsf{2EC-B-C}, we present new $4$ -approximation algorithms that run in linear time. We also propose various heuristics to improve the size of the computed subgraphs in practice, and conduct a thorough experimental study to assess their merits in practical scenarios.

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.