CIAC 2017

10th International Conference on Algorithms and Complexity
May 24-26, Athens, Greece

Registration is now open!


Aims and Scope

The International Conference on Algorithms and Complexity is intended to provide a forum for researchers working in all aspects of computational complexity and the use, design, analysis and experimentation of efficient algorithms and data structures. The 10th International Conference on Algorithms and Complexity (CIAC 2017) will take place in Athens, Greece, on May 24-26, 2017.


Papers presenting original research in the areas of algorithms and complexity are sought, including (but not limited to):

  • sequential, parallel and distributed algorithms and data structures
  • approximation and randomized algorithms
  • graph algorithms and graph drawing
  • on-line and streaming algorithms
  • analysis of algorithms and computational complexity
  • algorithm engineering
  • web algorithms
  • exact and parameterized computation
  • algorithmic game theory
  • computational biology
  • foundations of communication networks
  • computational geometry
  • discrete optimization

Important Dates

  • Deadline for early registration: April 10, 2017
  • Deadline for submission extended to: November 11, 2016, 23:59 AoΕ
  • Notification of acceptance: December 20, 2016
  • Final manuscript, camera ready: January 31, 2017
  • Conference: May 24-26, 2017

Invited Speakers

  • Giuseppe Italiano, Università di Roma 2, Italy
  • Klaus Jansen, University of Kiel, Germany
  • Christos Papadimitriou, University of California Berkeley, USA

Best Paper Award

This year there will be a CIAC 2017 Best Paper Award, accompanied by a prize of EUR 1,000 offered by Springer.




Program Committee

  • Vincenzo Bonifaci, IASI-CNR, Rome, Italy
  • Jarek Byrka, University of Wroclaw, Poland
  • Tiziana Calamoneri, Università di Roma I, "La Sapienza", Italy
  • Éric Colin de Verdière, CNRS and Université Paris-Est Marne-la-Vallée, France
  • Dimitris Fotakis, National Technical University of Athens, Greece
  • Thomas Erlebach, University of Leicester, UK
  • Irene Finocchi, Università di Roma I, "La Sapienza", Italy
  • Evangelos Kranakis, Carleton University, Canada
  • Dieter Kratsch, University of Lorraine, France
  • Michael Lampis, University Paris-Dauphine, France
  • Vangelis Markakis, Athens University of Economics and Business, Greece
  • Dániel Marx, Hungarian Academy of Science, Hungary
  • Monaldo Mastrolilli, IDSIA, Switzerland
  • Aris Pagourtzis, National Technical University of Athens, Greece
  • Vangelis Th. Paschos, University Paris-Dauphine, France (chair)
  • Francesco Pasquale, Università di Roma I, "La Sapienza", Italy
  • Giuseppe Persiano, Università di Salerno, Italy
  • Tomasz Radzik, King's College London, UK
  • Adi Rosén, CNRS and Université Paris Diderot, France
  • Guido Schäfer, CWI, Netherlands
  • Maria Serna, Universitat Politècnica de Catalunya, Spain
  • Paul Spirakis, University of Liverpool, UK and CTI, Greece
  • Ioan Todinca, University of Orleans, France
  • Angelika Steger, ETH Zurich, Switzerland
  • Andreas Wiese, Universidad de Chile, Chile

Best Paper Award Committee

  • Ljiljana Brankovic, University of Newcastle, Australia
  • Ralf Klasing, CNRS and University Bordeaux 1, France (chair)
  • Cécile Murat, University Paris-Dauphine, France
  • Vangelis Th. Paschos, University Paris-Dauphine, France
  • Peter Widmayer, ETH Zurich, Switzerland

Steering Committee

  • Giorgio Ausiello, Università di Roma I, "La Sapienza", Italy
  • Vangelis Paschos, University Paris-Dauphine, France
  • Rossella Petreschi, Università di Roma I, "La Sapienza", Italy
  • Paul Spirakis, University of Liverpool, UK and CTI, Greece
  • Peter Widmayer, ETH Zurich, Switzerland

Organizing Committee

  • Dimitris Fotakis, National Technical University of Athens (co-chair)
  • Euripides Markou, University of Thessaly
  • Ioannis Milis, Athens University of Economics and Business
  • Aris Pagourtzis, National Technical University of Athens (co-chair)
  • Dimitris Sakavalas, National Technical University of Athens
  • Vassilis Zissimopoulos, National and Kapodistrian University of Athens

Accepted Papers

Themistoklis Melissourgos and Paul Spirakis:
Existence of evolutionarily stable strategies remains hard to decide for a wide range of payoff values
Hans L. Bodlaender and Tom C. van der Zanden:
Improved Lower Bounds for Graph Embedding Problems
Klaus Jansen, Marten Maack and Roberto Solis-Oba:
Structural Parameters for Scheduling with Assignment Restrictions
Torben Hagerup, Frank Kammer and Moritz Laudahn:
Space-Efficient Euler Partition and Bipartite Edge Coloring
Oylum Şeker, Pinar Heggernes, Tınaz Ekim and Z. Caner Taşkın:
Linear-time generation of random chordal graphs
Eleni C. Akrida, Jurek Czyzowicz, Leszek Gasieniec, Lukasz Kuszner and Paul Spirakis:
Temporal flows in Temporal networks
Petr Golovach, Dieter Kratsch and Mohamed Yosri Sayadi:
Enumeration of Maximal Irredundant Sets for Claw-Free Graphs
Li-Hsuan Chen, Sun-Yuan Hsieh, Ling-Ju Hung, Ralf Klasing, Chia-Wei Lee and Bang Ye Wu:
On the complexity of the star p-hub center problem with parameterized triangle inequality
Aritra Banik, Matthew Katz, Eli Packer and Marina Simakov:
Tracking Paths
Konstantinos Mastakas and Antonios Symvonis:
Rooted Uniform Monotone Minimum Spanning Trees
Cristina Bazgan, Thomas Pontoizeau and Zsolt Tuza:
On the complexity of finding a potential community
Nader Bshouty and Ariel Gabizon:
Almost Optimal Cover-Free Families
Sándor Kisfaludi-Bak and Tom C. van der Zanden:
On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs
Martin Gairing, Konstantinos Kollias and Grammateia Kotsialou:
Cost-Sharing in Generalized Selfish Routing
Jason Crampton, Gregory Gutin, Martin Koutecký and Rémi Watrigant:
Parameterized Resiliency Problems via Integer Linear Programming
Fidaa Abed, Lin Chen, Yann Disser, Martin Groß, Nicole Megow, Julie Meissner, Alexander Richter and Roman Rischke:
Scheduling Maintenance Jobs in Networks
Klaus-Tycho Förster, Linus Groner, Torsten Hoefler, Michael König, Sascha Schmid and Roger Wattenhofer:
Multi-Agent Pathfinding with n Agents on Graphs with n Vertices: Combinatorial Classification and Tight Algorithmic Bounds
Yuval Emek, Yaacov Shapiro and Yuyi Wang:
Minimum Cost Perfect Matching with Delays for Two Sources
Lars Jaffke and Bart M. P. Jansen:
Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
Lukas Gianinazzi and Barbara Geissmann:
Cache Oblivious Minimum Cut
Yuya Higashikawa, Keiko Imai, Yusuke Matsumoto, Noriyoshi Sukegawa and Yusuke Yokosuka:
Minimum Point-Overlap Labeling
Laurent Gourves and Jerome Monnot:
Approximate Maximin Share Allocations in Matroids
Toshihiro Fujito:
Approximating Bounded Degree Deletion via Matroid Matching
Ioannis Lamprou, Russell Martin and Sven Schewe:
Perpetually Dominating Large Grids
Giovanni Viglietta, Giuseppe Antonio Di Luna, Paola Flocchini, Taisuke Izumi, Tomoko Izumi and Nicola Santoro:
Population Protocols with Faulty Interactions: the Impact of a Leader
Sascha Brauer:
Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems
Robert Bredereck, Christian Komusiewicz, Stefan Kratsch, Hendrik Molter, Rolf Niedermeier and Manuel Sorge:
Assessing the Computational Complexity of Multi-Layer Subgraph Detection
Sebastian Brandt, Felix Laufenberg, Yuezhou Lv, David Stolz and Roger Wattenhofer:
Collaboration without Communication: Evacuating Two Robots from a Disk
Pieter Kleer and Guido Schaefer:
Tight Inefficiency Bounds for Perception-Parameterized Affine Congestion Games
Stefan Dobrev, Evangelos Kranakis, Danny Krizanc, Manuel Lafond, Jan Manuch, Lata Narayanan, Jaroslav Opatrny and Ladislav Stacho:
Weak Coverage of a Rectangular Barrier
Jaroslav Opatrny, Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Lata Narayanan and Sunil Shende:
Linear Search with Terrain-Dependent Speeds
Matthias Feldotto, Lennart Leder and Alexander Skopalik:
Congestion Games with Complementarities
Erik D. Demaine, Isaac Grosof and Jayson Lynch:
Push-Pull Block Puzzles are Hard
Martin Fürer:
On the Combinatorial Power of the Weisfeiler-Lehman Algorithm
Eleni Bakali, Aggeliki Chalki, Aris Pagourtzis, Petros Pantavos and Stathis Zachos:
Completeness results for counting problems with easy decision
Akanksha Agrawal, Lawqueen Kanesh, Saket Saurabh and Prafullkumar Tale:
Paths to Trees and Cactus


There are different modalities of registration fees for CIAC 2017; all of them include the participation to all sessions on May 24-26, a copy of the proceedings, coffee breaks, lunches, a welcome reception and the social dinner. The registration fees for CIAC 2017 are described in the following table:

Early ( until April 10th ) Late ( until May 10th ) On-site (during the symposium)
Regular registration fee 380 Euros 450 Euros 480 Euros
Student registration fee 280 Euros 350 Euros 380 Euros

Acompanying persons can attend the social dinner; additional tickets will be available during the conference at the price of 50 euros.

Notice that for each accepted paper, at least one author must register.

Click here to register for CIAC 2017


We do not have any special deals with hotels, however some suggestions are listed below. Some of these hotels are relatively close to the conference venue (NTUA campus), while others are located in the city centre, with good connections (metro+bus) to NTUA campus. Please check the prices either from the hotel site directly or using the provided Booking link and pick the best option for you. We would also advise you to compare transportation options between the hotels and NTUA, according to your preferences (public transport, taxi, walking).

Hotel Hotel Website Booking Website
Hilton Athens Hilton Athens Website Booking Hilton
Divani Caravel Divani Caravel Website Booking Divani Caravel
Crowne Plaza Athens City Center Crowne Plaza Website Booking Crowne Plaza
Best Western Ilisia Hotel Best Western Ilisia Website Booking Best Western Ilisia
Airotel Stratos Vassilikos Airotel Stratos Vasilikos Website Booking Airotel Stratos Vasilikos
Golden Age Golden Age Website Booking Golden Age
Athinais Athinais Website Booking Athinais
Arethusa Arethusa Website Booking Arethusa
Pan Pan Website Booking Pan
Zappion Zappion Website Booking Zappion
Elizabeth hotel Elizabeth Website Booking Elizabeth
Family Inn Family Inn Website
President President Website Booking President
St George St George Website Booking St George
* Here is a map with the above hotels (kudos to Yaacov Shapiro for sharing this).


CIAC 2017 will take place in the Multimedia Amphitheater of the National Technical University of Athens, located in the basement of the building of NTUA's Central Library. See the map below:

You can arrive at the Central Library by various ways:

By public transport:

The easiest way is by taking the Blue Metro line (map) and getting off at the "ΚΑΤΕΧΑΚΗ" station. Then take the bus 242, get off at stop "ΘΥΡΩΡΕΙΟ" (you get off at the first stop inside the Campus) and walk 5 minutes towards the Central Library.

Another option is to take the bus 140 from the "ΚΑΤΕΧΑΚΗ" metro station and get off at stop "ΠΟΛΥΤΕΧΝΕΙΟΥΠΟΛΗ". Then get into the campus and walk 10 minutes towards the Central Library.

By taxi:

Taxi from the Katechaki ("ΚΑΤΕΧΑΚΗ") Station to NTUA will cost aproximately 3,5 €.

By car:

You can use this google map to get directions from Alimou-Katechaki Avenue.

Submission Guidelines

Authors are invited to submit an extended abstract of at most 12 pages by 23:59 AoE, Friday, November 11, 2016 (deadline extended). Submissions are handled by EasyChair at the following web page:

Submission Format: An extended abstract submitted to CIAC 2017 should start with the title of the paper, each author's name, affiliation and e-mail address, followed by a one-paragraph summary of the results to be presented. This should then be followed by a technical exposition of the main ideas and techniques used to achieve these results, including motivation and a clear comparison with related work. The extended abstract should not exceed 12 single-spaced pages (excluding references), using reasonable margins and at least 10-point font. If the authors believe that more details are essential to substantiate the claims of the paper, they may include a clearly marked appendix (with no space limit) that will be read at the discretion of the Program Committee. It is strongly recommended that submissions adhere to the specified format and length. Submissions that are clearly too long may be rejected immediately.

All submissions will be rigorously peer-reviewed and evaluated on the basis of the quality of their contribution, originality, soundness, and significance.

The proceedings of the conference will be published by Springer-Verlag in the ARCoSS/LNCS series and will be available for distribution at the conference. Accepted papers will be allocated 12 pages total in the LNCS format in the proceedings. Submissions are encouraged, though not required, to follow the LNCS format. More information about the LNCS format can be found on the author instructions page of Springer-Verlag.


Previous Conferences:

Travel Information

Athens is easily accessible by air, sea, and road. Once there, the public transportation system provides a safe, dependable and efficient way to move around the city. The public transportation network consists of underground (metro), train, suburban railways, buses, trolley buses and trams. Athens is also connected with other parts of the mainland through a network of roads and railways. Timetables and other information are available here.

Visitors arriving by air will arrive to the Athens International Airport "Eleftherios Venizelos" (IATA code: ATH).

Visa requirements

Citizens of EU

EU Citizens do not need a visa to travel to Greece. In most cases a personal ID card will suffice to enter the country.

Non-EU Citizens

Greece is a member of the European Union and for most nationalities no visa is required.

Citizens of some countries need an entry visa for Greece.

If you need a visa, make sure to apply for one well in advance. To check current visa requirements or find the nearest Greek Embassy or Consulate , see information provided by the Greek Ministry of Foreign Affairs.

Other Information

Time zone

Greece is in the Eastern European Time Zone. Eastern European Standard Time (EET) is two hours ahead of Greenwich Mean Time (GMT+2). Like most countries in Europe, Summer (Daylight-Saving) Time is observed in Greece, where the time is shifted forward by 1 hour; 3 hours ahead of Greenwich Mean Time (GMT+3). Daylight-Saving time will be observed during the conference.


The national currency in Greece is the Euro.