Skip to main content

Research Repository

Advanced Search

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.

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.

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.

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.

Parameterized algorithms for finding square roots (2014)
Journal Article
Cochefert, M., Couturier, J., Golovach, P., & Paulusma, D. (2014). Parameterized algorithms for finding square roots. Algorithmica, https://doi.org/10.1007/s00453-014-9967-4

We show that the following two problems are fixed-parameter tractable with parameter k: testing whether a connected n-vertex graph with m edges has a square root with at most n−1+k edges and testing whether such a graph has a square root with at leas... Read More about Parameterized algorithms for finding square roots.

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 intersection of tolerance and cocomparability graphs (2014)
Journal Article
Mertzios, G., & Zaks, S. (2016). On the intersection of tolerance and cocomparability graphs. Discrete Applied Mathematics, 199, 46-88. https://doi.org/10.1016/j.dam.2014.10.025

Tolerance graphs have been extensively studied since their introduction, due to their interesting structure and their numerous applications, as they generalize both interval and permutation graphs in a natural way. It has been conjectured by Golumbic... Read More about On the intersection of tolerance and cocomparability graphs.

Computing in Permutation Groups Without Memory (2014)
Journal Article
Cameron, P., Fairbairn, B., & Gadouleau, M. (2014). Computing in Permutation Groups Without Memory. Chicago journal of theoretical computer science, 2014(7), 1-20. https://doi.org/10.4086/cjtcs.2014.007

Memoryless computation is a modern technique to compute any function of a set of registers by updating one register at a time while using no memory. Its aim is to emulate how computations are performed in modern cores, since they typically involve up... Read More about Computing in Permutation Groups Without Memory.

Computing in Matrix Groups Without Memory (2014)
Journal Article
Cameron, P., Fairbairn, B., & Gadouleau, M. (2014). Computing in Matrix Groups Without Memory. Chicago journal of theoretical computer science, 2014(8), 1-16. https://doi.org/10.4086/cjtcs.2014.008

Memoryless computation is a novel means of computing any function of a set of registers by updating one register at a time while using no memory. We aim to emulate how computations are performed on modern cores, since they typically involve updates o... Read More about Computing in Matrix Groups Without Memory.

Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs (2014)
Journal Article
Broersma, H., Fiala, J., Golovach, P., Kaiser, T., Paulusma, D., & Proskurowski, A. (2015). Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs. Journal of Graph Theory, 79(4), 282-299. https://doi.org/10.1002/jgt.21832

We prove that for all inline image an interval graph is inline image-Hamilton-connected if and only if its scattering number is at most k. This complements a previously known fact that an interval graph has a nonnegative scattering number if and only... Read More about Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs.

Subset Glauber Dynamics on Graphs, Hypergraphs and Matroids of Bounded Tree-Width (2014)
Journal Article
Bordewich, M., & Kang, R. (2014). Subset Glauber Dynamics on Graphs, Hypergraphs and Matroids of Bounded Tree-Width. Electronic Journal of Combinatorics, 21(4), Article 19

Motivated by the `subgraphs world' view of the ferromagnetic Ising model, we analyse the mixing times of Glauber dynamics based on subset expansion expressions for classes of graph, hypergraph and matroid polynomials. With a canonical paths argument,... Read More about Subset Glauber Dynamics on Graphs, Hypergraphs and Matroids of Bounded Tree-Width.

Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs (2014)
Journal Article
Mertzios, G., & Spirakis, P. (2016). Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs. Algorithmica, 74(1), 385-414. https://doi.org/10.1007/s00453-014-9949-6

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 cannot be solved in... Read More about Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs.

Oracle Tractability of Skew Bisubmodular Functions (2014)
Journal Article
Huber, A., & Krokhin, A. (2014). Oracle Tractability of Skew Bisubmodular Functions. SIAM Journal on Discrete Mathematics, 28(4), 1828-1837. https://doi.org/10.1137/130936038

In this paper we consider skew bisubmodular functions as recently introduced by the authors and Powell. We construct a convex extension of a skew bisubmodular function which we call Lovász extension in correspondence to the submodular case. We use th... Read More about Oracle Tractability of Skew Bisubmodular Functions.

Closing complexity gaps for coloring problems on H-free graphs (2014)
Journal Article
Golovach, P., Paulusma, D., & Song, J. (2014). Closing complexity gaps for coloring problems on H-free graphs. Information and Computation, 237, 204-214. https://doi.org/10.1016/j.ic.2014.02.004

If a graph G contains no subgraph isomorphic to some graph H , then G is called H -free. A coloring of a graph G=(V,E) is a mapping c:V→{1,2,…} such that no two adjacent vertices have the same color, i.e., c(u)≠c(v) if uv∈E; if |c(V)|⩽k then c is a k... Read More about Closing complexity gaps for coloring problems on H-free graphs.

Memoryless computation: New results, constructions, and extensions (2014)
Journal Article
Gadouleau, M., & Riis, S. (2015). Memoryless computation: New results, constructions, and extensions. Theoretical Computer Science, 562, 129-145. https://doi.org/10.1016/j.tcs.2014.09.040

In this paper, we are interested in memoryless computation, a modern paradigm to compute functions which generalises the famous XOR swap algorithm to exchange the contents of two variables without using a buffer. In memoryless computation, programs a... Read More about Memoryless computation: New results, constructions, and extensions.

The computational complexity of disconnected cut and 2K2-partition (2014)
Journal Article
Martin, B., & Paulusma, D. (2015). The computational complexity of disconnected cut and 2K2-partition. Journal of Combinatorial Theory, Series B, 111, 17-37. https://doi.org/10.1016/j.jctb.2014.09.002

For a connected graph G=(V,E), a subset U⊆V is called a disconnected cut if U disconnects the graph and the subgraph induced by U is disconnected as well. We show that the problem to test whether a graph has a disconnected cut is NP-complete. This pr... Read More about The computational complexity of disconnected cut and 2K2-partition.

Entropy of Closure Operators and Network Coding Solvability (2014)
Journal Article
Gadouleau, M. (2014). Entropy of Closure Operators and Network Coding Solvability. Entropy, 16(9), 5122-5143. https://doi.org/10.3390/e16095122

The entropy of a closure operator has been recently proposed for the study ofnetwork coding and secret sharing. In this paper, we study closure operators in relation to their entropy. We first introduce four different kinds of rank functions for a gi... Read More about Entropy of Closure Operators and Network Coding Solvability.

Mixing of the Glauber Dynamics for the Ferromagnetic Potts Model (2014)
Journal Article
Bordewich, M., Greenhill, C., & Patel, V. (2016). Mixing of the Glauber Dynamics for the Ferromagnetic Potts Model. Random Structures and Algorithms, 48(1), 21-52. https://doi.org/10.1002/rsa.20569

We present several results on the mixing time of the Glauber dynamics for sampling from the Gibbs distribution in the ferromagnetic Potts model. At a fixed temperature and interaction strength, we study the interplay between the maximum degree (Δ) of... Read More about Mixing of the Glauber Dynamics for the Ferromagnetic Potts Model.