Source author record

Valia Mitsou

Valia Mitsou appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Discrete Mathematics math.CO

Catalog footprint

What is connected

5works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2022arXiv

Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity

We study the complexity of graph modification problems with respect to homomorphism-based colouring properties of edge-coloured graphs. A homomorphism from edge-coloured graph $G$ to edge-coloured graph $H$ is a vertex-mapping from $G$ to $H$ that preserves adjacencies and edge-colours. We consider the property of having a homomorphism to a fixed edge-coloured graph $H$. The question we are interested in is: given an edge-coloured graph $G$, can we perform $k$ graph operations so that the resulting graph admits a homomorphism to $H$? The operations we consider are vertex-deletion, edge-deletion and switching (an operation that permutes the colours of the edges incident to a given vertex). Switching plays an important role in the theory of signed graphs, that are 2-edge-coloured graphs whose colours are the signs $+$ and $-$. We denote the corresponding problems (parameterized by $k$) by VD-$H$-COLOURING, ED-$H$-COLOURING and SW-$H$-COLOURING. These problems generalise $H$-COLOURING (to decide if an input graph admits a homomorphism to a fixed target $H$). Our main focus is when $H$ is an edge-coloured graph with at most two vertices, a case that is already interesting as it includes problems such as VERTEX COVER, ODD CYCLE RANSVERSAL and EDGE BIPARTIZATION. For such a graph $H$, we give a P/NP-c complexity dichotomy for VD-$H$-COLOURING, ED-$H$-COLOURING and SW-$H$-COLOURING. We then address their parameterized complexity. We show that VD-$H$-COLOURING and ED-$H$-COLOURING for all such $H$ are FPT. In contrast, already for some $H$ of order 3, unless P=NP, none of the three problems is in XP, since 3-COLOURING is NP-c. We show that SW-$H$-COLOURING is different: there are three 2-edge-coloured graphs $H$ of order 2 for which SW-$H$-COLOURING is W-hard, and assuming the ETH, admits no algorithm in time $f(k)n^{o(k)}$. For the other cases, SW-$H$-COLOURING is FPT.

preprint2022arXiv

Grundy Distinguishes Treewidth from Pathwidth

Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to understand the "price of generality" of these widths: as we transition from more restrictive to more general notions, which are the problems that see their complexity status deteriorate from fixed-parameter tractable to intractable? This type of question is by now very well-studied, but, somewhat strikingly, the algorithmic frontier between the two (arguably) most central width notions, treewidth and pathwidth, is still not understood: currently, no natural graph problem is known to be W-hard for one but FPT for the other. Indeed, a surprising development of the last few years has been the observation that for many of the most paradigmatic problems, their complexities for the two parameters actually coincide exactly, despite the fact that treewidth is a much more general parameter. It would thus appear that the extra generality of treewidth over pathwidth often comes "for free". Our main contribution in this paper is to uncover the first natural example where this generality comes with a high price. We consider Grundy Coloring, a variation of coloring where one seeks to calculate the worst possible coloring that could be assigned to a graph by a greedy First-Fit algorithm. We show that this well-studied problem is FPT parameterized by pathwidth; however, it becomes significantly harder (W[1]-hard) when parameterized by treewidth. Furthermore, we show that Grundy Coloring makes a second complexity jump for more general widths, as it becomes para-NP-hard for clique-width. Hence, Grundy Coloring nicely captures the complexity trade-offs between the three most well-studied parameters. Completing the picture, we show that Grundy Coloring is FPT parameterized by modular-width.

preprint2014arXiv

Parameterized Edge Hamiltonicity

We study the parameterized complexity of the classical Edge Hamiltonian Path problem and give several fixed-parameter tractability results. First, we settle an open question of Demaine et al. by showing that Edge Hamiltonian Path is FPT parameterized by vertex cover, and that it also admits a cubic kernel. We then show fixed-parameter tractability even for a generalization of the problem to arbitrary hypergraphs, parameterized by the size of a (supplied) hitting set. We also consider the problem parameterized by treewidth or clique-width. Surprisingly, we show that the problem is FPT for both of these standard parameters, in contrast to its vertex version, which is W-hard for clique-width. Our technique, which may be of independent interest, relies on a structural characterization of clique-width in terms of treewidth and complete bipartite subgraphs due to Gurski and Wanke.

preprint2013arXiv

The Computational Complexity of the Game of Set and its Theoretical Applications

The game of SET is a popular card game in which the objective is to form Sets using cards from a special deck. In this paper we study single- and multi-round variations of this game from the computational complexity point of view and establish interesting connections with other classical computational problems. Specifically, we first show that a natural generalization of the problem of finding a single Set, parameterized by the size of the sought Set is W-hard; our reduction applies also to a natural parameterization of Perfect Multi-Dimensional Matching, a result which may be of independent interest. Second, we observe that a version of the game where one seeks to find the largest possible number of disjoint Sets from a given set of cards is a special case of 3-Set Packing; we establish that this restriction remains NP-complete. Similarly, the version where one seeks to find the smallest number of disjoint Sets that overlap all possible Sets is shown to be NP-complete, through a close connection to the Independent Edge Dominating Set problem. Finally, we study a 2-player version of the game, for which we show a close connection to Arc Kayles, as well as fixed-parameter tractability when parameterized by the number of rounds played.

preprint2012arXiv

Scrabble is PSPACE-Complete

In this paper we study the computational complexity of the game of Scrabble. We prove the PSPACE-completeness of a derandomized model of the game, answering an open question of Erik Demaine and Robert Hearn.