International Workshop on Combinatorial Algorithms

Problems Section

Dear Readers,

This is a non-exhaustive list of open problems contributed by the IWOCA community, often but not necessarily at the open problem session of the IWOCA conference.

If you know of any results relevant to one of the problems, also partial ones, we would greatly appreciate it if you could let us know. Please contact one of the problem section editors (Alessio Conte: alessio.conte_AT_unipi.it; Dominik Köppl: koeppl.dsc_AT_tmd.ac.jp).

If you have started working on a problem and made some advances, you could consider contacting the contributor of the problem, possibly but not necessarily with view of cooperating with him or her. In any case, we ask you to cite the IWOCA open problems page (www.iwoca.org, Problems Section) as well as the name of the problem contributor, should your work result in a publication.

If you have any open problems you would like to present to the IWOCA community, please don't hesitate to contact us:

  • Alessio Conte (conte_AT_di.unipi.it)
  • Dominik Köppl (koeppl.dsc_AT_tmd.ac.jp)


ARCHIVE
(problems that have been solved, or older versions of open problems)
 
Problem Contributed by in/at
 last updated
 
LATEST PROBLEMS (IWOCA 2022) (check last column for update status)
Recognition of well-dominated graphs U ́everton dos Santos Souza IWOCA 2022 Jan
2023
Tree Enumeration by Leaf Numbers Dominik Köppl IWOCA 2022 Nov 2022
From String Attractors to Strings Dominik Köppl IWOCA 2022 Nov 2022
Maximum Number of Distinct Lyndon Subsequences Dominik Köppl IWOCA 2022 Nov 2022
 
PROBLEMS FROM PREVIOUS IWOCA'S (check last column for update status)
Pancake flipping: The Big 3 Joe Sawada IWOCA 2021 July 2021
Non-preemptive tree packing Lasse Wulf IWOCA 2021 July 2021
Longest Path with Neighborly Help under Edge Deletion Fabian Frei IWOCA 2020 June 2020
Vertex Cover with Neighborly Help under Edge Deletion Fabian Frei IWOCA 2020 June 2020
Complexity of Multipacking in graphs Florent Foucaud IWOCA 2020 June 2020
 
Wheeler Graph Recognition on 3-NFAs and 4-NFAs Daniel Gibney IWOCA 2020 June 2020
 
Open Problems on Prefix Normal Words Zsuzsanna Lipták IWOCA 2020 July 2021
 
Orthogonal labelings in de Bruijn graphs Luca Mariot IWOCA 2020 June 2020
Straight-Line Orthogonal Drawings of Complete Ternary Trees in Near-Linear Area Maurizio Patrignani IWOCA 2018 Aug. 2018
Derangements with a Fixed Number of Inversions Max A. Alekseyev IWOCA 2016 Aug. 2016
Grammar-Based Compression Katrin Casel, Henning Fernau, Markus L. Schmid IWOCA 2016 Aug. 2016
The 3-Sphere Regular Cellulation Conjecture Sergio De Agostino IWOCA 2016 Apr. 2019
Sorting Strings by Reversals Guillaume Fertin IWOCA 2016 Aug. 2016
Does P-complete have a hierarchy like NP-complete has W[*]? Shouwei Li IWOCA 2016 Aug. 2016
Balanced Mobiles Yassine Hamoudi, Sophie Laplante, Roberto Mantaci IWOCA 2016 Aug. 2016
Can Lempel-Ziv and Burrows-Wheeler compression be asymptotically compared? Nicola Prezza IWOCA 2016 June 2020
Hamiltonian Paths in the Complete Graph Giuseppe Mazzuoccolo IWOCA 2015 Oct. 2015
Readability of bipartite graphs Martin Milanič IWOCA 2015 Oct. 2015
Vector connectivity with demands at most 3 Ferdinando Cicalese IWOCA 2015 Oct. 2015
Constructing sort of Δ-regular graphs to challenge the IRUP property for bin packing Romeo Rizzi IWOCA 2015 Oct. 2015
Counting numerical semigroups by genus Maria Bras-Amorós IWOCA 2014 Oct. 2014
Tiling hypercubes with copies of a given graph Jerrold R. Griggs IWOCA 2014 Dec. 2014
When is Size-One Memory Mastermind worse than original Mastermind? Gerold Jäger IWOCA 2014 Dec. 2014
On the Minimum Number of Plus Operators in Expressions of Series-Parallel Graphs and in Read-Once Functions Mark Korenblit,
Vadim E. Levit		 IWOCA 2014 Oct. 2015
The maximum edge q-coloring problem Tommi Larjomaa,
Alexandru Popa		 IWOCA 2014 Oct. 2015
Compute Runs/Repetitions Without Global Data Structures
In this talk there is more detailed info. See also the archive.		 Bill Smyth IWOCA 2014 Oct. 2014
Problems on Minimal Pancyclic Graphs Walter Wallis IWOCA 2014 Oct. 2014
Decision of Soccer Score Sequences Péter Burcsi IWOCA 2013 Oct. 2015
Simply Connected Domino Tatami Covering Alejandro Erickson IWOCA 2013 Oct. 2015
Finding posets P in a family of subposets Jerrold R. Griggs IWOCA 2013 Aug. 2014
Maximum Rooted Triplets Consistency Jesper Jansson Sep. 2013 Oct. 2015
Complexity of Magic Labelling Gerold Jäger IWOCA 2013 Oct. 2015
The (2,1) Consecutive-Ones-Property Murray Patterson IWOCA 2013 Aug. 2014
The generelized inverse Voronoi problem Hebert Pérez-Rosés IWOCA 2013 July 2013
Complexity of Unshuffling a Square for Small Alphabets. More details also in IWOCA 2013 slides (open problem on p.5). Michael Soltys IWOCA 2013 Oct. 2014
Decidability of set decipherability over directed figures Włodzimierz Moczurad IWOCA 2012 Oct. 2015
Tight bounds for sorting a multiset?Travis Gagie
 		 IWOCA 2009 Oct. 2015
Graphs with no equal length cycles Chunhui Lai IWOCA 2007 July 2021
The complexity of covering a ladder using cycles F. Foucaud IWOCA 2012 Oct. 2015
Element Uniqueness: A special case Tetsuo Asano
 IWOCA 2011 Mar. 2013
A problem on domatic partition S. Arumugam IWOCA 2011 June 2011
Acyclic Coloring Subdivision Rahnuma Islam Nishat IWOCA 2011 Apr. 2012
The nth MARM: Maximum Red Matching Free of Blue-Red Alternating Cycles in a Complete Blue-Red Bipartite Graph of Degree n Vadim Timkovsky Jan. 2011 Jan. 2011
Distance magic graphs S. Arumugam IWOCA 2010 Jan. 2011
Distance pattern distinguishing sets in graphs S. Arumugam IWOCA 2009 Jan. 2011
Open problems in dynamic map labeling Chee Yap IWOCA 2007 Mar. 2012
Indexed approximate string matching
(Partial progress has been made here and here, but in general still open.)		 Gonzalo Navarro June 2019
Certificate dispersal problems Koichi Wada
 		 IWOCA 2007
 
ARCHIVE
(problems that have been solved, or older versions of open problems)