Author: "Coati A" / Topic: combinatorics - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Coati A"' showing total 123 results

Start Over Author "Coati A" Topic combinatorics

123 results on '"Coati A"'

1. Bispindles in strongly connected digraphs with large chromatic number

Author: Raul Lopes, Nathann Cohen, Frédéric Havet, William Lochet, Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Laboratoire de Recherche en Informatique (LRI), CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), Laboratoire de Recherche en Informatique ( LRI ), Université Paris-Sud - Paris 11 ( UP11 ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -CentraleSupélec-Centre National de la Recherche Scientifique ( CNRS ), Combinatorics, Optimization and Algorithms for Telecommunications ( COATI ), Inria Sophia Antipolis - Méditerranée ( CRISAM ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -COMmunications, Réseaux, systèmes Embarqués et Distribués ( COMRED ), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis ( I3S ), Université Nice Sophia Antipolis ( UNS ), Université Côte d'Azur ( UCA ) -Université Côte d'Azur ( UCA ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Nice Sophia Antipolis ( UNS ), Université Côte d'Azur ( UCA ) -Université Côte d'Azur ( UCA ) -Centre National de la Recherche Scientifique ( CNRS ) -Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis ( I3S ), Université Côte d'Azur ( UCA ) -Université Côte d'Azur ( UCA ) -Centre National de la Recherche Scientifique ( CNRS ), Parallelism, Graphs and Optimization Research Group ( ParGO ), Universidade Federal do Ceará ( UFC ), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: Discrete mathematics, Strongly connected component, Conjecture, Applied Mathematics, [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM], Disjoint sets, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Theoretical Computer Science, Combinatorics, Computational Theory and Mathematics, Integer, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Geometry and Topology, Chromatic scale, Combinatorics (math.CO), Mathematics
Abstract: A $(k_1+k_2)$-bispindle is the union of $k_1$ $(x,y)$-dipaths and $k_2$ $(y,x)$-dipaths, all these dipaths being pairwise internally disjoint. Recently, Cohen et al. showed that for every $(1,1)$- bispindle $B$, there exists an integer $k$ such that every strongly connected digraph with chromatic number greater than $k$ contains a subdivision of $B$. We investigate generalizations of this result by first showing constructions of strongly connected digraphs with large chromatic number without any $(3,0)$-bispindle or $(2,2)$-bispindle. We then consider $(2,1)$-bispindles. Let $B(k_1,k_2;k_3)$ denote the $(2,1)$-bispindle formed by three internally disjoint dipaths between two vertices $x,y$, two $(x,y)$-dipaths, one of length $k_1$ and the other of length $k_2$, and one $(y,x)$-dipath of length $k_3$. We conjecture that for any positive integers $k_1, k_2,k_3$, there is an integer $g(k_1,k_2,k_3)$ such that every strongly connected digraph with chromatic number greater than $g(k_1,k_2,k_3)$ contains a subdivision of $B(k_1,k_2;k_3)$. As evidence, we prove this conjecture for $k_2=1$ (and $k_1, k_3$ arbitrary).
Published: 2018
Full Text: View/download PDF

2. Connectivity Inference in Mass Spectrometry based Structure Determination

Author: Deepesh Agarwal, Frédéric Cazals, David Coudert, Stéphane Pérennes, Christelle Caillouet, Júlio Araújo, Algorithms, Biology, Structure (ABS), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Bodlaender, H.L. and Italiano, G.F., Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), INRIA, Equipes-projet: ABS et COATI, Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Vertex (graph theory), Algorithm Analysis and Problem Complexity, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Inference, 0102 computer and information sciences, Data Structures, 01 natural sciences, Numeric Computing, Combinatorics, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], 03 medical and health sciences, Computer Communication Networks, Computer Graphics, Greedy algorithm, 030304 developmental biology, Mathematics, 0303 health sciences, Discrete Mathematics in Computer Science, A protein, Data structure, [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], Graph, Structural biology, 010201 computation theory & mathematics, Pairwise comparison, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM]
Abstract: We consider the following Minimum Connectivity Inference problem (MCI), which arises in structural biology: given vertex sets $V_i\subseteq V, i\in I$, find the graph $G=(V,E)$ minimizing the size of the edge set $E$, such that the sub-graph of $G$ induced by each $V_i$ is connected. This problem arises in structural biology, when one aims at finding the pairwise contacts between the proteins of a protein assembly, given the lists of proteins involved in sub-complexes. We present four contributions. First, using a reduction of the set cover problem, we establish that MCI is APX-hard. Second, we show how to solve the problem to optimality using a mixed integer linear programming formulation (MILP). Third, we develop a greedy algorithm based on union-find data structures (Greedy), yielding a $2(\log_2 |V|+\log_2 \kappa)$-approximation, with $\kappa$ the maximum number of subsets $V_i$ a vertex belongs to. Fourth, application-wise, we use the MILP and the greedy heuristic to solve the aforementioned connectivity inference problem in structural biology. We show that the solutions of MILP and Greedy are more parsimonious than those reported by the algorithm initially developed in biophysics, which are not qualified in terms of optimality. Since MILP outputs a set of optimal solutions, we introduce the notion of consensus solution. Using assemblies whose pairwise contacts are known exhaustively, we show an almost perfect agreement between the contacts predicted by our algorithms and the experimentally determined ones, especially for consensus solutions.; Nous considérons le problème d'Inférence de Connectivité Minimale (MCI) qui se pose en biologie structurale: étant donnés des ensembles de sommets $V_i\subseteq V, i\in I$, trouver le graphe $G=(V,E)$ minimisant la taille de l'ensemble des arêtes $E$, de telle sorte que le sous-graphe de $G$ induit par un chaque ensemble $V_i$ soit connexe. Ce problème se pose en biologie structurale, pour la determination des contacts plausibles entre les protéines d'un assemblage, à partir des listes de protéines présentes dans des sous-complexes. Nous présentons quatre contributions. Premièrement, nous montrons que le problème MCI est APX-hard en utilisant une réduction de set cover. Deuxièmement, nous présentons une formulation en programme linéaire mixte (MILP) permettant de résoudre MCI de façon optimale. Troisièmement, nous proposons un algorithme glouton (Greedy) basé sur des structures de données Union-Find. Nous montrons que cet algorithme est une $2(\log_2 |V|+\log_2 \kappa)$-approximation de l'optimal, où $\kappa$ est le nombre maximum d'ensembles $V_i$ contenant un sommet donné. Quatrièmement, d'un point de vue appliqué, nous utilisons l'approche MILP et l'algorithme glouton pour résoudre le problème MCI en biologie structurale. Nous montrons que les solutions calculées par MILP et Greedy sont plus parcimonieuses que celles produites par l'algorithme utilisé à ce jour en bio-physique --- lequel n'est pas qualifié en terme d'optimalité. Les algorithmes MILP et Greedy générant des ensembles de solutions, nous introduisons la notion de solution consensus. En utilisant le cas d'assemblages dont les contacts sont connus de façon exhaustive, nous montrons un accord presque parfait entre les contacts determinés par nos algorithmes et ceux determinés expérimentalement, en particulier pour les solutions consensus.
Published: 2013
Full Text: View/download PDF

3. Eternal Domination: D-Dimensional Cartesian and Strong Grids and Everything in Between

Author: Stéphane Pérennes, Fionn Mc Inerney, Nicolas Nisse, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Aix Marseille Université (AMU), Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France, Aix-Marseille Université, Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Algorithmique, Combinatoire et Recherche Opérationnelle (ACRO), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: General Computer Science, Domination analysis, Strong grid, King's graph, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Computer Science::Computational Geometry, 01 natural sciences, Omega, law.invention, Combinatorics, Computer Science::Discrete Mathematics, law, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], Cartesian coordinate system, Physics, Mathematics::Combinatorics, Applied Mathematics, Grids, 16. Peace & justice, Graph, Computer Science Applications, Vertex (geometry), Cartesian grid, 010201 computation theory & mathematics, Combinatorial Games, 020201 artificial intelligence & image processing, Eternal Domination, Graphs
Abstract: In the eternal domination game played on graphs, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to adjacent vertices on their turn. The goal is to determine the eternal domination number $$\gamma ^{\infty }_{all}$$ of a graph, which is the minimum number of guards required to defend against an infinite sequence of attacks. This paper first continues the study of the eternal domination game on strong grids $$P_n\boxtimes P_m$$ . Cartesian grids $$P_n \square P_m$$ have been vastly studied with tight bounds existing for small grids such as $$k\times n$$ grids for $$k\in \{2,3,4,5\}$$ . It was recently proven that $$\gamma ^{\infty }_{all}(P_n \square P_m)=\gamma (P_n \square P_m)+O(n+m)$$ where $$\gamma (P_n \square P_m)$$ is the domination number of $$P_n \square P_m$$ which lower bounds the eternal domination number [Lamprou et al. Eternally dominating large grids. Theoretical Computer Science, 794:27–46, 2019]. We prove that, for all $$n,m\in \mathbb {N^*}$$ such that $$m\ge n$$ , $$\lfloor \frac{n}{3} \rfloor \lfloor \frac{m}{3} \rfloor +\Omega (n+m)=\gamma _{all}^{\infty } (P_{n}\boxtimes P_{m})=\lceil \frac{n}{3} \rceil \lceil \frac{m}{3} \rceil + O(m\sqrt{n})$$ (note that $$\lceil \frac{n}{3} \rceil \lceil \frac{m}{3} \rceil$$ is the domination number of $$P_n\boxtimes P_m$$ ). We then generalise our technique to prove that $$\gamma _{all}^{\infty }(G)=\gamma (G)+o(\gamma (G))$$ for all graphs $$G\in {\mathcal {F}}$$ , where $${\mathcal {F}}$$ is a large family of D-dimensional grids which are supergraphs of the D-dimensional Cartesian grid and subgraphs of the D-dimensional strong grid. In particular, $${\mathcal {F}}$$ includes both the D-dimensional Cartesian grid and the D-dimensional strong grid.
Published: 2021
Full Text: View/download PDF

4. On minimizing the maximum color for the 1–2–3 Conjecture

Author: Bi Li, Binlong Li, Julien Bensmail, Nicolas Nisse, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Xidian University, Northwestern Polytechnical University [Xi'an] (NPU), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), and ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
Subjects: Conjecture, 1-2-3 Conjecture, Applied Mathematics, 0211 other engineering and technologies, 021107 urban & regional planning, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, small vertex colors, Graph, Vertex (geometry), Combinatorics, Treewidth, 010201 computation theory & mathematics, Bounded function, Bipartite graph, edge labelings, Discrete Mathematics and Combinatorics, Chromatic scale, proper vertex-colorings, Connectivity, Mathematics
Abstract: International audience; The 1-2-3 Conjecture asserts that, for every connected graph different from K2 , its edges can be labeled with 1,2,3 so that, when coloring each vertex with the sum of its incident labels, no two adjacent vertices get the same color. This conjecture takes place in the more general context of distinguishing labelings, where the goal is to label graphs so that some pairs of their elements are distinguishable relatively to some parameter computed from the labeling. In this work, we investigate the consequences of labeling graphs as in the 1-2-3 Conjecture when it is further required to make the maximum resulting color as small as possible. In some sense, we aim at producing a number of colors that is as close as possible to the chromatic number of the graph. We first investigate the hardness of determining the minimum maximum color by a labeling for a given graph, which we show is NP-complete in the class of bipartite graphs but polynomial-time solvable in the class of graphs with bounded treewidth. We then provide bounds on the minimum maximum color that can be generated both in the general context, and for particular classes of graphs. Finally, we study how using larger labels permits to reduce the maximum color.
Published: 2021
Full Text: View/download PDF

5. Sequential Metric Dimension

Author: Stéphane Pérennes, Julien Bensmail, Nicolas Nisse, Fionn Mc Inerney, Dorian Mazauric, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Algorithms, Biology, Structure (ABS), Inria Sophia Antipolis - Méditerranée (CRISAM), ANR-11-LABX-0031,UCN@SOPHIA,Réseau orienté utilisateur(2011), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], General Computer Science, Generalization, Existential quantification, Class (philosophy), 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], [MATH]Mathematics [math], 0101 mathematics, Time complexity, Mathematics, Applied Mathematics, 010102 general mathematics, Games in graphs, 020206 networking & telecommunications, Binary logarithm, metric dimension, Graph, Computer Science Applications, Vertex (geometry), Metric dimension, 010201 computation theory & mathematics, Theory of computation, Graph (abstract data type), complexity
Abstract: International audience; In the localization game, introduced by Seager in 2013, an invisible and immobile target is hidden at some vertex of a graph $G$. At every step, one vertex $v$ of $G$ can be probed which results in the knowledge of the distance between $v$ and the secret location of the target. The objective of the game is to minimize the number of steps needed to locate the target whatever be its location.We address the generalization of this game where $k\geq 1$ vertices can be probed at every step. Our game also generalizes the notion of the {\it metric dimension} of a graph.Precisely, given a graph $G$ and two integers $k,\ell \geq 1$, the {\sc Localization} problem asks whether there exists a strategy to locate a target hidden in $G$ in at most $\ell$ steps and probing at most $k$ vertices per step. We first show that, in general, this problem is \textsf{NP}-complete for every fixed $k \geq 1$ (resp., $\ell \geq 1$).We then focus on the class of trees.On the negative side,we prove that the \Localization problem is \textsf{NP}-complete in trees when $k$ and $\ell$ are part of the input. On the positive side, we design a $(+1)$-approximation algorithm for the problem in $n$-node trees, {\it i.e.}, an algorithm that computes in time $O(n \log n)$ (independent of $k$) a strategy to locate the target in at most one more step than an optimal strategy. This algorithm can be used to solve the \Localization problem in trees in polynomial time if $k$ is fixed.We also consider some of these questions in the context where, upon probing the vertices,the relative distances to the target are retrieved.This variant of the problem generalizes the notion of the {\it centroidal dimension} of a graph.
Published: 2020
Full Text: View/download PDF

6. On {a,b}-edge-weightings of bipartite graphs with odd a,b

Author: Julien Bensmail, Kasper Szabo Lyngsie, Fionn Mc Inerney, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Technical University of Denmark [Lyngby] (DTU), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), and Danmarks Tekniske Universitet = Technical University of Denmark (DTU)
Subjects: bipartite graphs, Applied Mathematics, 010102 general mathematics, odd weights, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Neighbour-sum-distinguishing edge-weightings, Combinatorics, Odd weights, 010201 computation theory & mathematics, 1-2-3 conjecture, 05c15, Bipartite graph, QA1-939, Discrete Mathematics and Combinatorics, 05c22, neighbour-sum-distinguishing edge-weightings, 0101 mathematics, Mathematics, Bipartite graphs
Abstract: International audience; For any S⊂ℤ we say that a graph G has the S-property if there exists an S-edge-weighting w:E(G)→S such that for any pair of adjacent vertices u,v we have Σ_{e∈E(v)} w(e) ≠ Σ_{e∈E(u)} w(e), where E(v) and E(u) are the sets of edges incident to v and u respectively. This work focuses on {a,a+2}-edge-weightings where a∈ℤ is odd. We show that a 2-connected bipartite graph has the {a,a+2}-property if and only if it is not a so-called odd multi-cactus. In the case of trees, we show that only one case is pathological. That is, we show that all trees have the {a,a+2}-property for odd a≠−1, while there is an easy characterization of trees without the {−1,1}-property.
Published: 2022
Full Text: View/download PDF

7. Metric Dimension: from Graphs to Oriented Graphs

Author: Fionn Mc Inerney, Julien Bensmail, Nicolas Nisse, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), This work has been partially supported by ANR project MultiMod and ANR program 'Investments for the Future' under reference ANR-11-LABX-0031-01. It has also been supported by the project GALOP STIC AMSUD 19-STIC-05., ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-17-EURE-0004,UCA DS4H,UCA Systèmes Numériques pour l'Homme(2017), ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Inria Sophia Antipolis - Méditerranée (CRISAM), and Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France
Subjects: Strongly-connected orientations, Resolving sets, General Computer Science, 0211 other engineering and technologies, Metric dimension, 02 engineering and technology, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, symbols.namesake, Discrete Mathematics and Combinatorics, [INFO]Computer Science [cs], 0101 mathematics, Undirected graph, Mathematics, Applied Mathematics, 010102 general mathematics, 021107 urban & regional planning, Torus, Eulerian path, Grid, Graph, 010201 computation theory & mathematics, Bounded function, symbols, Row
Abstract: International audience; The metric dimension $MD(G)$ of an undirected graph $G$ is the cardinality of a smallest set of vertices that allows, through their distances to all vertices, to distinguish any two vertices of $G$. Many aspects of this notion have been investigated since its introduction in the 70's, including its generalization to digraphs. In this work, we study, for particular graph families, the maximum metric dimension over all strongly-connected orientations, by exhibiting lower and upper bounds on this value. We first exhibit general bounds for graphs with bounded maximum degree. In particular, we prove that, in the case of subcubic $n$-node graphs, all strongly-connected orientations asymptotically have metric dimension at most $\frac{n}{2}$, and that there are such orientations having metric dimension $\frac{2n}{5}$. We then consider strongly-connected orientations of grids. For a torus with $n$ rows and $m$ columns, we show that the maximum value of the metric dimension of a strongly-connected Eulerian orientation is asymptotically $\frac{nm}{2}$ (the equality holding when $n$, $m$ are even, which is best possible). For a grid with $n$ rows and $m$ columns, we prove that all strongly-connected orientations asymptotically have metric dimension at most $\frac{2nm}{3}$, and that there are such orientations having metric dimension $\frac{nm}{2}$.
Published: 2022
Full Text: View/download PDF

8. On the dichromatic number of surfaces

Author: Frédéric Havet, Clément Rambaud, Kolja Knauer, Pierre Aboulker, Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), ANR-16-CE40-0009,GATO,Graphes, Algorithmes et TOpologie(2016), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)
Subjects: dichromatic number, 010102 general mathematics, Torus, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Surface (topology), graphs on surfaces, 01 natural sciences, planar graphs, Planar graph, Combinatorics, symbols.namesake, 010201 computation theory & mathematics, Euler characteristic, symbols, Projective plane, 0101 mathematics, Klein bottle, Mathematics
Abstract: In this paper, we give bounds on the dichromatic number $\overrightarrow{\chi }(\varSigma )$ of a surface $\varSigma $, which is the maximum dichromatic number of an oriented graph embeddable on $\varSigma $. We determine the asymptotic behaviour of $\overrightarrow{\chi }(\varSigma )$ by showing that there exist constants $a_1$ and $a_2$ such that, $ a_1\frac{\sqrt{-c}}{\log (-c)} \le \overrightarrow{\chi }(\varSigma ) \le a_2 \frac{\sqrt{-c}}{\log (-c)} $ for every surface $\varSigma $ with Euler characteristic $c\le -2$. We then give more explicit bounds for some surfaces with high Euler characteristic. In particular, we show that the dichromatic numbers of the projective plane $\mathbb {N}_1$, the Klein bottle $\mathbb {N}_2$, the torus $\mathbb {S}_1$, and Dyck’s surface $\mathbb {N}_3$ are all equal to 3, and that the dichromatic numbers of the 5-torus $\mathbb {S}_5$ and the 10-cross surface $\mathbb {N}_{10}$ are equal to 4.
Published: 2021
Full Text: View/download PDF

9. Search via Parallel Lévy Walks on Z2

Author: Francesco d'Amore, Emanuele Natale, Andrea E. F. Clementi, George Giakkoupis, Università degli Studi di Roma Tor Vergata [Roma], the World Is Distributed Exploring the tension between scale and coordination (WIDE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: Polynomial, Computer science, [SDV.BA]Life Sciences [q-bio]/Animal biology, Modulo, Hitting time, 0102 computer and information sciences, 01 natural sciences, Settore INF/01, Combinatorics, Mathematics::Probability, Lévy flight, 010201 computation theory & mathematics, 0103 physical sciences, Line (geometry), Exponent, Interval (graph theory), [INFO]Computer Science [cs], Almost surely, [MATH]Mathematics [math], 010306 general physics, ComputingMilieux_MISCELLANEOUS
Abstract: Motivated by the Levy foraging hypothesis -- the premise that various animal species have adapted to follow Levy walks to optimize their search efficiency -- we study the parallel hitting time of Levy walks on the infinite two-dimensional grid. We consider k independent discrete-time Levy walks, with the same exponent α ∈(1,∞), that start from the same node, and analyze the number of steps until the first walk visits a given target at distance l. % We show that for any choice of k and l from a large range, there is a unique optimal exponent α_k,∈ (2,3), for which the hitting time is O(l2/k) w.h.p., while modifying the exponent by any constant term e>0 increases the hitting time by a factor polynomial in l, or the walks fail to hit the target almost surely. % Based on that, we propose a surprisingly simple and effective parallel search strategy, for the setting where k and l are unknown: The exponent of each Levy walk is just chosen independently and uniformly at random from the interval (2,3). This strategy achieves optimal search time (modulo polylogarithmic factors) among all possible algorithms (even centralized ones that know k). % Our results should be contrasted with a line of previous work showing that the exponent α = 2 is optimal for various search problems. In our setting of k parallel walks, we show that the optimal exponent depends on k and l, and that randomizing the choice of the exponents works simultaneously for all k and l.
Published: 2021
Full Text: View/download PDF

10. Further Results on an Equitable 1-2-3 Conjecture

Author: Nicolas Nisse, Foivos Fioravantes, Julien Bensmail, Fionn Mc Inerney, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Algorithmique, Combinatoire et Recherche Opérationnelle (ACRO), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Conjecture, 1-2-3 Conjecture, Applied Mathematics, 0211 other engineering and technologies, 021107 urban & regional planning, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Combinatorics, 010201 computation theory & mathematics, Bipartite graph, Discrete Mathematics and Combinatorics, Proper labellings, Equitable labellings, Mathematics
Abstract: International audience; In this work, we consider equitable proper labellings of graphs, which were recently introduced by Baudon, Pilśniak, Przybyƚo, Senhaji, Sopena, and Wożniak. Given a graph G, the goal is to assign labels to the edges so that 1) no two adjacent vertices are incident to the same sum of labels, and 2) every two labels are assigned about the same number of times. Particularly , we aim at designing such equitable proper k-labellings of G with k being as small as possible. In connection with the so-called 1-2-3 Conjecture, it might be that labels 1,2,3 are, a few obvious exceptions apart, always sufficient to achieve this just as in the non-equitable version of the problem. We provide results regarding some open questions about equitable proper labellings. Via a hardness result, we first prove that there exist infinitely many graphs for which more labels are required in the equitable version than in the non-equitable version. This remains true in the bipartite case. We finally show that, for every $k≥3$, every k-regular bipartite graph admits an equitable proper k-labelling.
Published: 2021
Full Text: View/download PDF

11. The orthogonal colouring game

Author: Stephan Dominique Andres, Fionn Mc Inerney, Melissa A. Huggan, Richard J. Nowakowski, FernUniversität in Hagen, Dalhousie University [Halifax], Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Computer Science::Computer Science and Game Theory, mutually orthogonal Latin squares, General Computer Science, games on graphs, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Fixed point, scoring game, 01 natural sciences, 2008 MSC, 05C57, 05C15, 05B15, 91A46, 91A4, Graph, Theoretical Computer Science, Combinatorics, 010201 computation theory & mathematics, strictly matched involution, Orthogonal Colouring Game, [INFO]Computer Science [cs], 0101 mathematics, Graph isomorphism, orthogonal graph colouring, Mathematics
Abstract: International audience; We introduce the Orthogonal Colouring Game, in which two players alternately colour vertices (from a choice of m ∈ N colours) of a pair of isomorphic graphs while respecting the properness and the orthogonality of the colouring. Each player aims to maximise her score, which is the number of coloured vertices in the copy of the graph she owns. The main result of this paper is that the second player has a strategy to force a draw in this game for any m ∈ N for graphs that admit a strictly matched involution. An involution σ of a graph G is strictly matched if its fixed point set induces a clique and any non-fixed point v ∈ V (G) is connected with its image σ(v) by an edge. We give a structural characterisation of graphs admitting a strictly matched involution and bounds for the number of such graphs. Examples of such graphs are the graphs associated with Latin squares and sudoku squares.
Published: 2019
Full Text: View/download PDF

12. On the semi-proper orientations of graphs

Author: Ali Dehghan, Frédéric Havet, Carleton University, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: Applied Mathematics, 0211 other engineering and technologies, 021107 urban & regional planning, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Degeneracy (graph theory), Graph, Vertex (geometry), Planar graph, Combinatorics, symbols.namesake, 010201 computation theory & mathematics, Outerplanar graph, Bipartite graph, symbols, Discrete Mathematics and Combinatorics, Mathematics
Abstract: International audience; A weighted orientation of a graph G is a pair (D, w) where D is an orientation of G and w is an arc-weighting of D, that is an application A(D) → N \ {0}. The in-weight of a vertex v in a weighted orientation (D, w), denoted by S (D,w) (v), is the sum of the weights of arcs with head v in D. A semi-proper orientation is a weighted orientation such that two adjacent vertices have different in-weights. The semiproper orientation number of a graph G, denoted by − → χs(G), is min (D,w)∈Γ max v∈V (G) S (D,w) (v), where Γ is the set of all semi-proper orientations of G. A semi-proper orientation (D, w) of a graph G is optimal if max v∈V (G) S (D,w) (v) = − → χs(G). In this work, we show that every graph G has an optimal semi-proper orientation (D, w) such that the weight of each arc is 1 or 2. We then give some bounds on the semi-proper orientation number: we show Mad(G) 2 ≤ − → χs(G) ≤ Mad(G) 2 +χ(G)−1 and δ * (G)+1 2 ≤ − → χs(G) ≤ 2δ * (G) for all graph G, where Mad(G) and δ * (G) are the maximum average degree and the degeneracy of G, respectively. We then deduce that the maximum semi-proper orientation number of a tree is 2, of a cactus is 3, of an outerplanar graph is 4, and of a planar graph is 6. Finally, we consider the computational complexity of associated problems: we show that determining whether − → χs(G) = χ(G) is NP-complete for planar graphs G with − → χs(G) = 2; we also show that deciding whether − → χs(G) ≤ 2 is NP-complete for planar bipartite graphs G.
Published: 2021
Full Text: View/download PDF

13. On BMRN*-colouring of planar digraphs

Author: Foivos Fioravantes, Julien Bensmail, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Côte d'Azur, CNRS, I3S, France, Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), and COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: Mathematics::Combinatorics, General Computer Science, Tdma scheduling, Digraph, Girth (graph theory), Astrophysics::Cosmology and Extragalactic Astrophysics, BMRN*-colouring, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Upper and lower bounds, Theoretical Computer Science, Combinatorics, Planar, Computer Science::Discrete Mathematics, Discrete Mathematics and Combinatorics, planar digraphs, TDMA scheduling, Connection (algebraic framework), Focus (optics), Astrophysics::Galaxy Astrophysics, Mathematics
Abstract: In a recent work, Bensmail, Blanc, Cohen, Havet and Rocha, motivated by applications for TDMA scheduling problems, have introduced the notion of BMRN*-colouring of digraphs, which is a type of arc-colouring with particular colouring constraints. In particular, they gave a special focus to planar digraphs. They notably proved that every planar digraph can be 8-BMRN*-coloured, while there exist planar digraphs for which 7 colours are needed in a BMRN*-colouring. They also proved that the problem of deciding whether a planar digraph can be 3-BMRN*-coloured is NP-hard. In this work, we pursue these investigations on planar digraphs, in particular by answering some of the questions left open by the authors in that seminal work. We exhibit planar digraphs needing 8 colours to be BMRN*-coloured, thus showing that the upper bound of Bensmail, Blanc, Cohen, Havet and Rocha cannot be decreased in general. We also generalize their complexity result by showing that the problem of deciding whether a planar digraph can be k-BMRN*-coloured is NP-hard for every k ∈ {3,...,6}. Finally, we investigate the connection between the girth of a planar digraphs and the least number of colours in its BMRN*-colourings.
Published: 2021
Full Text: View/download PDF

14. Protection numbers in simply generated trees and Pólya trees

Author: Zbigniew Gołębiewski, Isabella Larcher, Bernhard Gittenberger, Małgorzata Sulkowska, Wroclaw University of Science and Technology, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Vienna University of Technology (TU Wien), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Technische Universität Wien
Subjects: Binary tree, Applied Mathematics, media_common.quotation_subject, Computation, Variance (accounting), Expected value, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 16. Peace & justice, Infinity, Tree (graph theory), Vertex (geometry), Combinatorics, [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Discrete Mathematics and Combinatorics, Limit (mathematics), Analysis, Mathematics, media_common
Abstract: We determine the limit of the expected value and the variance of the protection number of the root in simply generated trees, in P?lya trees, and in unlabelled non-plane binary trees, when the number of vertices tends to infinity. Moreover, we compute expectation and variance of the protection number of a randomly chosen vertex in all those tree classes. We obtain exact formulas as sum representations, where the obtained sums are rapidly converging thus allowing an efficient numerical computation of high accuracy.
Published: 2021
Full Text: View/download PDF

15. On Generalisations of the AVD Conjecture to Digraphs

Author: Julien Bensmail, Fionn Mc Inerney, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Algorithmique, Combinatoire et Recherche Opérationnelle (ACRO), Laboratoire d'Informatique et Systèmes (LIS), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), ANR-14-CE25-0006,GAG,Jeux et graphes(2014), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Conjecture, Approximations of π, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Theoretical Computer Science, Combinatorics, 010201 computation theory & mathematics, Digraphs, proper edge-colourings, Discrete Mathematics and Combinatorics, 0101 mathematics, Undirected graph, AVD Conjecture, Mathematics
Abstract: International audience; Given an undirected graph, in the AVD (edge-colouring) Conjecture, the goal is to find a proper edge-colouring with the least number of colours such that every two adjacent vertices are incident to different sets of colours. More precisely, the conjecture says that, a few exceptions apart, every graph G should admit such an edge-colouring with at most $∆(G)+2$ colours. Several aspects of interest behind this problem have been investigated over the recent years, including verifications of the conjecture for particular graph classes, general approximations of the conjecture, and multiple generalisations. In this paper, following a recent work of Sopena and Woźniak, generalisations of the AVD Conjecture to digraphs are investigated. More precisely, four of the several possible ways of generalising the conjecture are focused upon. We completely settle one of our four variants, while, for the three remaining ones, we provide partial results.
Published: 2021
Full Text: View/download PDF

16. The Largest Connected Subgraph Game

Author: Julien Bensmail, Foivos Fioravantes, Nicolas Nisse, Fionn Mc Inerney, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Helmholtz Center for Information Security [Saarbrücken] (CISPA), This work has been supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH, the STIC-AmSud project GALOP, the PHC Xu Guangqi project DESPROGES, and the UCA JEDI Investments in the Future project managed by the National Research Agency (ANR-15-IDEX-01)., Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France, CISPA Helmholtz Center for Information Security, Saarbrücken, Germany, ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), European Project: 725978,SYSTEMATICGRAPH(2017), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), projet SticAm-Sud Galop, ANR-17-EURE-0004,UCA DS4H,UCA Systèmes Numériques pour l'Homme(2017), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), This work has been supported by the European Research Council (ERC) consolidator grant N° 725978 SYSTEMATICGRAPH, H, the STIC-AmSud project GALOP, the PHC Xu Guangqi project DESPROGES, and the UCAjedi Investments in the Future project managed by the National Research Agency (ANR-15-IDEX-01)., COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), and This work has been supported by the European Research Council (ERC) consolidator grant N° 725978 SYSTEMATICGRAPH.
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Computer Science::Computer Science and Game Theory, General Computer Science, 0102 computer and information sciences, 02 engineering and technology, Astrophysics::Cosmology and Extragalactic Astrophysics, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Connection games, 01 natural sciences, Outcome (game theory), PSPACE-complete, Combinatorics, Games on graphs, Scoring games, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, 0202 electrical engineering, electronic engineering, information engineering, Order (group theory), Time complexity, Astrophysics::Galaxy Astrophysics, Mathematics, GI-hard, Applied Mathematics, 020207 software engineering, Computer Science Applications, Vertex (geometry), 010201 computation theory & mathematics, If and only if, Path (graph theory), Bipartite graph, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; This paper introduces the largest connected subgraph game played on an undirected graph G. In each round, Alice first colours an uncoloured vertex of G red, and then, Bob colours an uncoloured vertex of G blue, with all vertices initially uncoloured. Once all the vertices are coloured, Alice (Bob, resp.) wins if there is a red (blue, resp.) connected subgraph whose order is greater than the order of any blue (red, resp.) connected subgraph. We first prove that, if Alice plays optimally, then Bob can never win, and define a large class of graphs (called reflection graphs) in which the game is a draw. We then show that determining the outcome of the game is PSPACE-complete, even in bipartite graphs of small diameter, and that recognising reflection graphs is GI-hard. We also prove that the game is a draw in paths if and only if the path is of even order or has at least 11 vertices, and that Alice wins in cycles if and only if the cycle is of odd length. Lastly, we give an algorithm to determine the outcome of the game in cographs in linear time.
Published: 2021
Full Text: View/download PDF

17. An injective version of the 1-2-3 Conjecture

Author: Binlong Li, Bi Li, Julien Bensmail, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Xidian University, Northwestern Polytechnical University [Xi'an] (NPU), The first author was supported by a funding granted by the program 'Jeunes Talents FRANCE-CHINE'. The second author was supported by the National Natural Science Foundation of China (No. 11701440, 11626181). The third author was supported by the National Natural Science Foundation of China (No. 11601429) and the Fundamental Research Funds for the Central Universities (No. 3102019ghjd003)., Université côte d'azur, Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: Conjecture, 0211 other engineering and technologies, 021107 urban & regional planning, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Injective function, Graph, Theoretical Computer Science, Combinatorics, 010201 computation theory & mathematics, Discrete Mathematics and Combinatorics, Graph labelling, Mathematics
Abstract: In this work, we introduce and study a new graph labelling problem standing as a combination of the 1-2-3 Conjecture and injective colouring of graphs, which also finds connections with the notion of graph irregularity. In this problem, the goal, given a graph G, is to label the edges of G so that every two vertices having a common neighbour get incident to different sums of labels. We are interested in the minimum k such that G admits such a k-labelling. We suspect that almost all graphs G can be labelled this way using labels $$1,\dots ,\Delta (G)$$ . Towards this speculation, we provide bounds on the maximum label value needed in general. In particular, we prove that using labels $$1,\dots ,\Delta (G)$$ is indeed sufficient when G is a tree, a particular cactus, or when its injective chromatic number $$\mathrm{\chi _{\mathrm{i}}}(G)$$ is equal to $$\Delta (G)$$ .
Published: 2021
Full Text: View/download PDF

18. On the signed chromatic number of some classes of graphs

Author: Eric Sopena, Julien Bensmail, Sagnik Sen, Sandip Das, Soumen Nandi, Théo Pierron, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Indian Statistical Institute [Kolkata], Calcutta Institute of Engineering and Management (CIEM), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2, Faculty of Informatics [Brno] (FI / MUNI), Masaryk University [Brno] (MUNI), Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), IIT Dharwad (IITD), Université Côte D'Azur, Université de Bordeaux, Université Lyon 1, Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), ANR-17-CE40-0022,HOSIGRA,Homomorphismes de graphes signés(2017), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
Subjects: FOS: Computer and information sciences, Discrete Mathematics (cs.DM), planar graph, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, symbols.namesake, Simple (abstract algebra), FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Chromatic scale, Graph coloring, 0101 mathematics, Signed graph, Mathematics, Discrete mathematics, 010102 general mathematics, homomorphism of signed graphs, signed chromatic number, Function (mathematics), triangle-free planar graph, 16. Peace & justice, Kn-minor-free graph, Graph, bounded-degree graph, Planar graph, 010201 computation theory & mathematics, symbols, Homomorphism, Combinatorics (math.CO), Computer Science - Discrete Mathematics
Abstract: A signed graph ( G , σ ) is a graph G along with a function σ : E ( G ) → { + , − } . A closed walk of a signed graph is positive (resp., negative) if it has an even (resp., odd) number of negative edges, counting repetitions. A homomorphism of a (simple) signed graph to another signed graph is a vertex-mapping that preserves adjacencies and signs of closed walks. The signed chromatic number of a signed graph ( G , σ ) is the minimum number of vertices | V ( H ) | of a signed graph ( H , π ) to which ( G , σ ) admits a homomorphism. Homomorphisms of signed graphs have been attracting growing attention in the last decades, especially due to their strong connections to the theories of graph coloring and graph minors. These homomorphisms have been particularly studied through the scope of the signed chromatic number. In this work, we provide new results and bounds on the signed chromatic number of several families of signed graphs (planar graphs, triangle-free planar graphs, K n -minor-free graphs, and bounded-degree graphs).
Published: 2020
Full Text: View/download PDF

19. A variant of the Erdős‐Sós conjecture

Author: Maya Stein, David R. Wood, Bruce Reed, Frédéric Havet, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Center for Mathematical Modelling - Centro de Modelamiento Matematico [Santiago] (CMM), Universidad de Chile = University of Chile [Santiago] (UCHILE)-Centre National de la Recherche Scientifique (CNRS), Monash University [Melbourne], Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: Conjecture, Degree (graph theory), 010102 general mathematics, Graph theory, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Combinatorics, 010201 computation theory & mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology, 0101 mathematics, Mathematics
Abstract: International audience; A well-known conjecture of Erdős and Sós states that every graph with average degree exceeding $m−1$ contains every tree with m edges as a subgraph. We propose a variant of this conjecture, which states that every graph of maximum degree exceeding m and minimum degree at least $[\frac{2m}{3}]$ contains every tree with m edges. As evidence for our conjecture we show (i) for every m there is a g(m) such that the weakening of the conjecture obtained by replacing the first m by g(m) holds, and (ii) there is a $\gamma > 0$ such that the weakening of the conjecture obtained by replacing $[\frac{2m} {3}$ by $(1 − \gamma)m$ holds.
Published: 2020
Full Text: View/download PDF

20. Maximizing the expected number of components in an online search of a graph

Author: Fabricio Siqueira Benevides, Małgorzata Sulkowska, Wroclaw University of Science and Technology, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Universidade Federal do Ceará = Federal University of Ceará (UFC), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: 0102 computer and information sciences, Expected value, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Square (algebra), Theoretical Computer Science, Combinatorics, 010104 statistics & probability, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Discrete Mathematics and Combinatorics, Order (group theory), Mathematics - Combinatorics, Hexagonal lattice, Optimal stopping, simple graph, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete mathematics, Connected component, 2-dimensional lattice, [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], secretary problem, optimal stopping, 010201 computation theory & mathematics, Graph (abstract data type), 60G40, 60K35, Constant (mathematics), Mathematics - Probability
Abstract: The following optimal stopping problem is considered. The vertices of a graph $G$ are revealed one by one, in a random order, to a selector. He aims to stop this process at a time $t$ that maximizes the expected number of connected components in the graph $\tilde{G}_t$, induced by the currently revealed vertices. The selector knows $G$ in advance, but different versions of the game are considered depending on the information that he gets about $\tilde{G}_t$. We show that when $G$ has $N$ vertices and maximum degree of order $o(\sqrt{N})$, then the number of components of $\tilde{G}_t$ is concentrated around its mean, which implies that playing the optimal strategy the selector does not benefit much by receiving more information about $\tilde{G}_t$. Results of similar nature were previously obtained by M. Laso\'n for the case where $G$ is a $k$-tree (for constant $k$). We also consider the particular cases where $G$ is a square, triangular or hexagonal lattice, showing that an optimal selector gains $cN$ components and we compute $c$ with an error less than $0.005$ in each case., Comment: 17 pages, 4 figures
Published: 2020
Full Text: View/download PDF

21. Cooperative colorings of trees and of bipartite graphs

Author: Frédéric Havet, Eli Berger, Zilin Jiang, Ron Aharoni, Maria Chudnovsky, Department of Mathematics (TECHNION), Technion - Israel Institute of Technology [Haifa], University of Haifa [Haifa], Columbia University [New York], Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Massachusetts Institute of Technology (MIT), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Vertex (graph theory), 05C15, 05C69, Mathematics::Commutative Algebra, Applied Mathematics, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Theoretical Computer Science, Combinatorics, Computational Theory and Mathematics, Computer Science::Discrete Mathematics, Bipartite graph, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Geometry and Topology, Combinatorics (math.CO), Mathematics
Abstract: Given a system $(G_1, \ldots ,G_m)$ of graphs on the same vertex set $V$, a cooperative coloring is a choice of vertex sets $I_1, \ldots ,I_m$, such that $I_j$ is independent in $G_j$ and $\bigcup_{j=1}^{m}I_j = V$. For a class $\mathcal{G}$ of graphs, let $m_{\mathcal{G}}(d)$ be the minimal $m$ such that every $m$ graphs from $\mathcal{G}$ with maximum degree $d$ have a cooperative coloring. We prove that $\Omega(\log\log d) \le m_\mathcal{T}(d) \le O(\log d)$ and $\Omega(\log d)\le m_\mathcal{B}(d) \le O(d/\log d)$, where $\mathcal{T}$ is the class of trees and $\mathcal{B}$ is the class of bipartite graphs., Comment: 8 pages, 2 figures, accepted to the Electronic Journal of Combinatorics, corrections suggested by the referees have been incorporated
Published: 2020

22. Finding a Bounded-Degree Expander Inside a Dense One

Author: Emanuele Natale, Andrea E. F. Clementi, Luca Trevisan, Luca Becchetti, Francesco Pasquale, Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome], Università degli Studi di Roma Tor Vergata [Roma], Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centre National de la Recherche Scientifique (CNRS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Department of Electrical Engineering and Computer Sciences (Berkeley EECS), European Project: 834861,H2020-EU.1.1.,834861,SO-ReCoDi(2019), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: FOS: Computer and information sciences, Graph theory, Peer to peer networks, Satellites, Conjecture, Degree (graph theory), EXPANDER GRAPHS, SPARSIFICATION, Binary logarithm, DISTRIBUTED ALGORITHMS, Combinatorics, Treewidth, Settore INF/01, Computer Science - Distributed, Parallel, and Cluster Computing, Bounded function, DISTRIBUTED ALGORITHMS, EXPANDER GRAPHS, SPARSIFICATION, Bipartite graph, Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Time complexity, SIMPLE algorithm, Mathematics
Abstract: International audience; It follows from the Marcus-Spielman-Srivastava proof of the Kadison-Singer conjecture that if $G=(V,E)$ is a $\Delta$-regular dense expander then there is an edge-induced subgraph $H=(V,E_H)$ of $G$ of constant maximum degree which is also an expander. As with other consequences of the MSS theorem, it is not clear how one would explicitly construct such a subgraph. We show that such a subgraph (although with quantitatively weaker expansion and near-regularity properties than those predicted by MSS) can be constructed with high probability in linear time, via a simple algorithm. Our algorithm allows a distributed implementation that runs in $\mathcal O(\log n)$ rounds and does $\mathcal O(n)$ total work with high probability. The analysis of the algorithm is complicated by the complex dependencies that arise between edges and between choices made in different rounds. We sidestep these difficulties by following the combinatorial approach of counting the number of possible random choices of the algorithm which lead to failure. We do so by a compression argument showing that such random choices can be encoded with a non-trivial compression. Our algorithm bears some similarity to the way agents construct a communication graph in a peer-to-peer network, and, in the bipartite case, to the way agents select servers in blockchain protocols.
Published: 2020
Full Text: View/download PDF

23. Further Evidence Towards the Multiplicative 1-2-3 Conjecture

Author: Julien Bensmail, Hervé Hocquard, Eric Sopena, Dimitri Lajou, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université côte d'azur, Université de bordeaux, Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, Property (philosophy), Discrete Mathematics (cs.DM), 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, product version, Combinatorics, multiset version, FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Mathematics, 4-chromatic graphs, Multiset, Conjecture, 1-2-3 Conjecture, Applied Mathematics, Multiplicative function, 021107 urban & regional planning, Graph, 010201 computation theory & mathematics, Product (mathematics), Combinatorics (math.CO), Computer Science - Discrete Mathematics
Abstract: International audience; The product version of the 1-2-3 Conjecture, introduced by Skowronek-Kaziów in 2012, states that, a few obvious exceptions apart, all graphs can be 3-edge-labelled so that no two adjacent vertices get incident to the same product of labels. To date, this conjecture was mainly verified for complete graphs and 3-colourable graphs. As a strong support to the conjecture, it was also proved that all graphs admit such 4-labellings. In this work, we investigate how a recent proof of the multiset version of the 1-2-3 Conjecture by Vučković can be adapted to prove results on the product version. We prove that 4-chromatic graphs verify the product version of the 1-2-3 Conjecture. We also prove that for all graphs we can design 3-labellings that almost have the desired property. This leads to a new problem, that we solve for some graph classes.
Published: 2020
Full Text: View/download PDF

24. Study of a Combinatorial Game in Graphs Through Linear Programming

Author: Stéphane Pérennes, Fionn Mc Inerney, Nicolas Nisse, Nathann Cohen, Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Laboratoire de Recherche en Informatique (LRI), CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-13-BS02-0007,Stint,Structures Interdites(2013), ANR-11-LABX-0031,UCN@SOPHIA,Réseau orienté utilisateur(2011), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), EA AlDyNet, Inria Sophia Antipolis, and Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], General Computer Science, Linear programming, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Combinatorial game theory, Turn-by-turn games in graphs, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Upper and lower bounds, Combinatorics, Indifference graph, Chordal graph, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 0202 electrical engineering, electronic engineering, information engineering, Grid, Linear Programming, Graph algorithms, Mathematics, Discrete mathematics, 000 Computer science, knowledge, general works, Applied Mathematics, Spy game, Domination, Graph, Computer Science Applications, 010201 computation theory & mathematics, Theory of computation, Computer Science, Cops and Robber games, 020201 artificial intelligence & image processing, Graphs, Tree
Abstract: International audience; In the Spy game played on a graph G, a single spy travels the vertices of G at speed s, while multiple slow guards strive to have, at all times, one of them within distance d of that spy. In order to determine the smallest number of guards necessary for this task, we analyze the game through a Linear Programming formulation and the fractional strategies it yields for the guards. We then show the equivalence of fractional and integral strategies in trees. This allows us to design a polynomial-time algorithm for computing an optimal strategy in this class of graphs. Using duality in Linear Programming, we also provide non-trivial bounds on the fractional guard-number of grids and tori, which gives a lower bound for the integral guard-number in these graphs. We believe that the approach using fractional relaxation and Linear Programming is promising to obtain new results in the field of combinatorial games.
Published: 2020
Full Text: View/download PDF

25. Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties

Author: Joergen Bang-Jensen, Anders Yeo, Matthias Kriesell, Frédéric Havet, University of Southern Denmark (SDU), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Technische Universität Ilmenau (TU ), University of Johannesburg [South Africa] (UJ), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), and ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015)
Subjects: strong connectivity, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], semicomplete digraph, 05C20, 05C15, edge-disjoint spanning trees, Combinatorics, Integer, Computer Science::Discrete Mathematics, FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, arc-connectivity, majority colouring, ComputingMilieux_MISCELLANEOUS, Mathematics, Spanning tree, Conjecture, Mathematics::Combinatorics, Degree (graph theory), Digraph, Directed graph, Vertex (geometry), bipartite graph, Bipartite graph, Geometry and Topology, Combinatorics (math.CO), edge-connectivity
Abstract: Generalizing well-known results of Erdős and Lovász, we show that every graph (Formula presented.) contains a spanning (Formula presented.) -partite subgraph (Formula presented.) with (Formula presented.), where (Formula presented.) is the edge-connectivity of (Formula presented.). In particular, together with a well-known result due to Nash-Williams and Tutte, this implies that every 7-edge-connected graph contains a spanning bipartite graph whose edge set decomposes into two edge-disjoint spanning trees. We show that this is best possible as it does not hold for infinitely many 6-edge-connected graphs. For directed graphs, it was shown by Bang-Jensen et al. that there is no (Formula presented.) such that every (Formula presented.) -arc-connected digraph has a spanning strong bipartite subdigraph. We prove that every strong digraph has a spanning strong 3-partite subdigraph and that every strong semicomplete digraph on at least six vertices contains a spanning strong bipartite subdigraph. We generalize this result to higher connectivities by proving that, for every positive integer (Formula presented.), every (Formula presented.) -arc-connected digraph contains a spanning ((Formula presented.))-partite subdigraph which is (Formula presented.) -arc-connected and this is best possible. A conjecture by Kreutzer et al. implies that every digraph of minimum out-degree (Formula presented.) contains a spanning 3-partite subdigraph with minimum out-degree at least (Formula presented.). We prove that the bound (Formula presented.) would be best possible by providing an infinite class of digraphs with minimum out-degree (Formula presented.) which do not contain any spanning 3-partite subdigraph in which all out-degrees are at least (Formula presented.). We also prove that every digraph of minimum semidegree at least (Formula presented.) contains a spanning 6-partite subdigraph in which every vertex has in- and out-degree at least (Formula presented.).
Published: 2020
Full Text: View/download PDF

26. On the Complexity of Computing Treebreadth

Author: Guillaume Ducoffe, Nicolas Nisse, Sylvain Legay, National Institute for Research and Development in Informatics [Bucharest] (ICI), University of Bucharest (UniBuc), Laboratoire de Recherche en Informatique (LRI), CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Veli Mäkinen, Simon J. Puglisi, Leena Salmela, ANR-13-BS02-0007,Stint,Structures Interdites(2013), and ANR-11-LABX-0031,UCN@SOPHIA,Réseau orienté utilisateur(2011)
Subjects: Vertex (graph theory), [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], General Computer Science, Computational complexity theory, ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Comparability graph, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, law.invention, Combinatorics, symbols.namesake, Pathwidth, Maximum diameter, law, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS, Outerplanar graph, Line graph, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 0202 electrical engineering, electronic engineering, information engineering, Cograph, Forbidden graph characterization, Mathematics, Block graph, Discrete mathematics, Applied Mathematics, Tree decomposition, Graph, Computer Science Applications, Planar graph, 010201 computation theory & mathematics, Theory of computation, Bipartite graph, symbols, 020201 artificial intelligence & image processing, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; During the last decade, metric properties of the bags of tree decompositions of graphs have been studied. Roughly, the length and the breadth of a tree decomposition are the maximum diameter and radius of its bags respectively. The treelength and the treebreadth of a graph are the minimum length and breadth of its tree decompositions respectively. Pathlength and pathbreadth are defined similarly for path decompositions. In this paper, we answer open questions of [Dragan and Köhler, Algorithmica 2014] and [Dragan, Köhler and Leitert, SWAT 2014] about the computational complexity of treebreadth, pathbreadth and pathlength. Namely, we prove that computing these graph invariants is NP-hard. We further investigate graphs with treebreadth one, i.e., graphs that admit a tree decomposition where each bag has a dominating vertex. We show that it is NP-complete to decide whether a graph belongs to this class. We then prove some structural properties of such graphs which allows us to design polynomial-time algorithms to decide whether a bipartite graph, resp., a planar graph (or more generally, a triangle-free graph, resp., a K 3,3-minor-free graph), has treebreadth one.
Published: 2020
Full Text: View/download PDF

27. 1-2-3 Conjecture in Digraphs: More Results and Directions

Author: Kasper Szabo Lyngsie, Julien Bensmail, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Technical University of Denmark [Lyngby] (DTU), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), and Danmarks Tekniske Universitet = Technical University of Denmark (DTU)
Subjects: Conjecture, 1-2-3 Conjecture, Statement (logic), Applied Mathematics, 0211 other engineering and technologies, 021107 urban & regional planning, Digraph, Field (mathematics), 0102 computer and information sciences, 02 engineering and technology, Complexity, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, Choosability, 010201 computation theory & mathematics, Bounds, Small class, 1–2–3 Conjecture, Discrete Mathematics and Combinatorics, Directed variants, Mathematics
Abstract: International audience; Horňak, Przybyło and Woźniak recently proved that, a small class of obvious exceptions apart, every digraph can be 4-arc-weighted so that, for every arc u->v, the sum of weights incoming to u is different from the sum of weights outgoing from v. They conjectured a stronger result, namely that the same statement with 3 instead of 4 should also be true. We verify this conjecture in this work. This work takes place in a recent "quest" towards a directed version of the 1-2-3 Conjecture, the variant above being one of the last introduced ones. We take the occasion of this work to establish a summary of all results known in this field, covering known upper bounds, complexity aspects, and choosability. On the way we prove additional results which were missing in the whole picture. We also mention the aspects that remain open.
Published: 2020
Full Text: View/download PDF

28. Powers of paths in tournaments

Author: Alex Scott, Benny Sudakov, Jacob Fox, Frédéric Havet, Nemanja Draganić, Dániel Korándi, François Dross, António Girão, David Munhá Correia, William Lochet, Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich] (ETH Zürich), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Stanford University, Heidelberg University, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), University of Oxford [Oxford], University of Bergen (UiB), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), and University of Oxford
Subjects: Statistics and Probability, Applied Mathematics, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Square (algebra), Theoretical Computer Science, Power (physics), Combinatorics, Computational Theory and Mathematics, 010201 computation theory & mathematics, Path (graph theory), FOS: Mathematics, Mathematics - Combinatorics, Tournament, Combinatorics (math.CO), 0101 mathematics, Mathematics
Abstract: In this short note we prove that every tournament contains the $k$-th power of a directed path of linear length. This improves upon recent results of Yuster and of Gir\~ao. We also give a complete solution for this problem when $k=2$, showing that there is always a square of a directed path of length $\lceil 2n/3 \rceil-1$, which is best possible., Comment: 6 pages; updated affiliations; accepted at CPC
Published: 2020
Full Text: View/download PDF

29. Decomposing degenerate graphs into locally irregular subgraphs

Author: Julien Bensmail, François Dross, Nicolas Nisse, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), and ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
Subjects: Conjecture, degenerate graphs, k-trees, 010102 general mathematics, Degenerate energy levels, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Degeneracy (graph theory), Graph, planar graphs, Theoretical Computer Science, Planar graph, Combinatorics, symbols.namesake, 010201 computation theory & mathematics, symbols, Bipartite graph, Discrete Mathematics and Combinatorics, Partition (number theory), locally irregular decompositions, 0101 mathematics, Mathematics, cacti
Abstract: International audience; A (undirected) graph is locally irregular if no two of its adjacent vertices have the same degree. A decomposition of a graph G into k locally irregular subgraphs is a partition E_1,...,E_k of E(G) into k parts each of which induces a locally irregular subgraph. Not all graphs decompose into locally irregular subgraphs; however, it was conjectured that, whenever a graph does, it should admit such a decomposition into at most three locally irregular subgraphs. This conjecture was verified for a few graph classes in recent years.This work is dedicated to the decomposability of degenerate graphs with low degeneracy. Our main result is that decomposable k-degenerate graphs decompose into at most 3k+1 locally irregular subgraphs, which improves on previous results whenever k≤9. We improve this result further for some specific classes of degenerate graphs, such as bipartite cacti, k-trees, and planar graphs. Although our results provide only little progress towards the leading conjecture above, the main contribution of this work is rather the decomposition schemes and methods we introduce to prove these results.
Published: 2020
Full Text: View/download PDF

30. Explicit Linear Kernels for Packing Problems

Author: Valentin Garnero, Dimitrios M. Thilikos, Christophe Paul, Ignasi Sau, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)
Subjects: FOS: Computer and information sciences, Discrete Mathematics (cs.DM), General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Parameterized complexity, G.2.2, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Constructive, packing problems, Combinatorics, symbols.namesake, protrusion replacement, linear kernels, Computer Science - Data Structures and Algorithms, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), 05C85, graph minors, Mathematics, Discrete mathematics, dynamic pro- gramming, Applied Mathematics, F.2.2, Graph, Computer Science Applications, Planar graph, Vertex (geometry), Packing problems, 010201 computation theory & mathematics, Theory of computation, symbols, 020201 artificial intelligence & image processing, Pairwise comparison, Combinatorics (math.CO), MathematicsofComputing_DISCRETEMATHEMATICS, Computer Science - Discrete Mathematics
Abstract: During the last years, several algorithmic meta-theorems have appeared (Bodlaender et al. [FOCS 2009], Fomin et al. [SODA 2010], Kim et al. [ICALP 2013]) guaranteeing the existence of linear kernels on sparse graphs for problems satisfying some generic conditions. The drawback of such general results is that it is usually not clear how to derive from them constructive kernels with reasonably low explicit constants. To fill this gap, we recently presented [STACS 2014] a framework to obtain explicit linear kernels for some families of problems whose solutions can be certified by a subset of vertices. In this article we enhance our framework to deal with packing problems, that is, problems whose solutions can be certified by collections of subgraphs of the input graph satisfying certain properties. ${\mathcal F}$-Packing is a typical example: for a family ${\mathcal F}$ of connected graphs that we assume to contain at least one planar graph, the task is to decide whether a graph $G$ contains $k$ vertex-disjoint subgraphs such that each of them contains a graph in ${\mathcal F}$ as a minor. We provide explicit linear kernels on sparse graphs for the following two orthogonal generalizations of ${\mathcal F}$-Packing: for an integer $\ell \geq 1$, one aims at finding either minor-models that are pairwise at distance at least $\ell$ in $G$ ($\ell$-${\mathcal F}$-Packing), or such that each vertex in $G$ belongs to at most $\ell$ minors-models (${\mathcal F}$-Packing with $\ell$-Membership). Finally, we also provide linear kernels for the versions of these problems where one wants to pack subgraphs instead of minors., 43 pages, 4 figures
Published: 2018
Full Text: View/download PDF

31. Minimum size tree-decompositions

Author: Fatima Zahra Moataz, Karol Suchan, Nicolas Nisse, Bi Li, Chinese Academy of Sciences [Beijing] (CAS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Faculty of Applied Mathematics [Krakow], AGH University of Science and Technology [Krakow, PL] (AGH UST), Facultad de Ingeniería y Ciencias [Santiago], Universidad Adolfo Ibáñez [Santiago], ANR-13-BS02-0007,Stint,Structures Interdites(2013), Xidian University, Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Discrete mathematics, Minimum size tree-decomposition, Applied Mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, NP-hard, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Tree-depth, 01 natural sciences, 1-planar graph, Tree decomposition, Graph, Treewidth, Combinatorics, 010201 computation theory & mathematics, Chordal graph, 020204 information systems, Partial k-tree, treewidth, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Mathematics
Abstract: International audience; Tree-decompositions are the cornerstone of many dynamic programming algorithms for solving graph problems. Since the complexity of such algorithms generally depends exponentially on the width (size of the bags) of the decomposition, much work has been devoted to compute tree-decompositions with small width. However, practical algorithms computing tree-decompositions only exist for graphs with treewidth less than 4. In such graphs, the time-complexity of dynamic programming algorithms is dominated by the size (number of bags) of the tree-decompositions. It is then interesting to minimize the size of the tree-decompositions. In this extended abstract, we consider the problem of computing a tree-decomposition of a graph with width at most k and minimum size. We prove that the problem is NP-complete for any fixed k ≥ 4 and polynomial for k ≤ 2; for k = 3, we show that it is polynomial in the class of trees and 2-connected outerplanar graphs.
Published: 2018
Full Text: View/download PDF

32. Spy-game on graphs: Complexity and simple topologies

Author: Nathann Cohen, Nicolas Nisse, Rudini Menezes Sampaio, Nícolas A. Martins, Stéphane Pérennes, Fionn Mc Inerney, Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Laboratoire de Recherche en Informatique (LRI), CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-13-BS02-0007,Stint,Structures Interdites(2013), ANR-11-LABX-0031,UCN@SOPHIA,Réseau orienté utilisateur(2011), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: General Computer Science, Computational complexity theory, 010102 general mathematics, Minimum distance, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Network topology, 01 natural sciences, PSPACE-hard, Graph, Theoretical Computer Science, Vertex (geometry), Combinatorics, 010201 computation theory & mathematics, Dominating set, Cops and Robber games, [INFO]Computer Science [cs], [MATH]Mathematics [math], 0101 mathematics, Graphs, Mathematics
Abstract: International audience; We define and study the following two-player game on a graph G. Let k ∈ N *. A set of k guards is occupying some vertices of G while one spy is standing at some node. At each turn, first the spy may move along at most s edges, where s ∈ N * is his speed. Then, each guard may move along one edge. The spy and the guards may occupy the same vertices. The spy has to escape the surveillance of the guards, i.e., must reach a vertex at distance more than d ∈ N (a predefined distance) from every guard. Can the spy win against k guards? Similarly, what is the minimum distance d such that k guards may ensure that at least one of them remains at distance at most d from the spy? This game generalizes two well-studied games: Cops and robber games (when s = 1) and Eternal Dominating Set (when s is unbounded). We consider the computational complexity of the problem, showing that it is NP-hard (for every speed s and distance d) and that some variant of it is PSPACE-hard in DAGs. Then, we establish tight tradeoffs between the number of guards, the speed s of the spy and the required distance d when G is a path or a cycle.
Published: 2018
Full Text: View/download PDF

33. On locally irregular decompositions of subcubic graphs

Author: Olivier Baudon, Eric Sopena, Julien Bensmail, Mohammed Senhaji, Hervé Hocquard, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2
Subjects: Connected component, Discrete mathematics, Conjecture, General Mathematics, lcsh:T57-57.97, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Combinatorics, Indifference graph, subcubic graphs, 010201 computation theory & mathematics, Chordal graph, locally irregular edge-colouring, lcsh:Applied mathematics. Quantitative methods, Partition (number theory), 0101 mathematics, ComputingMilieux_MISCELLANEOUS, irregular chromatic index, Mathematics
Abstract: A graph $G$ is locally irregular if every two adjacent vertices of $G$ have different degrees. A locally irregular decomposition of $G$ is a partition $E_1,\dots,E_k$ of $E(G)$ such that each $G[E_i]$ is locally irregular. Not all graphs admit locally irregular decompositions, but for those who are decomposable, in that sense, it was conjectured by Baudon, Bensmail, Przybyło and Woźniak that they decompose into at most 3 locally irregular graphs. Towards that conjecture, it was recently proved by Bensmail, Merker and Thomassen that every decomposable graph decomposes into at most 328 locally irregular graphs. We here focus on locally irregular decompositions of subcubic graphs, which form an important family of graphs in this context, as all non-decomposable graphs are subcubic. As a main result, we prove that decomposable subcubic graphs decompose into at most 5 locally irregular graphs, and only at most 4 when the maximum average degree is less than $\frac{12}{5}$. We then consider weaker decompositions, where subgraphs can also include regular connected components, and prove the relaxations of the conjecture above for subcubic graphs.
Published: 2018
Full Text: View/download PDF

34. Minimum density of identifying codes of king grids

Author: Rennan Dantas, Frédéric Havet, Rudini Menezes Sampaio, Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Discrete mathematics, Applied Mathematics, Discharging method, Neighbourhood (graph theory), identifying codes, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Theoretical Computer Science, Combinatorics, king grids, Discharging Method, 010201 computation theory & mathematics, Identifying code, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, King grid, Minimum density, Mathematics
Abstract: A set C ⊆ V ( G ) is an identifying code in a graph G if for all v ∈ V ( G ) , C [ v ] ≠ ∅ , and for all distinct u , v ∈ V ( G ) , C [ u ] ≠ C [ v ] , where C [ v ] = N [ v ] ∩ C and N [ v ] denotes the closed neighbourhood of v in G. The minimum density of an identifying code in G is denoted by d ⁎ ( G ) . In this paper, we study the density of king grids which are strong product of two paths. We show that for every king grid G , d ⁎ ( G ) ≥ 2 / 9 . In addition, we show this bound is attained only for king grids which are strong products of two infinite paths. Given k ≥ 3 , we denote by K k the (infinite) king strip with k rows. We prove that d ⁎ ( K 3 ) = 1 / 3 , d ⁎ ( K 4 ) = 5 / 16 , d ⁎ ( K 5 ) = 4 / 15 and d ⁎ ( K 6 ) = 5 / 18 . We also prove that 2 9 + 8 81 k ≤ d ⁎ ( K k ) ≤ 2 9 + 4 9 k for every k ≥ 7 .
Published: 2017
Full Text: View/download PDF

35. Applying clique-decomposition for computing Gromov hyperbolicity

Author: David Coudert, Guillaume Ducoffe, Nathann Cohen, Aurélien Lancin, Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Laboratoire de Mathématiques Informatique et Applications (LAMIA), Université des Antilles (UA), ANR-13-BS02-0007,Stint,Structures Interdites(2013), ANR-11-LABX-0031,UCN@SOPHIA,Réseau orienté utilisateur(2011), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and Laboratoire de Mathématiques Informatique et Applications [UR1_1] (LAMIA)
Subjects: graph algorithms, 0301 basic medicine, Mathematics::Dynamical Systems, General Computer Science, Computation, MathematicsofComputing_NUMERICALANALYSIS, 0102 computer and information sciences, 01 natural sciences, Theoretical Computer Science, Combinatorics, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], 03 medical and health sciences, Gromov hyperbolicity, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, Outerplanar graph, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, Graph algorithms, ComputingMethodologies_COMPUTERGRAPHICS, Mathematics, outerplanar graphs, Discrete mathematics, Substitution method, Complex network, Mathematics::Geometric Topology, Graph, 030104 developmental biology, 010201 computation theory & mathematics, clique-decomposition, Biological network, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; Given a graph, its hyperbolicity is a measure of how close its distance distribution is to the one of a tree. This parameter has gained recent attention in the analysis of some graph algorithms and the classification of complex networks. We study on practical improvements for the computation of hyperbolicity in large graphs. Precisely, we investigate on relations between the hyperbolicity of a graph G and the hyperbolicity of its atoms, that are the subgraphs output by the clique-decomposition invented by Tarjan [51, 65]. We prove that the maximum hyperbolicity taken over the atoms is at most one unit off from the hyperbol-icity of G and the bound is sharp. We also give an algorithm to slightly modify the atoms, called the " substitution method " , which is at no extra cost than computing the clique-decomposition, and so that the maximum hyperbolicity taken over the resulting graphs is exactly the hyperbolicity of the input graph G. An experimental evaluation of our method for computing the hyperbolicity of a given graph from its atoms is provided for collaboration networks and biological networks. Finally, on a more theoretical side, we deduce from our results the first linear-time algorithm for computing the hyperbolicity of an outerplanar graph.
Published: 2017
Full Text: View/download PDF

36. Polyhedral results on the stable set problem in graphs containing even or odd pairs

Author: Bruce Reed, Marco E. Lübbecke, Jonas Witt, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Rheinisch-Westfälische Technische Hochschule Aachen (RWTH), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and Rheinisch-Westfälische Technische Hochschule Aachen University (RWTH)
Subjects: Discrete mathematics, General Mathematics, Numerical analysis, 010102 general mathematics, Structure (category theory), Strong perfect graph theorem, Polytope, 0102 computer and information sciences, Characterization (mathematics), Stable set problem, 01 natural sciences, Combinatorics, Computer Science::Graphics, 010201 computation theory & mathematics, Independent set, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Odd graph, [MATH]Mathematics [math], 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Software, Mathematics
Abstract: Even and odd pairs are important tools in the study of perfect graphs and were instrumental in the proof of the Strong Perfect Graph Theorem. We suggest that such pairs impose a lot of structure also in arbitrary, not just perfect graphs. To this end, we show that the presence of even or odd pairs in graphs imply a special structure of the stable set polytope. In fact, we give a polyhedral characterization of even and odd pairs.
Published: 2017
Full Text: View/download PDF

37. A proof of the Barát–Thomassen conjecture

Author: Tien-Nam Le, Stéphan Thomassé, Martin Merker, Ararat Harutyunyan, Julien Bensmail, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Danmarks Tekniske Universitet = Technical University of Denmark (DTU), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Technical University of Denmark [Lyngby] (DTU)
Subjects: Elliott–Halberstam conjecture, Barát-Thomassen Conjecture, abc conjecture, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Collatz conjecture, Combinatorics, Tree-decomposition, Discrete Mathematics and Combinatorics, large edge-connectivity, 0101 mathematics, Lonely runner conjecture, Mathematics, Discrete mathematics, Conjecture, 010102 general mathematics, 16. Peace & justice, Tree decomposition, Graph, Barát-Thomassen conjecture, Computational Theory and Mathematics, Large edge-connectivity, tree-decomposition, 010201 computation theory & mathematics, Beal's conjecture
Abstract: International audience; The Barát-Thomassen conjecture asserts that for every tree T on m edges, there exists a constant k T such that every k T-edge-connected graph with size divisible by m can be edge-decomposed into copies of T. So far this conjecture has only been verified when T is a path or when T has diameter at most 4. Here we prove the full statement of the conjecture.
Published: 2017
Full Text: View/download PDF

38. Exclusive graph searching vs. pathwidth

Author: Nicolas Nisse, Euripides Markou, Stéphane Pérennes, Department of Computer Science & Biomedical Informatics [Galaneika], University of Thessaly [Volos] (UTH), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), ANR-13-BS02-0007,Stint,Structures Interdites(2013), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], 0211 other engineering and technologies, Comparability graph, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, law.invention, Combinatorics, graph searching, Pathwidth, law, Outerplanar graph, Line graph, Graph minor, Split graph, Graph property, Mathematics, Discrete mathematics, 021103 operations research, pathwidth, Computer Science Applications, Computational Theory and Mathematics, 010201 computation theory & mathematics, Null graph, MathematicsofComputing_DISCRETEMATHEMATICS, Information Systems
Abstract: International audience; In Graph Searching, a team of searchers aims at capturing an invisible fugitive moving arbitrarily fast in a graph. Equivalently, the searchers try to clear a contaminated network. The problem is to compute the minimum number of searchers required to accomplish this task. Several variants of Graph Searching have been studied mainly because of their close relationship with the pathwidth of a graph. Blin et al. defined the Exclusive Graph Searching where searchers cannot " jump " and no node can be occupied by more than one searcher. In this paper, we study the complexity of this new variant. We show that the problem is NP-hard in planar graphs with maximum degree 3 and it can be solved in linear-time in the class of cographs. We also show that monotone Exclusive Graph Searching is NP-complete in split graphs where Pathwidth is known to be solvable in polynomial time. Moreover, we prove that monotone Exclusive Graph Searching is in P in a subclass of star-like graphs where Pathwidth is known to be NP-hard. Hence, the computational complexities of monotone Exclusive Graph Searching and Pathwidth cannot be compared. This is the first variant of Graph Searching for which such a difference is proved.
Published: 2017
Full Text: View/download PDF

39. How to determine if a random graph with a fixed degree sequence has a giant component

Author: Guillem Perarnau, Dieter Rautenbach, Bruce Reed, Felix Joos, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), IRATO / Kawarabayashi Large Graph Project [Japan], National Institute of Informatics (NII), Instituto Nacional de Matemática Pura e Aplicada (IMPA), Department of Mathematics [Birmingham, Alabama], University of Alabama at Birmingham [ Birmingham] (UAB), Institut für Optimierung und Operations Research, Universität Ulm - Ulm University [Ulm, Allemagne], Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics, Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), and Instituto Nacional de matematica pura e aplicada
Subjects: FOS: Computer and information sciences, Statistics and Probability, Vertex (graph theory), Discrete Mathematics (cs.DM), 0102 computer and information sciences, Type (model theory), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Lambda, 01 natural sciences, Giant component, Combinatorics, 010104 statistics & probability, FOS: Mathematics, Mathematics - Combinatorics, [INFO]Computer Science [cs], 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete mathematics, High probability, Random graph, Degree (graph theory), Grafs, Teoria de, Probability (math.PR), Complex network, Vertex (geometry), Graph theory, 010201 computation theory & mathematics, Bounded function, Graph (abstract data type), Combinatorics (math.CO), Statistics, Probability and Uncertainty, Heuristic argument, Mathematics - Probability, Analysis, Computer Science - Discrete Mathematics, Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs [Àrees temàtiques de la UPC]
Abstract: For a fixed degree sequence $\mathcal{D}=(d_1,...,d_n)$, let $G(\mathcal{D})$ be a uniformly chosen (simple) graph on $\{1,...,n\}$ where the vertex $i$ has degree $d_i$. In this paper we determine whether $G(\mathcal{D})$ has a giant component with high probability, essentially imposing no conditions on $\mathcal{D}$. We simply insist that the sum of the degrees in $\mathcal{D}$ which are not 2 is at least $\lambda(n)$ for some function $\lambda$ going to infinity with $n$. This is a relatively minor technical condition, and when $\mathcal{D}$ does not satisfy it, both the probability that $G(\mathcal{D})$ has a giant component and the probability that $G(\mathcal{D})$ has no giant component are bounded away from $1$., Comment: 42 pages, to appear in Probability Theory and Related Fields
Published: 2017
Full Text: View/download PDF

40. A short note on the complexity of computing strong pathbreadth

Author: Guillaume Ducoffe, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Vertex (graph theory), Conjecture, graph theory, Graph theory, 0102 computer and information sciences, 02 engineering and technology, 16. Peace & justice, 01 natural sciences, Graph, Computer Science Applications, Theoretical Computer Science, Combinatorics, strong pathbreadth, path decomposition, 010201 computation theory & mathematics, Signal Processing, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, NP-complete, acyclic clustering, Information Systems, Mathematics
Abstract: International audience; The strong pathbreadth of a given graph G is the minimum ρ such that G admits a Robertson and Seymour's path decomposition where every bag is the complete ρ-neighbourhood of some vertex in G. We prove that deciding whether a given graph has strong pathbreadth at most one is NP-complete. The latter answers negatively to a conjecture of [Leitert and Dragan, CO-COA'16].
Published: 2018
Full Text: View/download PDF

41. Edge Weights and Vertex Colours: Minimizing Sum Count

Author: Eric Sopena, Hervé Hocquard, Julien Bensmail, Olivier Baudon, Mohammed Senhaji, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: Applied Mathematics, 0211 other engineering and technologies, 021107 urban & regional planning, 0102 computer and information sciences, 02 engineering and technology, Decision problem, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Vertex (geometry), Combinatorics, 010201 computation theory & mathematics, Bounded function, Bipartite graph, Discrete Mathematics and Combinatorics, Chromatic scale, Mathematics
Abstract: Neighbour-sum-distinguishing edge-weightings are a way to “encode” proper vertex-colourings via the sums of weights incident to the vertices. Over the last decades, this notion has been attracting, in the context of several conjectures, ingrowing attention dedicated, notably, to understanding, which weights are needed to produce neighbour-sum-distinguishing edge-weightings for a given graph. This work is dedicated to investigating another related aspect, namely the minimum number of distinct sums/colours we can produce via a neighbour-sum-distinguishing edge-weighting of a given graph G , and the role of the assigned weights in that context. Clearly, this minimum number is bounded below by the chromatic number χ ( G ) of G . When using weights of Z , we show that, in general, we can produce neighbour-sum-distinguishing edge-weightings generating χ ( G ) distinct sums, except in the peculiar case where G is a balanced bipartite graph, in which case χ ( G ) + 1 distinct sums can be generated. These results are best possible. When using k consecutive weights 1 , … , k , we provide both lower and upper bounds, as a function of the maximum degree Δ , on the maximum least number of sums that can be generated for a graph with maximum degree Δ . For trees, which, in general, admit neighbour-sum-distinguishing 2-edge-weightings, we prove that this maximum, when using weights 1 and 2, is of order 2 log 2 Δ . Finally, we also establish the NP -hardness of several decision problems related to these questions.
Published: 2019

42. Decomposability of graphs into subgraphs fulfilling the 1-2-3 Conjecture

Author: Julien Bensmail, Jakub Przybyło, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), AGH University of Science and Technology [Krakow, PL] (AGH UST), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: Conjecture, locally irregular graph, 1-2-3 Conjecture, Applied Mathematics, 0211 other engineering and technologies, 021107 urban & regional planning, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Upper and lower bounds, Graph, Combinatorics, 010201 computation theory & mathematics, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Regular graph, Combinatorics (math.CO), graph decomposition, Lovász local lemma, Mathematics
Abstract: The well-known 1-2-3 Conjecture asserts that the edges of every graph without isolated edges can be weighted with $1$, $2$ and $3$ so that adjacent vertices receive distinct weighted degrees. This is open in general. We prove that every $d$-regular graph, $d\geq 2$, can be decomposed into at most $2$ subgraphs (without isolated edges) fulfilling the 1-2-3 Conjecture if $d\notin\{10,11,12,13,15,17\}$, and into at most $3$ such subgraphs in the remaining cases. Additionally, we prove that in general every graph without isolated edges can be decomposed into at most $24$ subgraphs fulfilling the 1-2-3 Conjecture, improving the previously best upper bound of $40$. Both results are partly based on applications of the Lov\'asz Local Lemma., Comment: 13 pages
Published: 2019
Full Text: View/download PDF

43. On the Unavoidability of Oriented Trees

Author: François Dross, Frédéric Havet, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), Université Nice Sophia Antipolis (1965 - 2019) (UNS), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Arborescence, General Computer Science, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Unavoidable, Tree (descriptive set theory), oriented trees, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Order (group theory), Tournament, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, Oriented tree, 010102 general mathematics, Ramsey theory, 020207 software engineering, Digraph, unavoidability, Computational Theory and Mathematics, 010201 computation theory & mathematics, Computer Science - Discrete Mathematics
Abstract: A digraph is n-unavoidable if it is contained in every tournament of order n. We first prove that every arborescence of order n with k leaves is ( n + k − 1 ) -unavoidable. We then prove that every oriented tree of order n ( n ≥ 2 ) with k leaves is ( 3 2 n + 3 2 k − 2 ) -unavoidable and ( 9 2 n − 5 2 k − 9 2 ) -unavoidable, and thus ( 21 8 n − 47 16 ) -unavoidable. Finally, we prove that every oriented tree of order n with k leaves is ( n + 144 k 2 − 280 k + 124 ) -unavoidable.
Published: 2019
Full Text: View/download PDF

44. Eternal Domination in Grids

Author: Stéphane Pérennes, Fionn Mc Inerney, Nicolas Nisse, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-17-EURE-0004,UCA DS4H,UCA Systèmes Numériques pour l'Homme(2017), ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France, Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: Physics, Mathematics::Combinatorics, Domination analysis, Mathematics::Classical Analysis and ODEs, Grids, 0102 computer and information sciences, 02 engineering and technology, Computer Science::Computational Geometry, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 16. Peace & justice, 01 natural sciences, Omega, Graph, Vertex (geometry), Combinatorics, 010201 computation theory & mathematics, Computer Science::Discrete Mathematics, Combinatorial Games, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, [INFO]Computer Science [cs], Eternal Domination, Graphs
Abstract: International audience; In the eternal domination game played on graphs, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to adjacent vertices on their turn. The goal is to determine the eternal domination number $\gamma^{\infty}_{all}$ of a graph which is the minimum number of guards required to defend against an infinite sequence of attacks.This paper continues the study of the eternal domination game on strong grids $P_n\boxtimes P_m$. Cartesian grids $P_n \square P_m$ have been vastly studied with tight bounds existing for small grids such as $k\times n$ grids for $k\in \{2,3,4,5\}$. It was recently proven that $\gamma^{\infty}_{all}(P_n \square P_m)=\gamma(P_n \square P_m)+O(n+m)$ where $\gamma(P_n \square P_m)$ is the domination number of $P_n \square P_m$ which lower bounds the eternal domination number [Lamprou et al., CIAC 2017]. We prove that, for all $n,m\in \mathbb{N^*}$ such that $m\geq n$, $\lfloor\frac{n}{3}\rfloor \lfloor\frac{m}{3}\rfloor+\Omega(n+m)=\gamma_{all}^{\infty} (P_{n}\boxtimes P_{m})=\lceil\frac{n}{3}\rceil \lceil\frac{m}{3}\rceil + O(m\sqrt{n})$ (note that $\lceil\frac{n}{3}\rceil \lceil\frac{m}{3}\rceil$ is the domination number of $P_n\boxtimes P_m$). Our technique may be applied to other ``grid-like" graphs.
Published: 2019

45. A 1-2-3-4 result for the 1-2-3 Conjecture in 5-regular graphs

Author: Julien Bensmail, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), The author was supported by PEPS grant POCODIS., COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Discrete mathematics, Conjecture, 1-2-3 Conjecture, Applied Mathematics, 0211 other engineering and technologies, 021107 urban & regional planning, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Collatz conjecture, Combinatorics, New digraph reconstruction conjecture, 010201 computation theory & mathematics, 5-regular graphs, Discrete Mathematics and Combinatorics, Beal's conjecture, Four weights, Lonely runner conjecture, Connectivity, Mathematics
Abstract: The 1-2-3 Conjecture, posed by Karonski, Łuczak and Thomason, asks whether every connected graph G different from K 2 can be 3-edge-weighted so that every two adjacent vertices of G get distinct sums of incident weights. Towards that conjecture, the best-known result to date is due to Kalkowski, Karonski and Pfender, who proved that it holds when relaxed to 5-edge-weightings. Their proof builds upon a weighting algorithm designed by Kalkowski for a total version of the problem. In this work, we present new mechanisms for using Kalkowski’s algorithm in the context of the 1-2-3 Conjecture. As a main result we prove that every 5-regular graph admits a 4-edge-weighting that permits to distinguish its adjacent vertices via their incident sums.
Published: 2019
Full Text: View/download PDF

46. Overlaying a hypergraph with a graph with bounded maximum degree

Author: Dorian Mazauric, Frédéric Havet, Viet-Ha Nguyen, Rémi Watrigant, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Algorithms, Biology, Structure (ABS), Inria Sophia Antipolis - Méditerranée (CRISAM), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Inria Sophia Antipolis, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Hypergraph, Spanning subgraph, Computational complexity theory, 0102 computer and information sciences, Overlay, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], complexité, biologie structurale computationnelle, 01 natural sciences, Combinatorics, biologie structurale computation-nelle, 03 medical and health sciences, graphes, Discrete Mathematics and Combinatorics, [INFO]Computer Science [cs], 030304 developmental biology, Mathematics, 0303 health sciences, algorithm, Applied Mathematics, hypergraphes, graph, Graph, graphe, 010201 computation theory & mathematics, Bounded function, complexity, Hypergraphe, algorithme, algorithmes, computational structural biology
Abstract: International audience; Let G be a graph and H a hypergraph with the same set of vertices and let F be a fixed graph. The graph GF overlays a hyperedge S of H if F is a covering subgraph of the subgraph of G induced by S. The graph GF-overlaying H if F overlays each hyperedge of H. We have analyze the complexity of the following two problems. The first problem, ($∆ ≤ k$) F-OVERLAY, consists in deciding if there is a graph of maximum degree at most k which F overlays a given hypergraph H. This is a special case of the second problem, MAX ($∆ ≤ k$) F-OVERLAY, which, given a hypergraph H and an integer s, consists in deciding whether there is a graph of maximum degree at most k which F overlays at least s hyper edges of H. We prove a polynomial /NP-complete dichotomy for the MAX ($∆ ≤ k$) -F-OVERLAY, and prove the complexity of the problem ($∆ ≤ k$) F-OVERLAY for a large number of pairs (F, k). These two problems model a central problem in computational structural biology: the determination of the contacts between the proteins of a macromolecular assembly. The vertices are the proteins, the hyperedges are the known complexes, the graph F is the generic graph whose edges correspond to the contacts between the proteins of the assembly. Determining the graph G then comes down to finding the contacts between the proteins so that the graph F is a subgraph covering in each hyperedge and so that the degree is bounded (a protein is in contact with a limited number of others proteins). Finally, these problems are of more general interest for network inference problems.; Soient G un graphe et H un hypergraphe avec le même ensemble de sommets et soit F un graphe fixé. Le graphe GF-revouvre une hyperarête S de H si F est un sous-graphe couvrant du sous-graphe de G induit par S. Le graphe GF-revouvre H s’il F-revouvrechaque hyperarête de H. Nous avons analysé la complexité des deux problèmes suivants. Le premier problème, ($∆ ≤ k$) F-OVERLAY, consistè a décider s'il existe un graphe de degré maximum au plus k qui F-revouvre un hypergraphe H donné. C'est un cas particulier du second problème, MAX ($∆ ≤ k$) F-OVERLAY, qui,étant donné un hypergraphe H et un entier s, consistè a décider s'il existe un graphe de degré maximum au plus k qui F-revouvre au moins s hyperarêtes de H. Nous prouvons une dichotomie polynomial/N P-complet pour le problème MAX ($∆ ≤ k$)-F-OVERLAY dépendant de la paire (F, k), et prouvons la complexité du problème ($∆ ≤ k$) F-OVERLAY pour un grand nombre de paires (F, k). Ces deux problèmes modélisent un problème central en biologie structurale computationnelle : la détermination des contacts entre les protéines d'un assemblage macromoléculaire. Les sommets sont les protéines, les hyperarêtes sont les complexes connus, le graphe F est le graphe générique dont les arêtes correspondent aux contacts entre les protéines de l'assemblage. Déterminer le graphe G revient alorsà trouver les contacts entre les protéines de telle sorte que le graphe F soit un sous-graphe couvrant dans chaque hyperarête et de telle sorte que le degré soit borné (une protéine est en contact avec un nombre limité d'autres protéines). Enfin, ces problèmes sont d'intérêt plus général pour les problèmes d'inférence de réseaux.
Published: 2019
Full Text: View/download PDF

47. Self-stabilizing repeated balls-into-bins

Author: Emanuele Natale, Gustavo Posta, Francesco Pasquale, Andrea E. F. Clementi, Luca Becchetti, Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome], and Università degli Studi di Roma Tor Vergata [Roma]
Subjects: FOS: Computer and information sciences, Computer Networks and Communications, Self-stabilizing systems, Self-stabilization, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Bin, Balls into bins, Markov chains, Parallel resource assignment, Theoretical Computer Science, Hardware and Architecture, Computational Theory and Mathematics, Combinatorics, Balls into bins Markov chains, 0202 electrical engineering, electronic engineering, information engineering, Analysis of Algorithmsand, Problem Complexity, Theory, Algorithms, Computer communication networks, Time complexity, ComputingMilieux_MISCELLANEOUS, Mathematics, High probability, Markov chain, Settore INF/01 - Informatica, Complete graph, 020206 networking & telecommunications, Binary logarithm, Settore MAT/06 - Probabilita' e Statistica Matematica, Computer Science - Distributed, Parallel, and Cluster Computing, 010201 computation theory & mathematics, Bounded function, Theory of computation, Ball (bearing), Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Algorithm
Abstract: We study the following synchronous process that we call repeated balls-into-bins. The process is started by assigning n balls to n bins in an arbitrary way. Then, in every subsequent round, one ball is chosen according to some fixed strategy (random, FIFO, etc) from each non-empty bin, and re-assigned to one of the n bins uniformly at random. This process corresponds to a non-reversible Markov chain and our aim is to study its self-stabilization properties with respect to the maximum(bin) load and some related performance measures. We define a configuration (i.e., a state) legitimate if its maximum load is O(log n). We first prove that, starting from any legitimate configuration, the process will only take on legitimate configurations over a period of length bounded by any polynomial in n, with high probability (w.h.p.). Further we prove that, starting from any configuration, the process converges to a legitimate configuration in linear time, w.h.p. This implies that the process is self-stabilizing w.h.p. and, moreover, that every ball traverses all bins in O(n log2n) rounds, w.h.p. The latter result can also be interpreted as an almost tight bound on the cover time for the problem of parallel resource assignment in the complete graph.
Published: 2019
Full Text: View/download PDF

48. Step-By-Step Community Detection in Volume-Regular Graphs

Author: Francesco Pasquale, Luca Becchetti, Emilio Cruciani, Sara Rizzo, Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Università degli Studi di Roma Tor Vergata [Roma], Gran Sasso Science Institute (GSSI), Istituto Nazionale di Fisica Nucleare (INFN), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome], COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: FOS: Computer and information sciences, General Computer Science, Discrete Mathematics (cs.DM), Multivariate random variable, Lumpability, 0102 computer and information sciences, 02 engineering and technology, Spectral analysis, 01 natural sciences, Theoretical Computer Science, Combinatorics, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, Data Structures and Algorithms (cs.DS), Community detection, Distributed algorithms, Dynamics, Markov chains, Eigenvalues and eigenvectors, Clustering coefficient, Mathematics, 000 Computer science, knowledge, general works, Markov chain, Stochastic matrix, Random walk, Settore INF/01, Computer Science - Distributed, Parallel, and Cluster Computing, 010201 computation theory & mathematics, Computer Science, 020201 artificial intelligence & image processing, Distributed, Parallel, and Cluster Computing (cs.DC), Laplacian matrix, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Computer Science - Discrete Mathematics
Abstract: Spectral techniques have proved amongst the most effective approaches to graph clustering. However, in general they require explicit computation of the main eigenvectors of a suitable matrix (usually the Laplacian matrix of the graph). Recent work (e.g., Becchetti et al., SODA 2017) suggests that observing the temporal evolution of the power method applied to an initial random vector may, at least in some cases, provide enough information on the space spanned by the first two eigenvectors, so as to allow recovery of a hidden partition without explicit eigenvector computations. While the results of Becchetti et al. apply to perfectly balanced partitions and/or graphs that exhibit very strong forms of regularity, we extend their approach to graphs containing a hidden $k$ partition and characterized by a milder form of volume-regularity. We show that the class of $k$-volume-regular graphs is the largest class of undirected (possibly weighted) graphs whose transition matrix admits $k$ "stepwise" eigenvectors (i.e., vectors that are constant over each set of the hidden partition). To obtain this result, we highlight a connection between volume regularity and lumpability of Markov chains. Moreover, we prove that if the stepwise eigenvectors are those associated to the first $k$ eigenvalues and the gap between the $k$-th and the ($k$+1)-th eigenvalues is sufficiently large, the averaging dynamics of Becchetti et al. recovers the underlying community structure of the graph in logarithmic time, with high probability., Comment: Preliminary version appeared in Proceedings of ISAAC 2019
Published: 2019
Full Text: View/download PDF

49. Subdivisions in digraphs of large out-degree or large dichromatic number

Author: Frédéric Havet, Nathann Cohen, Phablo F. S. Moura, William Lochet, Pierre Aboulker, Stéphan Thomassé, Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Universidade Estadual de Campinas (UNICAMP), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), École normale supérieure - Paris (ENS-PSL), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Universidade Estadual de Campinas = University of Campinas (UNICAMP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Computer Science::Discrete Mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Tournament, [INFO]Computer Science [cs], [MATH]Mathematics [math], Subdivision, Mathematics, Transitive relation, Conjecture, Mathematics::Combinatorics, business.industry, Applied Mathematics, Out degree, Digraph, Graph, Computational Theory and Mathematics, 010201 computation theory & mathematics, Geometry and Topology, Combinatorics (math.CO), business
Abstract: In 1985, Mader conjectured the existence of a function $f$ such that every digraph with minimum out-degree at least $f(k)$ contains a subdivision of the transitive tournament of order $k$. This conjecture is still completely open, as the existence of $f(5)$ remains unknown. In this paper, we show that if $D$ is an oriented path, or an in-arborescence (i.e., a tree with all edges oriented towards the root) or the union of two directed paths from $x$ to $y$ and a directed path from $y$ to $x$, then every digraph with minimum out-degree large enough contains a subdivision of $D$. Additionally, we study Mader's conjecture considering another graph parameter. The dichromatic number of a digraph $D$ is the smallest integer $k$ such that $D$ can be partitioned into $k$ acyclic subdigraphs. We show that any digraph with dichromatic number greater than $4^m (n-1)$ contains every digraph with $n$ vertices and $m$ arcs as a subdivision. We show that any digraph with dichromatic number greater than $4^m (n-1)$ contains every digraph with $n$ vertices and $m$ arcs as a subdivision.
Published: 2019

50. Hyperopic Cops and Robbers

Author: Margaret-Ellen Messinger, Nancy E. Clarke, Stephen Finbow, Anthony Bonato, F. Mc Inerney, Danielle Cox, Ryerson University [Toronto], Acadia University, Mount Saint Vincent University [Halifax] (MSVU), Université Saint-Francis-Xavier (CANADA), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Department of Mathematics and Computer Science [Mount Allison University], Mount Allison University, COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: FOS: Computer and information sciences, Discrete Mathematics (cs.DM), General Computer Science, 0102 computer and information sciences, 02 engineering and technology, New variant, 01 natural sciences, Theoretical Computer Science, Planar graph, Combinatorics, Set (abstract data type), symbols.namesake, 010201 computation theory & mathematics, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, symbols, Countable set, Mathematics - Combinatorics, 020201 artificial intelligence & image processing, [INFO]Computer Science [cs], Combinatorics (math.CO), [MATH]Mathematics [math], Mathematics, Real number, Computer Science - Discrete Mathematics
Abstract: We introduce a new variant of the game of Cops and Robbers played on graphs, where the robber is invisible unless outside the neighbor set of a cop. The hyperopic cop number is the corresponding analogue of the cop number, and we investigate bounds and other properties of this parameter. We characterize the cop-win graphs for this variant, along with graphs with the largest possible hyperopic cop number. We analyze the cases of graphs with diameter 2 or at least 3, focusing on when the hyperopic cop number is at most one greater than the cop number. We show that for planar graphs, as with the usual cop number, the hyperopic cop number is at most 3. The hyperopic cop number is considered for countable graphs, and it is shown that for connected chains of graphs, the hyperopic cop density can be any real number in [ 0 , 1 / 2 ] .
Published: 2019

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

123 results on '"Coati A"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources