Skip to main content

Research Repository

Advanced Search

Kernelization Lower Bounds for Finding Constant-Size Subgraphs (2018)
Book Chapter
Fluschnik, T., Mertzios, G., & Nichterlein, A. (2018). Kernelization Lower Bounds for Finding Constant-Size Subgraphs. In F. Manea, R. Miller, & D. Nowotka (Eds.), Sailing routes in the world of computation : 14th Conference on Computability in Europe, CiE 2018, Kiel, Germany, July 30-August 3, 2018. Proceedings (183-193). Springer Verlag. https://doi.org/10.1007/978-3-319-94418-0_19

Kernelization is an important tool in parameterized algorithmics. Given an input instance accompanied by a parameter, the goal is to compute in polynomial time an equivalent instance of the same problem such that the size of the reduced instance only... Read More about Kernelization Lower Bounds for Finding Constant-Size Subgraphs.

Polymorphisms, and how to use them (2017)
Book Chapter
Barto, L., Krokhin, A., & Willard, R. (2017). Polymorphisms, and how to use them. In A. Krokhin, & S. Živný (Eds.), The constraint satisfaction problem : complexity and approximability (1-44). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/dfu.vol7.15301.1

This article describes the algebraic approach to Constraint Satisfaction Problem that led to many developments in both CSP and universal algebra. No prior knowledge of universal algebra is assumed.

The complexity of Valued CSPs (2017)
Book Chapter
Krokhin, A., & Živný, S. (2017). The complexity of Valued CSPs. In A. Krokhin, & S. Živný (Eds.), The constraint satisfaction problem : complexity and approximability (233-266). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/dfu.vol7.15301.9

We survey recent results on the broad family of problems that can be cast as valued constraint satisfaction problems (VCSPs). We discuss general methods for analysing the complexity of such problems, give examples of tractable cases, and identify gen... Read More about The complexity of Valued CSPs.

A multi-level hypergraph partitioning algorithm using rough set clustering (2015)
Book Chapter
Lotfifar, F., & Johnson, M. (2015). A multi-level hypergraph partitioning algorithm using rough set clustering. In J. Träff, S. Hunold, & F. Versaci (Eds.), Euro-Par 2015 : parallel processing : 21st International Conference on Parallel and Distributed Computing, Vienna, Austria, August 24-28, 2015, Proceedings (159-170). Springer Verlag. https://doi.org/10.1007/978-3-662-48096-0_13

The hypergraph partitioning problem has many applications in scientific computing and provides a more accurate inter-processor communication model for distributed systems than the equivalent graph problem. In this paper, we propose a sequential multi... Read More about A multi-level hypergraph partitioning algorithm using rough set clustering.

Intersection Graphs of L-Shapes and Segments in the Plane (2014)
Book Chapter
Felsner, S., Knauer, K., Mertzios, G., & Ueckerdt, T. (2014). Intersection Graphs of L-Shapes and Segments in the Plane. In E. Csuhaj-Varjú, M. Dietzfelbinger, & Z. Ésik (Eds.), Mathematical foundations of computer science 2014 : 39th international symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, part II (299-310). Springer Verlag. https://doi.org/10.1007/978-3-662-44465-8_26

An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: ⌊,⌈,⌋ and ⌉. A k-bend path is a simple path in the plane, whose direction changes k times from horizontal to vertical. If a graph adm... Read More about Intersection Graphs of L-Shapes and Segments in the Plane.

Determining Majority in Networks with Local Interactions and Very Small Local Memory (2014)
Book Chapter
Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2014). Determining Majority in Networks with Local Interactions and Very Small Local Memory. In J. Esparza, P. Fraigniaud, T. Husfeldt, & E. Koutsoupias (Eds.), Automata, languages, and programming : 41st international colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, proceedings, part I (871-882). Springer Verlag. https://doi.org/10.1007/978-3-662-43948-7_72

We study here the problem of determining the majority type in an arbitrary connected network, each vertex of which has initially two possible types (states). The vertices may have a few additional possible states and can interact in pairs only if the... Read More about Determining Majority in Networks with Local Interactions and Very Small Local Memory.

Minimum Bisection Is NP-hard on Unit Disk Graphs (2014)
Book Chapter
Díaz, J., & Mertzios, G. (2014). Minimum Bisection Is NP-hard on Unit Disk Graphs. In E. Csuhaj-Varjú, M. Dietzfelbinger, & Z. Ésik (Eds.), Mathematical foundations of computer science 2014 : 39th international symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, part II (251-262). Springer Verlag. https://doi.org/10.1007/978-3-662-44465-8_22

In this paper we prove that the Min-Bisection problem is NP-hard on unit disk graphs, thus solving a longstanding open question.

Towards a Characterization of Constant-Factor Approximable Min CSPs (2014)
Book Chapter
Dalmau, V., Krokhin, A., & Manokaran, R. (2015). Towards a Characterization of Constant-Factor Approximable Min CSPs. In P. Indyk (Ed.), Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms : San Diego, California, USA, January 4-6, 2015 (847-857). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611973730.58

We study the approximability of Minimum Constraint Satisfaction Problems (Min CSPs) with a fixed finite constraint language Γ on an arbitrary finite domain. The goal in such a problem is to minimize the number of unsatisfied constraints in a given in... Read More about Towards a Characterization of Constant-Factor Approximable Min CSPs.

Approximating Fixation Probabilities in the Generalized Moran Process (2014)
Book Chapter
Mertzios, G. (2014). Approximating Fixation Probabilities in the Generalized Moran Process. In M. Kao (Ed.), Encyclopedia of algorithms (1-6). Springer Verlag. https://doi.org/10.1007/978-3-642-27848-8_596-1

Problem Definition Population and evolutionary dynamics have been extensively studied, usually with the assumption that the evolving population has no spatial structure. One of the main models in this area is the Moran process [17]. The initial popul... Read More about Approximating Fixation Probabilities in the Generalized Moran Process.

On the Recognition of Four-Directional Orthogonal Ray Graphs (2013)
Book Chapter
Felsner, S., Mertzios, G., & Mustata, I. (2013). On the Recognition of Four-Directional Orthogonal Ray Graphs. In K. Chatterjee, & J. Sgall (Eds.), Mathematical foundations of computer science 2013 : 38th international symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings (373-384). Springer Verlag. https://doi.org/10.1007/978-3-642-40313-2_34

Orthogonal ray graphs are the intersection graphs of horizontal and vertical rays (i.e. half-lines) in the plane. If the rays can have any possible orientation (left/right/up/down) then the graph is a 4-directional orthogonal ray graph (4-DORG). Othe... Read More about On the Recognition of Four-Directional Orthogonal Ray Graphs.

Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs (2013)
Book Chapter
Mertzios, G., & Spirakis, P. (2013). Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs. In P. V. E. Boas, F. C. Groen, G. F. Italiano, J. Nawrocki, & H. Sack (Eds.), SOFSEM 2013 : theory and practice of computer science : 39th international conference on current trends in theory and practice of computer science, Špindlerův Mlýn, Czech Republic, January 26-31, 2013. Proceedings (332-343). Springer Verlag. https://doi.org/10.1007/978-3-642-35843-2_29

The 3-coloring problem is well known to be NP-complete. It is also well known that it remains NP-complete when the input is restricted to graphs with diameter 4. Moreover, assuming the Exponential Time Hypothesis (ETH), 3-coloring can not be solved i... Read More about Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs.

Strong Bounds for Evolution in Networks (2013)
Book Chapter
Mertzios, G., & Spirakis, P. (2013). Strong Bounds for Evolution in Networks. In F. V. Fomin, R. Freivalds, M. Kwiatkowska, & D. Peleg (Eds.), Automata, languages, and programming : 40th international colloquium, ICALP 2013, Riga, Latvia, July 8 - 12, 2013, proceedings, part II (669-680). Springer Verlag. https://doi.org/10.1007/978-3-642-39212-2_58

This work extends what is known so far for a basic model of evolutionary antagonism in undirected networks (graphs). More specifically, this work studies the generalized Moran process, as introduced by Lieberman, Hauert, and Nowak [Nature, 433:312-31... Read More about Strong Bounds for Evolution in Networks.

Temporal Network Optimization Subject to Connectivity Constraints (2013)
Book Chapter
Mertzios, G., Michail, O., Chatzigiannakis, I., & Spirakis, P. (2013). Temporal Network Optimization Subject to Connectivity Constraints. In F. V. Fomin, R. Freivalds, M. Kwiatkowska, & D. Peleg (Eds.), Automata, languages, and programming : 40th international colloquium, ICALP 2013, Riga, Latvia, July 8 - 12, 2013, proceedings, part II (657-668). Springer Verlag. https://doi.org/10.1007/978-3-642-39212-2_57

In this work we consider temporal networks, i.e. networks defined by a labeling λ assigning to each edge of an underlying graph G a set of discrete time-labels. The labels of an edge, which are natural numbers, indicate the discrete time moments at w... Read More about Temporal Network Optimization Subject to Connectivity Constraints.

The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial (2013)
Book Chapter
Mertzios, G. (2013). The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial. In H. L. Bodlaender, & G. F. Italiano (Eds.), Algorithms - ESA 2013 : 21st annual European symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings (719-730). Springer Verlag. https://doi.org/10.1007/978-3-642-40450-4_61

Intersection graphs of geometric objects have been extensively studied, both due to their interesting structure and their numerous applications; prominent examples include interval graphs and permutation graphs. In this paper we study a natural graph... Read More about The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial.

Random Network Coding and Matroids (2012)
Book Chapter
Gadouleau, M. (2012). Random Network Coding and Matroids. In K. Al Agha (Ed.), Network coding (147-184). John Wiley and Sons

Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width (2011)
Book Chapter
Bordewich, M., & Kang, R. (2011). Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width. In L. Aceto, M. Henzinger, & J. Sgall (Eds.), Automata, languages and programming (533-544). Springer Verlag. https://doi.org/10.1007/978-3-642-22006-7_45

Motivated by the ‘subgraphs world’ view of the ferromagnetic Ising model, we develop a general approach to studying mixing times of Glauber dynamics based on subset expansion expressions for a class of graph polynomials. With a canonical paths argume... Read More about Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width.

Dualities for constraint satisfaction problems (2008)
Book Chapter
Bulatov, A., Krokhin, A., & Larose, B. (2008). Dualities for constraint satisfaction problems. In N. Creignou, P. Kolaitis, & H. Vollmer (Eds.), Complexity of constraints : an overview of current research themes (93-124). Springer Verlag. https://doi.org/10.1007/978-3-540-92800-3_5

In a nutshell, a duality for a constraint satisfaction problem equates the existence of one homomorphism to the non-existence of other homomorphisms. In this survey paper, we give an overview of logical, combinatorial, and algebraic aspects of the fo... Read More about Dualities for constraint satisfaction problems.