Lecture Notes in Computer Science 6410 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison,UK TakeoKanade,USA JosefKittler,UK JonM.Kleinberg,USA AlfredKobsa,USA FriedemannMattern,Switzerland JohnC.Mitchell,USA MoniNaor,Israel OscarNierstrasz,Switzerland C.PanduRangan,India BernhardSteffen,Germany MadhuSudan,USA DemetriTerzopoulos,USA DougTygar,USA GerhardWeikum,Germany Advanced Research in Computing and Software Science SublineofLecturesNotesinComputerScience SublineSeriesEditors GiorgioAusiello,UniversityofRome‘LaSapienza’,Italy VladimiroSassone,UniversityofSouthampton,UK SublineAdvisoryBoard SusanneAlbers,UniversityofFreiburg,Germany BenjaminC.Pierce,UniversityofPennsylvania,USA BernhardSteffen,UniversityofDortmund,Germany MadhuSudan,MicrosoftResearch,Cambridge,MA,USA DengXiaotie,CityUniversityofHongKong JeannetteM.Wing,CarnegieMellonUniversity,Pittsburgh,PA,USA Dimitrios M. Thilikos (Ed.) Graph-Theoretic Concepts in Computer Science 36th International Workshop, WG 2010 Zarós, Crete, Greece, June 28-30, 2010 Revised Papers 1 3 VolumeEditor DimitriosM.Thilikos NationalandKapodistrianUniversityofAthens DepartmentofMathematics Panepistimioupolis,15784Athens,Greece E-mail:[email protected] LibraryofCongressControlNumber:2010938221 CRSubjectClassification(1998):G.2.2,I.2.8,E.1,F.2,I.3.5,C.2 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ISSN 0302-9743 ISBN-10 3-642-16925-2SpringerBerlinHeidelbergNewYork ISBN-13 978-3-642-16925-0SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. springer.com ©Springer-VerlagBerlinHeidelberg2010 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SPIN: 06/3180 543210 Preface The 36th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2010) took place in Zaro´s, Crete, Greece, June 28–30, 2010. About 60 mathematicians and computer scientists from all over the world (Australia,Canada,CzechRepublic, France,Germany,Greece,Hungary,Israel, Japan, The Netherlands, Norway, Poland, Switzerland, the UK, and the USA) attended the conference. WG has a long tradition. Since 1975, WG has taken place 21 times in Germany, four times in The Netherlands, twice in Austria, twice in France and once in the Czech Republic, Greece, Italy, Norway, Slovakia, Switzerland, and the UK. WG aims at merging theory and practice by demonstrating how concepts from graph theory can be applied to various areas in computer science, or by extracting new graph theoretic problems from applications. The goal is to presentemergingresearchresultsandtoidentifyandexploredirectionsoffuture research.Theconferenceis well-balancedwithrespectto establishedresearchers and young scientists. There were 94 submissions, two of which where withdrawn before entering the review process. Each submission was carefully reviewed by at least 3, and on average 4.5, members of the Program Committee. The Committee accepted 28papers,whichmakesanacceptanceratioofaround30%.Ishouldstressthat, due to the high competition and the limited schedule, there were papers that were not accepted while they deserved to be. Theprogramalsoincludedtwoexcellentinvitedtalks:thefirstonewasgiven by Dimitris Achlioptas (Department of Computer Science, UC Santa Cruz) on “AlgorithmicBarriersfromPhaseTransitionsinGraphs”andthesecondonewas given by Erik D. Demaine (MIT Computer Science and Artificial Intelligence Laboratory)on“AlgorithmicGraphMinorsandBidimensionality.”Thisvolume contains the abstracts of both talks. I wish to thankall those who contributed to the success of WG 2010. While it is impossible to enumerate them all, this includes the authors for submitting high-quality papers, the reviewersand the members of the ProgramCommittee for their detailed work,the speakersfor their well-preparedtalks, all the partic- ipants for their enthusiasm,andthe personnelof the hotel“Idi”for the pleasant conference environment and facilities. I am grateful to all the students of the Department of Mathematics of the National and KapodistrianUniversity of Athens that helped with the organiza- tion.AmongpeoplefromtheDepartmentofMathematics,UniversityofCrete,I shouldthank ChristosKourouniotisfor his link to the Anogia Academic Village andMihalisKolountzakisforhisvaluableadvice.Butmostofall,Iamindebted VI Preface totheconferencesecretaryMarinaVassilakiforherprofessionalityanddiligence during the preparationand the management of the conference. All material of the conference, including photos and videos of the invited talks, can be found at the homepage of WG 2010 (http://www.math.uoa.gr/ wg2010/).SpecialthankstoCharalamposTampakopoulosforhisprogramming, development, and hosting services. Finally, I should also thank the EasyChair team for the wonderful conference management system. September 2010 Dimitrios M. Thilikos Δημήτριος Μ. Θηλυκός WG 2010 Ζαρός, Κρήτη The Long Tradition of WG WG 1975 U. Pape – Berlin, Germany WG 1976 H. Noltemeier – G¨ottingen, Germany WG 1977 J. Mu¨hlbacher – Linz, Austria WG 1978 M. Nagl, H.J. Schneider – Castler Feuerstein, Germany WG 1979 U. Pape – Berlin, Germany WG 1980 H. Noltemeier – Bad Honnef, Germany WG 1981 J. Mu¨hlbacher – Linz, Austria WG 1982 H.J. Schneider, H. G¨ottler – Neuenkirchen, Germany WG 1983 M. Nagl, J. Perl – Haus Ohrbeck near Onasbru¨ck, Germany WG 1984 U. Pape – Berlin, Germany WG 1985 H. Noltemeier – Castle Schwanberg near Wu¨rzburg, Germany WG 1986 G. Tinhofer, G. Schmidt – Bernried near Munich, Germany WG 1987 H. G¨ottler, H.J. Schneider – Kloster Banz near Bamberg, Germany WG 1988 J. van Leeuwen – Amsterdam, The Netherlands WG 1989 M. Nagl – Castle Rolduc, The Netherlands WG 1990 R.H. M¨ohring – Berlin, Germany WG 1991 G. Schmidt, R. Berghammer – Fischbachau near Munich, Germany WG 1992 E.W Mayr – Wiesbaden-Naurod, Germany WG 1993 J. van Leeuwen – Utrecht, The Netherlands WG 1994 G. Tinhofer, E.W. Mayr, G. Schmidt – Herrsching near Munich, Germany WG 1995 M. Nagl – Aachen, Germany WG 1996 G. Ausiello, A. Marchetti-Spaccamela– Como, Italy WG 1997 R.H. M¨ohring – Berlin, Germany WG 1998 J. Hromkoviˇc, O. Sy´kora – Smolenice Castle, Slovak Republic WG 1999 P. Widmayer – Ascona, Switzerland WG 2000 D. Wagner – Konstanz, Germany WG 2001 A. Brandst¨adt, Boltenhagen near Rostock, Germany WG 2002 L. Kuˇcera – Cˇesky´ Krumlov, Czech Republic WG 2003 H.L. Bodlaender – Elspeet, The Netherlands WG 2004 J. Hromkoviˇc, M. Nagl – Bad Honnef, Germany WG 2005 D. Kratsch – Metz, France WG 2006 F.V. Fomin – Bergen, Norway WG2007 A.Brandst¨adt,D.Kratsch,H.Mu¨ller–DornburgnearJena,Germany WG 2008 H. Broersma,T. Erlebach– Durham, UK WG 2009 C. Paul, M. Habib – Montpellier, France WG 2010 D.M. Thilikos – Zaro´s,Crete, Greece WG 2010 Organization Program Chair Dimitrios M. Thilikos Department of Mathematics, National and Kapodistrian University of Athens, Greece Program Committee Fedor V. Fomin University of Bergen, Norway Pierre Fraigniaud CNRS and University Paris Diderot, France Gregory Z. Gutin Royal Holloway,University of London, UK Fr´ed´eric Havet INRIA Sophia-Antipolis, France Giuseppe F. Italiano University of Rome Tor Vergata, Italy Kazuo Iwama Kyoto University, Japan Jan Kratochv´ıl Charles University, Czech Republic Bojan Mohar Simon Fraser University, Canada David Peleg Weizmann Institute of Science, Israel Prabhakar Ragde University of Waterloo, Canada Dieter Rautenbach Ilmenau University of Technology,Germany Saket Saurabh Institute of Mathematical Sciences, India Ingo Schiermeyer Freiberg University of Mining and Technology, Germany Maria Serna Technical University of Catalonia, Spain Martin Skutella Technical University of Berlin, Germany Dimitrios M. Thilikos National & KapodistrianUniversity of Athens, Greece Jan van Leeuwen Utrecht University, The Netherlands Peter Widmayer Federal Institute of Technology Zurich, Switzerland Gerhard J. Woeginger Eindhoven University of Technology, The Netherlands Organizing Committee Dimitrios M. Thilikos (Chair) Marina Vassilaki (Secretary) Archontia Giannopoulou, Athanassios Koutsonas, Ignasi Sau, Konstantinos Stavropoulos, Charalampos Tampakopoulos,Dimitris Zoros X WG 2010 Organization Organization Entities Anogia Academic Vilage Department of Mathematics, National and Kapodistrian University of Athens External Reviewers of WG 2010 Ittai Abraham, Faisal Abu-Khzam, Noa Agmon, Carme A´lvarez, David Avis, Jørgen Bang-Jensen, Robert Benkoczi, Philip Bille, Jean Blair, Andreas Bley, HansL.Bodlaender,AndreasBrandst¨adt,HajoBroersma,SergioCabello,Sourav Chakraborty, Markus Chimani, Nathann Cohen, Derek Corneil, Robert Crow- ston, Marek Cygan, Ajoy K. Datta, Guoli Ding, Yann Disser, Benjamin Doerr, Frederic Dorn, Michael Dracopoulos, Feodor Dragan, Amalia Duch, Vida Du- jmovi´c, Zdenˇek Dvoˇra´k, Louis Esperet, Uriel Feige, Andreas Emil Feldmann, Michael Fellows, Stefan Felsner, Holger Flier, Radoslav Fulek, Anna Galluc- cio, Leszek Gasieniec, Serge Gaspers, Archontia Giannopoulou, Boris Golden- (cid:2) gorin, Petr Golovach, Martin Golumbic, Fabrizio Grandoni, Jiong Guo, Michel Habib, Mohammad, Taghi Hajiaghayi, Johannes Hatzl, Yinnon Haviv, Pinar Heggernes, Pavol Hell, Christoph Helmberg, Petr Petr Hlinˇeny´, Andreas Holm- sen, Takashi Horiyama, Tomas Hruz, Thore Husfeldt, Hiro Ito, Bart Jansen, Jeannette Janssen, Mark Jones, Tibor Jordan, Hirotsugu Kakugawa, Marcin Kamin´ski,MamadouMoustaphaKant´e,AlexisKaporis,Jan-PhilippKappmeier, Menelaos I. Karavelas, J´an Katrenic, Jun Kawahara, Ken-ichi Kawarabayashi, Judith Keijsper, Jonathan Kelner, Eun Jung Kim, Ralf Klasing, Bettina Klinz, Christian Knauer, Anja Kohl, Mikko Koivisto, Stavros Kolliopoulos, Athanas- sios Koutsonas, Daniel Kr´al, Ilia Krasikov, Dieter Kratsch, Matthias Kriesell, Sven Krumke, Michael Lampis, Monique Laurent, Mathieu Liedloff, Giuseppe Liotta, Daniel Lokshtanov, Vadim Lozin, John Maharry, Monaldo Mastrolilli, Yasuko Matsui, Jannik Matuschke, Jens Maue, Klaus Meer, George Mertzios, Matu´ˇsMihala´k,Zolta´nMiklo´s,NeeldharaMisra,ValiaMitsou,MatthiasMnich, JaninaMu¨ttel,Shin-IchiNakano,N.S.Narayanaswamy,HungNgo,RolfNieder- meier, Prajakta Nimbhorkar, Nicolas Nisse, Jan Obdrza´lek, Yoshio Okamoto, MichaelOkun,Sang-ilOum,AttilaPo´r,ChristophePaul,Dani¨elPaulusma,Rudi Pendavingh,GeevarghesePhilip,PreyasPopat,IanPost,AndrzejProskurowski, Arash Rafiey, Venkatesh Raman, Bert Randerath, Friedrich Regen, Peter Ross- manith, Zdenˇek Ryj´aˇcek, Ignasi Sau, Mathias Schacht, Diego Scheide, Ildiko´ Schlotter, Marcel Sch¨ongens, Philipp Matthias Sch¨afer, Jean-S´ebastien Sereni, Kazuhisa Seto, Akiyoshi Shioura, Michiel Smid, Bettina Speckmann, Daniel Spielman, Rastislav Sramek, Juraj Stacho, Konstantinos Stavropoulos, Michal Stern, Hisao Tamaki, Suguru Tamaki, Wolfgang Thomas, Ioan Todinca, Csaba Toth,RyuheiUehara,TakeakiUno,Pimvan’tHof,LeovanIersel,ErikJanvan Leeuwen, Johan M.M. van Rooij, Martin Vatshelle, Yngve Villanger, Kristina Vuˇskovi´c, Koichi Wada, Oren Weimann, Andreas Wiese, Thomas Wolle, Koichi Yamazaki,HirokiYanagisawa,YuichiYoshida,DimitrisZoros,VadimZverovich, Anna Zych. Table of Contents Invited Talks Algorithmic Barriers from Phase Transitions in Graphs ............... 1 Dimitris Achlioptas Algorithmic Graph Minors and Bidimensionality ..................... 2 Erik D. Demaine Regular Talks Complexity Results for the Spanning Tree Congestion Problem ........ 3 Yota Otachi, Hans L. Bodlaender, and Erik Jan van Leeuwen max-cut and Containment Relations in Graphs ..................... 15 Marcin Kamin´ski The Longest Path Problem is Polynomial on Cocomparability Graphs ......................................................... 27 Kyriaki Ioannidou and Stavros D. Nikolopoulos Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds ......................................................... 39 Petr A. Golovach, Dieter Kratsch, and Jean-Francois Couturier On Stable Matchings and Flows ................................... 51 Tama´s Fleiner Narrowing Down the Gap on the Complexity of Coloring P -Free k Graphs ......................................................... 63 Hajo Broersma, Petr A. Golovach, Dani¨el Paulusma, and Jian Song Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time ........................................................... 75 Pinar Heggernes, Pim van ’t Hof, Daniel Lokshtanov, and Jesper Nederlof Solving Capacitated Dominating Set by Using Coveringby Subsets and Maximum Matching.............................................. 88 Mathieu Liedloff, Ioan Todinca, and Yngve Villanger Efficient Algorithms for Eulerian Extension ......................... 100 Frederic Dorn, Hannes Moser, Rolf Niedermeier, and Mathias Weller