BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

George B. Mertzios

George B. Mertzios contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDiscrete MathematicsComputational Complexitymath.COmath.OC

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
9works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

preprint2022arXiv

Linear Programming Complementation

In this paper we introduce a new operation for Linear Programming (LP), called LP complementation, which resembles many properties of LP duality. Given a maximisation (resp.~minimisation) LP $P$, we define its complement $Q$ as a specific minimisation (resp.~maximisation) LP with the same objective function as $P$. Our central result is the LP complementation theorem, that establishes the following relationship between the optimal value $\text{Opt}(P)$ of $P$ and the optimal value $\text{Opt}(Q)$ of its complement: $\frac{1}{\text{Opt}(P)}+\frac{1}{\text{Opt}(Q)}=1$. The LP complementation operation can be applied if and only if $\text{Opt}(P) > 1$. We then apply LP complementation to hypergraphs. For every hypergraph $H=(V,E)$, its dual is $H^*$ and we call $\overline{H}=(V,\{V\setminus e : e\in E\})$ the complement of $H$. For the covering LP $K(H)$ we obtain $\frac{1}{ \text{Opt}( K(H^*) ) }+\frac{1}{\text{Opt}( K(\overline{H}) ) } = 1$ (and similarly for packing, matching and transversal LPs). We then consider \emph{fractional graph theory}. We prove that the LP for the \Define{fractional in-dominating number} of a digraph $D$ is the complement of the LP for the \Define{fractional total out-dominating number} of the digraph complement of $D$. We also establish that the fractional matching number of a matroid coincides with its edge toughness. Finally, we introduce the problem \text{Vertex Cover with Budget (VCB)}: for a graph $G$ and a positive integer $b$, what is the maximum number $t_b$ of vertex covers $S_1, \dots, S_{t_b}$ of $G$, such that every vertex appears in at most $b$ vertex covers? We relate \text{VCB} with the LP $Q_G$ for the fractional chromatic number of $G$: as $b \to \infty$, $t_b \sim t_f \cdot b$, where $t_f$ is the optimal value of the complement LP of $Q_G$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The complexity of computing optimum labelings for temporal connectivity

A graph is temporally connected if there exists a strict temporal path, i.e. a path whose edges have strictly increasing labels, from every vertex $u$ to every other vertex $v$. In this paper we study temporal design problems for undirected temporally connected graphs. The basic setting of these optimization problems is as follows: given a connected undirected graph $G$, what is the smallest number $|λ|$ of time-labels that we need to add to the edges of $G$ such that the resulting temporal graph $(G,λ)$ is temporally connected? As it turns out, this basic problem, called MINIMUM LABELING (ML), can be optimally solved in polynomial time. However, exploiting the temporal dimension, the problem becomes more interesting and meaningful in its following variations, which we investigate in this paper. First we consider the problem MIN. AGED LABELING (MAL) of temporally connecting the graph when we are given an upper-bound on the allowed age (i.e. maximum label) of the obtained temporal graph $(G,λ)$. Second we consider the problem MIN. STEINER LABELING (MSL), where the aim is now to have a temporal path between any pair of "terminals" vertices which lie in a subset $R\subseteq V$. This relaxed problem resembles STEINER TREE in static graphs. However, due to the requirement of strictly increasing labels in a temporal path, STEINER TREE is not a special case of MSL. Finally we consider the age-restricted version of MSL, namely MIN. AGED STEINER LABELING (MASL). Our main results are threefold: we prove that (i) MAL becomes NP-complete on undirected graphs, while (ii) MASL becomes W[1]-hard with respect to the number $|R|$ of terminals. On the other hand we prove that (iii) although the age-unrestricted problem MSL is NP-hard, it is in FPT with respect to the number $|R|$ of terminals. That is, adding the age restriction, makes the above problems strictly harder.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Deleting edges to restrict the size of an epidemic in temporal networks

Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information spread over social networks and biological diseases spreading over contact networks. Often, the networks over which these processes spread are dynamic in nature, and can be modeled with temporal graphs. Here, we study the problem of deleting edges from a given temporal graph in order to reduce the number of vertices (temporally) reachable from a given starting point. This could be used to control the spread of a disease, rumour, etc. in a temporal graph. In particular, our aim is to find a temporal subgraph in which a process starting at any single vertex can be transferred to only a limited number of other vertices using a temporally-feasible path. We introduce a natural edge-deletion problem for temporal graphs and provide positive and negative results on its computational complexity and approximability.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Polynomial Fixed-Parameter Algorithms: A Case Study for Longest Path on Interval Graphs

We study the design of fixed-parameter algorithms for problems already known to be solvable in polynomial time. The main motivation is to get more efficient algorithms for problems with unattractive polynomial running times. Here, we focus on a fundamental graph problem: Longest Path, that is, given an undirected graph, find a maximum-length path in $G$. Longest Path is NP-hard in general but known to be solvable in $O(n^{4})$ time on $n$-vertex interval graphs. We show how to solve Longest Path on Interval Graphs, parameterized by vertex deletion number $k$ to proper interval graphs, in $O(k^{9}n)$ time. Notably, Longest Path is trivially solvable in linear time on proper interval graphs, and the parameter value $k$ can be approximated up to a factor of 4 in linear time. From a more general perspective, we believe that using parameterized complexity analysis may enable a refined understanding of efficiency aspects for polynomial-time solvable problems similarly to what classical parameterized complexity analysis does for NP-hard problems.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle

In this paper we consider the following total functional problem: Given a cubic Hamiltonian graph $G$ and a Hamiltonian cycle $C_0$ of $G$, how can we compute a second Hamiltonian cycle $C_1 \neq C_0$ of $G$? Cedric Smith proved in 1946, using a non-constructive parity argument, that such a second Hamiltonian cycle always exists. Our main result is an algorithm which computes the second Hamiltonian cycle in time $O(n \cdot 2^{(0.3-\varepsilon)n})$ time, for some positive constant $\varepsilon>0$, and in polynomial space, thus improving the state of the art running time for solving this problem. Our algorithm is based on a fundamental structural property of Thomason's lollipop algorithm, which we prove here for the first time. In the direction of approximating the length of a second cycle in a Hamiltonian graph $G$ with a given Hamiltonian cycle $C_0$ (where we may not have guarantees on the existence of a second Hamiltonian cycle), we provide a linear-time algorithm computing a second cycle with length at least $n - 4α(\sqrt{n}+2α)+8$, where $α= \frac{Δ-2}{δ-2}$ and $δ,Δ$ are the minimum and the maximum degree of the graph, respectively. This approximation result also improves the state of the art.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Matching in Stochastically Evolving Graphs

This paper studies the maximum cardinality matching problem in stochastically evolving graphs. We formally define the arrival-departure model with stochastic departures. There, a graph is sampled from a specific probability distribution and it is revealed as a series of snapshots. Our goal is to study algorithms that create a large matching in the sampled graphs. We define the price of stochasticity for this problem which intuitively captures the loss of any algorithm in the worst case in the size of the matching due to the uncertainty of the model. Furthermore, we prove the existence of a deterministic optimal algorithm for the problem. In our second set of results we show that we can efficiently approximate the expected size of a maximum cardinality matching by deriving a fully randomized approximation scheme (FPRAS) for it. The FPRAS is the backbone of a probabilistic algorithm that is optimal when the model is defined over two timesteps. Our last result is an upper bound of $\frac{2}{3}$ on the price of stochasticity. This means that there is no algorithm that can match more than $\frac{2}{3}$ of the edges of an optimal matching in hindsight.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Power of Data Reduction for Matching

Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For $m$-edge and $n$-vertex graphs, it is well-known to be solvable in $O(m\sqrt{n})$ time; however, for several applications this running time is still too slow. We investigate how linear-time (and almost linear-time) data reduction (used as preprocessing) can alleviate the situation. More specifically, we focus on (almost) linear-time kernelization. We start a deeper and systematic study both for general graphs and for bipartite graphs. Our data reduction algorithms easily comply (in form of preprocessing) with every solution strategy (exact, approximate, heuristic), thus making them attractive in various settings.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs

Given a graph $G$, the longest path problem asks to compute a simple path of $G$ with the largest number of vertices. This problem is the most natural optimization version of the well known and well studied Hamiltonian path problem, and thus it is NP-hard on general graphs. However, in contrast to the Hamiltonian path problem, there are only few restricted graph families such as trees and some small graph classes where polynomial algorithms for the longest path problem have been found. Recently it has been shown that this problem can be solved in polynomial time on interval graphs by applying dynamic programming to a characterizing ordering of the vertices of the given graph \cite{longest-int-algo}, thus answering an open question. In the present paper, we provide the first polynomial algorithm for the longest path problem on a much greater class, namely on cocomparability graphs. Our algorithm uses a similar - but essentially simpler - dynamic programming approach, which is applied to a Lexicographic Depth First Search (LDFS) characterizing ordering of the vertices of a cocomparability graph. Therefore, our results provide evidence that this general dynamic programming approach can be used in a more general setting, leading to efficient algorithms for the longest path problem on greater classes of graphs. LDFS has recently been introduced in \cite{Corneil-LDFS08}. Since then, a similar phenomenon of extending an existing interval graph algorithm to cocomparability graphs by using an LDFS preprocessing step has also been observed for the minimum path cover problem \cite{Corneil-MPC}. Therefore, more interestingly, our results also provide evidence that cocomparability graphs present an interval graph structure when they are considered using an LDFS ordering of their vertices, which may lead to other new and more efficient combinatorial algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Recognition of Tolerance and Bounded Tolerance Graphs

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This subclass of perfect graphs has been extensively studied, due to both its interesting structure and its numerous applications. Several efficient algorithms for optimization problems that are NP-hard on general graphs have been designed for tolerance graphs. In spite of this, the recognition of tolerance graphs - namely, the problem of deciding whether a given graph is a tolerance graph - as well as the recognition of their main subclass of bounded tolerance graphs, have been the most fundamental open problems on this class of graphs (cf. the book on tolerance graphs \cite{GolTol04}) since their introduction in 1982 \cite{GoMo82}. In this article we prove that both recognition problems are NP-complete, even in the case where the input graph is a trapezoid graph. The presented results are surprising because, on the one hand, most subclasses of perfect graphs admit polynomial recognition algorithms and, on the other hand, bounded tolerance graphs were believed to be efficiently recognizable as they are a natural special case of trapezoid graphs (which can be recognized in polynomial time) and share a very similar structure with them. For our reduction we extend the notion of an \emph{acyclic orientation} of permutation and trapezoid graphs. Our main tool is a new algorithm that uses \emph{vertex splitting} to transform a given trapezoid graph into a permutation graph, while preserving this new acyclic orientation property. This method of vertex splitting is of independent interest; very recently, it has been proved a powerful tool also in the design of efficient recognition algorithms for other classes of graphs \cite{MC-Trapezoid}.

0 citations0 reviewsNo code linkedOpen access