Search

Your search keyword '"Frédéric Havet"' showing total 86 results
Start Over Author "Frédéric Havet" Topic mathematics
86 results on '"Frédéric Havet"'

1. On the inversion number of oriented graphs

Author

Jørgen Bang-Jensen, Jonas Costa Ferreira da Silva, and Frédéric Havet

Subjects
mathematics - combinatorics, computer science - discrete mathematics, Mathematics, QA1-939
Abstract

Let $D$ be an oriented graph. The inversion of a set $X$ of vertices in $D$ consists in reversing the direction of all arcs with both ends in $X$. The inversion number of $D$, denoted by ${\rm inv}(D)$, is the minimum number of inversions needed to make $D$ acyclic. Denoting by $\tau(D)$, $\tau' (D)$, and $\nu(D)$ the cycle transversal number, the cycle arc-transversal number and the cycle packing number of $D$ respectively, one shows that ${\rm inv}(D) \leq \tau' (D)$, ${\rm inv}(D) \leq 2\tau(D)$ and there exists a function $g$ such that ${\rm inv}(D)\leq g(\nu(D))$. We conjecture that for any two oriented graphs $L$ and $R$, ${\rm inv}(L\rightarrow R) ={\rm inv}(L) +{\rm inv}(R)$ where $L\rightarrow R$ is the dijoin of $L$ and $R$. This would imply that the first two inequalities are tight. We prove this conjecture when ${\rm inv}(L)\leq 1$ and ${\rm inv}(R)\leq 2$ and when ${\rm inv}(L) ={\rm inv}(R)=2$ and $L$ and $R$ are strongly connected. We also show that the function $g$ of the third inequality satisfies $g(1)\leq 4$. We then consider the complexity of deciding whether ${\rm inv}(D)\leq k$ for a given oriented graph $D$. We show that it is NP-complete for $k=1$, which together with the above conjecture would imply that it is NP-complete for every $k$. This contrasts with a result of Belkhechine et al. which states that deciding whether ${\rm inv}(T)\leq k$ for a given tournament $T$ is polynomial-time solvable.

Published
2022
Full Text
View/download PDF

2. Constrained ear decompositions in graphs and digraphs

Author

Frédéric Havet and Nicolas Nisse

Subjects
[info.info-dm]computer science [cs]/discrete mathematics [cs.dm], [info.info-cc]computer science [cs]/computational complexity [cs.cc], Mathematics, QA1-939
Abstract

Ear decompositions of graphs are a standard concept related to several major problems in graph theory like the Traveling Salesman Problem. For example, the Hamiltonian Cycle Problem, which is notoriously N P-complete, is equivalent to deciding whether a given graph admits an ear decomposition in which all ears except one are trivial (i.e. of length 1). On the other hand, a famous result of Lovász states that deciding whether a graph admits an ear decomposition with all ears of odd length can be done in polynomial time. In this paper, we study the complexity of deciding whether a graph admits an ear decomposition with prescribed ear lengths. We prove that deciding whether a graph admits an ear decomposition with all ears of length at most is polynomial-time solvable for all fixed positive integer. On the other hand, deciding whether a graph admits an ear decomposition without ears of length in F is N P-complete for any finite set F of positive integers. We also prove that, for any k ≥ 2, deciding whether a graph admits an ear decomposition with all ears of length 0 mod k is N P-complete. We also consider the directed analogue to ear decomposition, which we call handle decomposition, and prove analogous results : deciding whether a digraph admits a handle decomposition with all handles of length at most is polynomial-time solvable for all positive integer ; deciding whether a digraph admits a handle decomposition without handles of length in F is N P-complete for any finite set F of positive integers (and minimizing the number of handles of length in F is not approximable up to n(1 −)); for any k ≥ 2, deciding whether a digraph admits a handle decomposition with all handles of length 0 mod k is N P-complete. Also, in contrast with the result of Lovász, we prove that deciding whether a digraph admits a handle decomposition with all handles of odd length is N P-complete. Finally, we conjecture that, for every set A of integers, deciding whether a digraph has a handle decomposition with all handles of length in A is N P-complete, unless there exists h ∈ N such that A = {1, · · · , h}.

Published
2019
Full Text
View/download PDF

3. Backbone colouring and algorithms for TDMA scheduling

Author

Julien Bensmail, Thibaut Blanc, Nathann Cohen, Frédéric Havet, and Leonardo Rocha

Subjects
wireless networks, tdma scheduling, backbone colouring, algorithmic complexity, [info.info-dm]computer science [cs]/discrete mathematics [cs.dm], Mathematics, QA1-939
Abstract

We investigate graph colouring models for the purpose of optimizing TDMA link scheduling in Wireless Networks. Inspired by the BPRN-colouring model recently introduced by Rocha and Sasaki, we introduce a new colouring model, namely the BMRN-colouring model, which can be used to model link scheduling problems where particular types of collisions must be avoided during the node transmissions. In this paper, we initiate the study of the BMRN-colouring model by providing several bounds on the minimum number of colours needed to BMRN-colour digraphs, as well as several complexity results establishing the hardness of finding optimal colourings. We also give a special focus on these considerations for planar digraph topologies, for which we provide refined results.

Published
2019
Full Text
View/download PDF

4. List circular backbone colouring

Author

Frédéric Havet and Andrew King

Subjects
discrete mathematics, graph theory, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], Mathematics, QA1-939
Abstract

Graph Theory

Published
2014
Full Text
View/download PDF

5. 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

6. 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

7. 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

8. 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

9. 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

10. Finding a subdivision of a prescribed digraph of order 4

Author

A. Karolinna Maia, Bojan Mohar, and Frédéric Havet

Subjects
Reduction (recursion theory), business.industry, 010102 general mathematics, Digraph, 0102 computer and information sciences, Mathematical proof, 01 natural sciences, Combinatorics, Algorithmic complexity, 010201 computation theory & mathematics, Discrete Mathematics and Combinatorics, Order (group theory), Point (geometry), Geometry and Topology, 0101 mathematics, business, Mathematics, Subdivision
Abstract

The problem of when a given digraph contains a subdivision of a fixed digraph F is considered. Bang-Jensen et al. [4] laid out foundations for approaching this problem from the algorithmic point of view. In this article, we give further support to several open conjectures and speculations about algorithmic complexity of finding F-subdivisions. In particular, up to five exceptions, we completely classify for which 4-vertex digraphs F, the F-subdivision problem is polynomial-time solvable and for which it is NP-complete. While all NP-hardness proofs are made by reduction from some version of the 2-linkage problem in digraphs, some of the polynomial-time solvable cases involve relatively complicated algorithms.

Published
2017
Full Text
View/download PDF

12. 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

13. 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

14. 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

15. 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

16. Proper orientation of cacti

Author

Júlio Araújo, Cláudia Linhares Sales, Ana Silva, Frédéric Havet, Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), 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), FUNCAP/CNRS project GAIATO INC-0083- 00047.01.00/13, ANR-13-BS02-0007,Stint,Structures Interdites(2013), Université Nice Sophia Antipolis (... - 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 (... - 2019) (UNS)

Subjects
Factor-critical graph, General Computer Science, planar graph, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], cactus graph, 01 natural sciences, Theoretical Computer Science, Combinatorics, Graph power, Outerplanar graph, graph coloring, 0202 electrical engineering, electronic engineering, information engineering, Graph minor, Complement graph, Mathematics, Discrete mathematics, block graph, Cactus graph, 020206 networking & telecommunications, Butterfly graph, claw-free graph, 010201 computation theory & mathematics, proper orientation, Null graph
Abstract

International audience; An orientation of a graph G is proper if two adjacent vertices have different in-degrees. The proper-orientation number − → χ (G) of a graph G is the minimum maximum in-degree of a proper orientation of G. In [1], the authors ask whether the proper orientation number of a planar graph is bounded. We prove that every cactus admits a proper orientation with maximum in-degree at most 7. We also prove that the bound 7 is tight by showing a cactus having no proper orientation with maximum in-degree less than 7. We also prove that any planar claw-free graph has a proper orientation with maximum in-degree at most 6 and that this bound can also be attained.

Published
2016
Full Text
View/download PDF

17. 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

18. $χ$-bounded families of oriented graphs

Author

Pierre Charbit, Frédéric Maffray, Nicolas Bousquet, Frédéric Havet, José Zamora, Jørgen Bang-Jensen, Pierre Aboulker, 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), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Nice Sophia Antipolis (... - 2019) (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)-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 Southern Denmark (SDU), OC (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Universidad Andrés Bello - UNAB (CHILE), 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), 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), COMUE Université Côte 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), Department of Mathematics and Computer Science [Odense] (IMADA), Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), 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), Optimisation Combinatoire (G-SCOP_OC ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Universidad Andrés Bello [Santiago] (UNAB), ANR-13-BS02-0007,Stint,Structures Interdites(2013), COMUE Université Côte 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), This work was supported by ANR under contract STINT ANR-13-BS02-0007., COMUE Université Côte 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 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), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS), Université Côte d'Azur (UCA), Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-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)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)

Subjects
Transitive relation, Conjecture, Mathematics::Combinatorics, 010102 general mathematics, Induced subgraph, Digraph, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, clique number, Combinatorics, 010201 computation theory & mathematics, chromatic number, Computer Science::Discrete Mathematics, Bounded function, χ-bounded, Discrete Mathematics and Combinatorics, Tournament, Geometry and Topology, Chromatic scale, 0101 mathematics, Mathematics, Computer Science - Discrete Mathematics
Abstract

A famous conjecture of Gy\'arf\'as and Sumner states for any tree $T$ and integer $k$, if the chromatic number of a graph is large enough, either the graph contains a clique of size $k$ or it contains $T$ as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star $S$ and integer $k$, if the chromatic number of a digraph is large enough, either the digraph contains a clique of size $k$ or it contains $S$ as an induced subgraph. As an evidence, we prove that for any oriented star $S$, every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order $3$ or $S$ as an induced subdigraph. We then study for which sets ${\cal P}$ of orientations of $P_4$ (the path on four vertices) similar statements hold. We establish some positive and negative results., Comment: 27 pages, 4 figures

Published
2018
Full Text
View/download PDF

19. Complexity dichotomies for the Minimum F -Overlay problem

Author

Frédéric Havet, Dorian Mazauric, Ignasi Sau, Nathann Cohen, Rémi Watrigant, Laboratoire de Recherche en Informatique (LRI), 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 (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), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), Algorithms, Biology, Structure (ABS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), 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), 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), ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016), Graphes, Algorithmes et Combinatoire (LRI) (GALaC - 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), Universidade Federal do Ceará = Federal University of Ceará (UFC), Projet de Recherche Exploratoire Inria: Improving inference algorithms for macromolecular structure determination, ANR-13-BS02-0007,Stint,Structures Interdites(2013), 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), 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), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), This work was partially funded by ‘Projet de Recherche Exploratoire’, Inria, Improving inference algorithms for macromolecular structure determination, Inria Sophia Antipolis, CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), É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
FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Hypergraph, Spanning subgraph, Dichotomy, Subgraph isomorphism problem, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Parameterized complexity, 0102 computer and information sciences, 02 engineering and technology, Overlay, Computational Complexity (cs.CC), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Induced subgraph isomorphism problem, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete mathematics, Complete graph, 020206 networking & telecommunications, NP-completeness, Minimum F-Overlay Problem, Computer Science - Computational Complexity, Computational Theory and Mathematics, 010201 computation theory & mathematics, Fixed-parameter tractability
Abstract

International audience; For a (possibly infinite) fixed family of graphs F, we say that a graph G overlays F on a hypergraph H if V (H) is equal to V (G) and the subgraph of G induced by every hyperedge of H contains some member of F as a spanning subgraph. While it is easy to see that the complete graph on |V (H)| overlays F on a hypergraph H whenever the problem admits a solution, the Minimum F-Overlay problem asks for such a graph with the minimum number of edges. This problem allows to generalize some natural problems which may arise in practice. For instance, if the family F contains all connected graphs, then Minimum F-Overlay corresponds to the Minimum Connectivity Inference problem (also known as Subset Interconnection Design problem) introduced for the low-resolution reconstruction of macro-molecular assembly in structural biology, or for the design of networks. Our main contribution is a strong dichotomy result regarding the polynomial vs. NP-hard status with respect to the considered family F. Roughly speaking, we show that the easy cases one can think of (e.g. when edge-less graphs of the right sizes are in F, or if F contains only cliques) are the only families giving rise to a polynomial problem: all others are NP-complete. We then investigate the parameterized complexity of the problem and give similar sufficient conditions on F that give rise to W[1]-hard, W[2]-hard or FPT problems when the parameter is the size of the solution. This yields an FPT/W[1]-hard dichotomy for a relaxed problem , where every hyperedge of H must contain some member of F as a (non necessarily spanning) subgraph.

Published
2018
Full Text
View/download PDF

20. 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

21. On the Minimum Size of an Identifying Code Over All Orientations of a Graph

Author

Nathann Cohen, Frédéric Havet, 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), ANR-13-BS02-0007,Stint,Structures Interdites(2013), 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
Applied Mathematics, Digraph, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Graph, Theoretical Computer Science, Combinatorics, identifying code, orientations, Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology, NP-complete, Mathematics
Abstract

If $G$ be a graph or a digraph, let $\mathrm{id}(G)$ be the minimum size of an identifying code of $G$ if one exists, and $\mathrm{id}(G)=+\infty$ otherwise. For a graph $G$, let $\mathrm{idor}(G)$ be the minimum of $\mathrm{id}(D)$ overall orientations $D$ of $G$. We give some lower and upper bounds on $\mathrm{idor}(G)$. In particular, we show that $\mathrm{idor}(G)\leqslant \frac{3}{2} \mathrm{id}(G)$ for every graph $G$. We also show that computing $\mathrm{idor}(G)$ is NP-hard, while deciding whether $\mathrm{idor}(G)\leqslant |V(G)|-k$ is polynomial-time solvable for every fixed integer $k$.

Published
2018
Full Text
View/download PDF

22. Complexity Dichotomies for the Minimum $$\mathcal {F}$$-Overlay Problem

Author

Dorian Mazauric, Rémi Watrigant, Nathann Cohen, Ignasi Sau, and Frédéric Havet

Subjects
Combinatorics, Hypergraph, Spanning subgraph, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Complete graph, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Overlay, 01 natural sciences, Graph, Mathematics
Abstract

For a (possibly infinite) fixed family of graphs \(\mathcal {F}\), we say that a graph G overlays \(\mathcal {F}\) on a hypergraph H if V(H) is equal to V(G) and the subgraph of G induced by every hyperedge of H contains some member of \(\mathcal {F}\) as a spanning subgraph. While it is easy to see that the complete graph on |V(H)| overlays \(\mathcal {F}\) on a hypergraph H whenever the problem admits a solution, the Minimum \(\mathcal {F}\)-Overlay problem asks for such a graph with the minimum number of edges. This problem allows to generalize some natural problems which may arise in practice. For instance, if the family \(\mathcal {F}\) contains all connected graphs, then Minimum \(\mathcal {F}\)-Overlay corresponds to the Minimum Connectivity Inference problem (also known as Subset Interconnection Design problem) introduced for the low-resolution reconstruction of macro-molecular assembly in structural biology, or for the design of networks.

Published
2018
Full Text
View/download PDF

23. Tournaments and Semicomplete Digraphs

Author

Jørgen Bang-Jensen, Frédéric Havet, Bang-Jensen, Jørgen, Gutin, Gregory, COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), 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), Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), 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
Class (set theory), Mathematics::Combinatorics, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Mathematical proof, 01 natural sciences, Combinatorics, Range (mathematics), Cover (topology), 010201 computation theory & mathematics, Computer Science::Discrete Mathematics, Order (group theory), 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Superclass, Mathematics
Abstract

The class of tournaments is by far the most well-studied class of digraphs with many deep and important results. Since Moon’s pioneering book in 1968 [146], the study of tournaments and their properties has flourished and research on tournaments is still a very active area. Often this research deals with the superclass of semicomplete digraphs which are digraphs with no pair of non-adjacent vertices (that is, contrary to tournaments, we allow directed cycles of length 2). In this chapter we cover a very broad range of results on tournaments and semicomplete digraphs from classical to very recent ones. In order to stimulate further research, we not only list a number of open problems, but also give a number of proofs which illustrate the diversity of proof techniques that have been applied. These range from elementary to quite advanced.

Published
2018
Full Text
View/download PDF

24. Steinberg-like theorems for backbone colouring

Author

Frédéric Havet, Júlio Araújo, Mathieu Schmitt, 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), École normale supérieure - Lyon (ENS Lyon), 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), and CNRS-FUNCAP GAIATO

Subjects
Graph colouring, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Planar Graph, Combinatorics, symbols.namesake, Steinberg's Conjecture, Subgroup, Graph power, Graph minor, Discrete Mathematics and Combinatorics, Graph toughness, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete mathematics, Connected component, Graph Colouring, Applied Mathematics, 010102 general mathematics, Backbone Colouring, Graph, Planar graph, New digraph reconstruction conjecture, Edge-transitive graph, 010201 computation theory & mathematics, symbols, Bound graph, Graph factorization
Abstract

A function f : V ( G ) → { 1 , … , k } is a (proper) k -colouring of G if ∣ f ( u ) − f ( v ) ∣ ≥ 1 , for every edge u v ∈ E ( G ) . The chromatic number χ ( G ) is the smallest integer k for which there exists a proper k -colouring of G . Given a graph G and a subgraph H of G , a circular q -backbone k -colouring f of ( G , H ) is a k -colouring of G such that q ≤ ∣ f ( u ) − f ( v ) ∣ ≤ k − q , for each edge u v ∈ E ( H ) . The circular q -backbone chromatic number of a graph pair ( G , H ) , denoted CBC q ( G , H ) , is the minimum k such that ( G , H ) admits a circular q -backbone k -colouring. Inspired by Steinberg’s conjecture, we conjecture that if G is a planar graph containing no cycles on 4 or 5 vertices and H ⊆ G is a forest, then CBC 2 ( G , H ) ≤ 6 . In this work, we first show that if G is a planar graph containing no cycle on 4 or 5 vertices and H ⊆ G is a forest, then CBC 2 ( G , H ) ≤ 7 . Then, we prove that if H ⊆ G is a forest whose connected components are paths, then CBC 2 ( G , H ) ≤ 6 .

Published
2018
Full Text
View/download PDF

25. On the Complexity of Compressing Two Dimensional Routing Tables with Order

Author

Joanna Moulierac, Frédéric Havet, Frédéric Giroire, 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), 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
Discrete mathematics, Reduction (recursion theory), General Computer Science, Applied Mathematics, Routing table, Order (ring theory), Approximation algorithm, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Function (mathematics), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Computer Science Applications, Combinatorics, Integer, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Routing (electronic design automation), Mathematics
Abstract

Motivated by routing in telecommunication network using Software Defined Network (SDN) technologies, we consider the following problem of finding short routing lists using aggregation rules. We are given a set of communications $$\mathcal {X}$$ , which are distinct pairs $$(s,t)\subseteq S\times T$$ , (typically S is the set of sources and T the set of destinations), and a port function $$\pi :\mathcal {X} \rightarrow P$$ where P is the set of ports. A routing list $$\mathcal {R}$$ is an ordered list of triples which are of the form (s, t, p), $$(*,t,p)$$ , $$(s,*,p)$$ or $$(*,*,p)$$ with $$s\in S$$ , $$t\in T$$ and $$p\in P$$ . It routes the communication (s, t) to the port $$r(s,t) =p$$ which appears on the first triple in the list $$\mathcal {R}$$ that is of the form (s, t, p), $$(*,t,p)$$ , $$(s,*,p)$$ or $$(*,*,p)$$ . If $$r(s,t)=\pi (s,t)$$ , then we say that (s, t) is properly routed by $$\mathcal {R}$$ and if all communications of $$\mathcal {X}$$ are properly routed, we say that $$\mathcal {R}$$ emulates $$(\mathcal {X}, \pi )$$ . The aim is to find a shortest routing list emulating $$(\mathcal {X}, \pi )$$ . In this paper, we carry out a study of the complexity of the two dual decision problems associated to it. Given a set of communication $$\mathcal {X}$$ , a port function $$\pi $$ and an integer k, the first one called Routing List (resp. the second one, called List Reduction) consists in deciding whether there is a routing list emulating $$(\mathcal {X}, \pi )$$ of size at most k (resp. $$|\mathcal {X}| -k$$ ). We prove that both problems are NP-complete. We then give a 3-approximation for List Reduction, which can be generalized to higher dimensions. We also give a 4-approximation for Routing List in the fundamental case when there are only two ports (i.e. $$|P|=2$$ ), $$\mathcal {X}=S\times T$$ and $$|S|=|T|$$ .

Published
2018
Full Text
View/download PDF

26. Bispindle in strongly connected digraphs with large chromatic number

Author

Raul Lopes, William Lochet, Frédéric Havet, Nathann Cohen, 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 (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 National de Recherche en Informatique et en Automatique (Inria), Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), ANR-13-BS02-0007,Stint,Structures Interdites(2013), Université Nice Sophia Antipolis (... - 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 (... - 2019) (UNS)

Subjects
Strongly connected component, business.industry, Applied Mathematics, Digraph, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Disjoint sets, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, Integer, 010201 computation theory & mathematics, chromatic number, subdivision, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Chromatic scale, business, Mathematics, Subdivision
Abstract

A ( k 1 + k 2 )-bispindle is the union of k1 (x, y)-dipaths and k2 (y, x)-dipaths, all these dipaths being pairwise internally disjoint. Recently, Cohen et al. showed that for every (2 + 0)-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 generalisations of this result by first showing constructions of strongly connected digraphs with large chromatic number without any ( 3 + 0 )-bispindle or ( 2 + 2 )-bispindle. Then we show that for any k, there exists γ k such that every strongly connected digraph with chromatic number greater than γ k contains a ( 2 + 1 )-bispindle with the (y, x)-dipath and one of the (x, y)-dipaths of length at least k.

Published
2017
Full Text
View/download PDF

27. Out-degree reducing partitions of digraphs

Author

Joergen Bang-Jensen, Frédéric Havet, Anders Yeo, Stéphane Bessy, Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), 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), 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), Danish research council, grant number 1323-00178B, Labex UCN@Sophia, OSMO project, Occitanie regional council, ANR-13-BS02-0007,Stint,Structures Interdites(2013), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), 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, Vertex (graph theory), Discrete Mathematics (cs.DM), General Computer Science, Maximum out-degree reducing partition, Polynomial algorithm, 0102 computer and information sciences, Characterization (mathematics), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Integer, Computer Science::Discrete Mathematics, FOS: Mathematics, Mathematics - Combinatorics, 05C20, 0101 mathematics, Mathematics, NP-complete, Discrete mathematics, Mathematics::Combinatorics, 2-partition, 010102 general mathematics, Out degree, Digraph, 010201 computation theory & mathematics, Combinatorics (math.CO), Computer Science - Discrete Mathematics
Abstract

Let $k$ be a fixed integer. We determine the complexity of finding a $p$-partition $(V_1, \dots, V_p)$ of the vertex set of a given digraph such that the maximum out-degree of each of the digraphs induced by $V_i$, ($1\leq i\leq p$) is at least $k$ smaller than the maximum out-degree of $D$. We show that this problem is polynomial-time solvable when $p\geq 2k$ and ${\cal NP}$-complete otherwise. The result for $k=1$ and $p=2$ answers a question posed in \cite{bangTCS636}. We also determine, for all fixed non-negative integers $k_1,k_2,p$, the complexity of deciding whether a given digraph of maximum out-degree $p$ has a $2$-partition $(V_1,V_2)$ such that the digraph induced by $V_i$ has maximum out-degree at most $k_i$ for $i\in [2]$. It follows from this characterization that the problem of deciding whether a digraph has a 2-partition $(V_1,V_2)$ such that each vertex $v\in V_i$ has at least as many neighbours in the set $V_{3-i}$ as in $V_i$, for $i=1,2$ is ${\cal NP}$-complete. This solves a problem from \cite{kreutzerEJC24} on majority colourings., 11 pages, 1 figure

Published
2017
Full Text
View/download PDF

28. Bipartite spanning sub(di)graphs induced by 2-partitions

Author

Jørgen Bang-Jensen, Anders Yeo, Frédéric Havet, Stéphane Bessy, University of Southern Denmark (SDU), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), 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), Occitanie regional council. Grant Number: OSMO- Labex UCN©Sophia- Danish Research Council. Grant Number: 1323‐00178B, ANR-13-BS02-0007,Stint,Structures Interdites(2013), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-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
FOS: Computer and information sciences, Strongly connected component, Discrete Mathematics (cs.DM), eulerian, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, 2-partition, spanning bipartite subdigraph, Combinatorics, symbols.namesake, Computer Science::Discrete Mathematics, Spanning bipartite subdigraph, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 05C20, 0101 mathematics, Nuclear Experiment, Eulerian, Mathematics, Mathematics::Combinatorics, Minimum out-degree, 2-partition, 010102 general mathematics, strong spanning subdigraph, Strong spanning subdigraph, Digraph, Eulerian path, Graph, Vertex (geometry), 010201 computation theory & mathematics, Bipartite graph, symbols, minimum out-degree, Geometry and Topology, Combinatorics (math.CO), Computer Science - Discrete Mathematics
Abstract

For a given $2$-partition $(V_1,V_2)$ of the vertices of a (di)graph $G$, we study properties of the spanning bipartite subdigraph $B_G(V_1,V_2)$ of $G$ induced by those arcs/edges that have one end in each $V_i$. We determine, for all pairs of non-negative integers $k_1,k_2$, the complexity of deciding whether $G$ has a 2-partition $(V_1,V_2)$ such that each vertex in $V_i$ has at least $k_i$ (out-)neighbours in $V_{3-i}$. We prove that it is ${\cal NP}$-complete to decide whether a digraph $D$ has a 2-partition $(V_1,V_2)$ such that each vertex in $V_1$ has an out-neighbour in $V_2$ and each vertex in $V_2$ has an in-neighbour in $V_1$. The problem becomes polynomially solvable if we require $D$ to be strongly connected. We give a characterisation, based on the so-called strong component digraph of a non-strong digraph of the structure of ${\cal NP}$-complete instances in terms of their strong component digraph. When we want higher in-degree or out-degree to/from the other set the problem becomes ${\cal NP}$-complete even for strong digraphs. A further result is that it is ${\cal NP}$-complete to decide whether a given digraph $D$ has a $2$-partition $(V_1,V_2)$ such that $B_D(V_1,V_2)$ is strongly connected. This holds even if we require the input to be a highly connected eulerian digraph., Comment: 17 pages, 4 figures

Published
2017
Full Text
View/download PDF

29. Identifying codes for infinite triangular grids with a finite number of rows

Author

Frédéric Havet, Rudini Menezes Sampaio, Rennan Dantas, Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), 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), INRIA Sophia Antipolis - I3S, FUNCAP/CNRS project GAIATO INC-0083- 00047.01.00/13, ANR-13-BS02-0007,Stint,Structures Interdites(2013), 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), and FUNCAP-CNRS project GAIATO

Subjects
Vertex (graph theory), Discrete mathematics, grille, Discharging method, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Triangular grid, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, grid, Graph, Theoretical Computer Science, Combinatorics, identifying code, 010201 computation theory & mathematics, méthode de déchargement, code identifiant, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, discharging method, Row, Finite set, Minimum density, Mathematics
Abstract

Let $\mathcal{G}_T$ be the infinite triangular grid. For any positive integer $k$, we denote by $T_k$ the subgraph of $\mathcal{G}_T$ induced by the vertex set $\{(x,y)\in\mathbb{Z}\times[k]\}$.A set $C\subset V(G)$ is an {\it identifying code} in a graph $G$ if for all $v\in V(G)$, $N[v]\cap C\neq \emptyset$, and for all $u,v\in V(G)$, $N[u]\cap C\neq N[v]\cap C$, where $N[x]$ denotes the closed neighborhood of $x$ in $G$.The minimum density of an identifying code in $G$ is denoted by $d^*(G)$.In this paper, we prove that $d^*(T_1)=d^*(T_2)=1/2$, $d^*(T_3)=d^*(T_4)=1/3$, $d^*(T_5)=3/10$, $d^*(T_6)=1/3$ and $d^*(T_k)=1/4+1/(4k)$ for every $k\geq 7$ odd. Moreover, we prove that $1/4+1/(4k)\leq d^*(T_k)\leq 1/4+1/(2k)$ for every $k\geq 8$ even.; Soit $\mathcal{G}_T$ la grille triangulaire infinie. Pour pout entier strictement positif $k$, nous notons $T_k$ le sous-graphe de $\mathcal{G}_T$ induit par l'ensemble des sommets $\{(x,y)\in\mathbb{Z}\times[k]\}$.Un ensemble $C\subset V(G)$ est un {\it code identifiant} d'un graphe $G$ si pour tout $v\in V(G)$, $N[v]\cap C\neq \emptyset$, et pour tout $u,v\in V(G)$, $N[u]\cap C\neq N[v]\cap C$, o\`u $N[x]$ est le voisinage ferm\'e de $x$ dans $G$.La densit\'e minimum d'un code identifiant de $G$ est not\'ee $d^*(G)$.Dans ce rapport, nous montrons que $d^*(T_1)=d^*(T_2)=1/2$, $d^*(T_3)=d^*(T_4)=1/3$, $d^*(T_5)=3/10$, $d^*(T_6)=1/3$ et $d^*(T_k)=1/4+1/(4k)$ pour tout $k\geq 7$ impair. De plus, nous montrons que $1/4+1/(4k)\leq d^*(T_k)\leq 1/4+1/(2k)$ pour tout $k\geq 8$ pair.

Published
2016
Full Text
View/download PDF

30. Finding good 2-partitions of digraphs II. Enumerable properties

Author

Nathann Cohen, Jørgen Bang-Jensen, Frédéric Havet, Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), Laboratoire de Recherche en Informatique (LRI), 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 (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é Nice Sophia Antipolis (... - 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 (... - 2019) (UNS)

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Strongly connected component, General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, Disjoint sets, Vertex partition, 01 natural sciences, Polynomial, Out-branching, Theoretical Computer Science, Combinatorics, Computer Science::Discrete Mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Partition (number theory), Tournament, 0101 mathematics, Feedback vertex set, Mathematics, NP-complete, Acyclic, Discrete mathematics, Semicomplete digraph, 010102 general mathematics, Digraph, Oriented, Has property, 2-Partition, 010201 computation theory & mathematics, Minimum degree, Splitting digraphs, Partition
Abstract

International audience; We continue the study, initiated in [3], of the complexity of deciding whether a given digraph D has a vertex-partition into two disjoint subdigraphs with given structural properties and given minimum cardinality. Let EE be the following set of properties of digraphs: E=E={strongly connected, connected, minimum out-degree at least 1, minimum in-degree at least 1, minimum semi-degree at least 1, minimum degree at least 1, having an out-branching, having an in-branching}. In this paper we determine, for all choices of P1,P2P1,P2 from EE and all pairs of fixed positive integers k1,k2k1,k2, the complexity of deciding whether a digraph has a vertex partition into two digraphs D1,D2D1,D2 such that DiDi has property PiPi and |V(Di)|≥ki|V(Di)|≥ki, i=1,2i=1,2. We also classify the complexity of the same problems when restricted to strongly connected digraphs. The complexity of the analogous problems when P1∈HP1∈H and P2∈H∪EP2∈H∪E, where H=H={acyclic, complete, arc-less, oriented (no 2-cycle), semicomplete, symmetric, tournament} were completely characterized in [3].

Published
2016
Full Text
View/download PDF

31. New Bounds on the Grundy Number of Products of Graphs

Author

Frédéric Havet, András Gyárfás, Cláudia Linhares Sales, Victor Campos, and Frédéric Maffray

Subjects
Discrete mathematics, 010102 general mathematics, Graph theory, 0102 computer and information sciences, Complete coloring, 01 natural sciences, Graph, Greedy coloring, Combinatorics, 010201 computation theory & mathematics, Grundy number, Discrete Mathematics and Combinatorics, Geometry and Topology, 0101 mathematics, Greedy algorithm, Mathematics
Abstract

The Grundy number of a graph G is the largest k such that G has a greedy k-coloring, that is, a coloring with k colors obtained by applying the greedy algorithm according to some ordering of the vertices of G. In this article, we give new bounds on the Grundy number of the product of two graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:78–88, 2012 © 2012 Wiley Periodicals, Inc.

Published
2012
Full Text
View/download PDF

32. Finding an induced subdivision of a digraph

Author

Frédéric Havet, Nicolas Trotignon, Jørgen Bang-Jensen, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), 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), Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Financial support from the Danish National Science research council (FNU) (under grant no. 09-066741)., Electronic Notes on Discrete Mathematics, ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), 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 INRIA

Subjects
FOS: Computer and information sciences, Polynomial, Discrete Mathematics (cs.DM), General Computer Science, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Mathematical proof, 01 natural sciences, Theoretical Computer Science, Combinatorics, 3-SAT, Computer Science::Discrete Mathematics, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 05C85, Mathematics, Subdivision, Discrete mathematics, Mathematics::Combinatorics, business.industry, Applied Mathematics, 020206 networking & telecommunications, Digraph, Graph, NP-completeness, induced paths and cycles, 010201 computation theory & mathematics, Combinatorics (math.CO), linkings, business, Computer Science(all), Computer Science - Discrete Mathematics, digraphs
Abstract

International audience; We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) G, does it contain an induced subdivision of a prescribed digraph D? The complexity of this problem depends on D and on whether G must be an oriented graph or is allowed to contain 2-cycles. We give a number of examples of polynomial instances as well as several NP-completeness proofs.

Published
2012
Full Text
View/download PDF

33. Acyclic Edge-Coloring of Planar Graphs

Author

L. Sunil Chandran, Tobias Müller, Nathann Cohen, Manu Basavaraju, and Frédéric Havet

Subjects
Discrete mathematics, Conjecture, Planar straight-line graph, General Mathematics, Graph, Planar graph, Combinatorics, symbols.namesake, Edge coloring, Planar, Pathwidth, symbols, Computer Science & Automation, Mathematics
Abstract

A proper edge-coloring with the property that every cycle contains edges of at least three distinct colors is called an acyclic edge-coloring. The acyclic chromatic index of a graph G, denoted. chi'(alpha)(G), is the minimum k such that G admits an acyclic edge-coloring with k colors. We conjecture that if G is planar and Delta(G) is large enough, then chi'(alpha) (G) = Delta (G). We settle this conjecture for planar graphs with girth at least 5. We also show that chi'(alpha) (G)

Published
2011
Full Text
View/download PDF

34. k-L(2,1)-labelling for planar graphs is NP-complete for k≥4

Author

Steven D. Noble, Nicole Eggemann, and Frédéric Havet

Subjects
Discrete mathematics, Vertex (graph theory), Applied Mathematics, Complete graph, Graph, Planar graph, Combinatorics, symbols.namesake, Planar, Integer, Labelling, symbols, Discrete Mathematics and Combinatorics, NP-complete, Mathematics
Abstract

A mapping from the vertex set of a graph G=(V,E) into an interval of integers {0,...,k} is an L(2,1)-labelling of G of span k if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices at distance 2 are mapped onto distinct integers. It is known that, for any fixed k>=4, deciding the existence of such a labelling is an NP-complete problem while it is polynomial for [email protected]?3. For even k>=8, it remains NP-complete when restricted to planar graphs. In this paper, we show that it remains NP-complete for any k>=4 by reduction from Planar Cubic Two-Colourable Perfect Matching. Schaefer stated without proof that Planar Cubic Two-Colourable Perfect Matching is NP-complete. In this paper we give a proof of this.

Published
2010
Full Text
View/download PDF

35. Acyclic edge-colouring of planar graphs. Extended abstract

Author

Nathann Cohen, Frédéric Havet, and Tobias Müller

Subjects
Discrete mathematics, Clique-sum, Planar straight-line graph, Applied Mathematics, 1-planar graph, Planar graph, Combinatorics, symbols.namesake, Pathwidth, Graph power, Chordal graph, Outerplanar graph, symbols, Discrete Mathematics and Combinatorics, Mathematics
Abstract

A proper edge-colouring with the property that every cycle contains edges of at least three distinct colours is called an acyclic edge-colouring. The acyclic chromatic index of a graph G, denoted χ a ′ ( G ) is the minimum k such that G admits an acyclic edge-colouring with k colours. We conjecture that if G is planar and Δ ( G ) is large enough then χ a ′ ( G ) = Δ ( G ) . We settle this conjecture for planar graphs with girth at least 5 and outerplanar graphs. We also show that if G is planar then χ a ′ ( G ) ⩽ Δ ( G ) + 25 .

Published
2009
Full Text
View/download PDF

36. Complexity of (p,1)-total labelling

Author

Frédéric Havet and Stéphan Thomassé

Subjects
Discrete mathematics, Vertex (graph theory), Applied Mathematics, 010102 general mathematics, 0102 computer and information sciences, 01 natural sciences, Upper and lower bounds, Graph, Combinatorics, 010201 computation theory & mathematics, Labelling, Bipartite graph, Discrete Mathematics and Combinatorics, Cubic graph, Regular graph, 0101 mathematics, Graph labelling, Mathematics
Abstract

A (p,1)-total labelling of a graph G=(V,E) is a total colouring L from V@?E into {0,...,l} such that |L(v)-L(e)|>=p whenever an edge e is incident to a vertex v. The minimum l for which G admits a (p,1)-total labelling is denoted by @l"p(G). The case p=1 corresponds to the usual notion of total colouring, which is NP-hard to compute even for cubic bipartite graphs [C.J. McDiarmid, A. Sanchez-Arroyo, Total colouring regular bipartite graphs is NP-hard, Discrete Math. 124 (1994), 155-162]. In this paper we assume p>=2. It is easy to show that @l"p(G)>=@D+p-1, where @D is the maximum degree of G. Moreover, when G is bipartite, @D+p is an upper bound for @l"p(G), leaving only two possible values. In this paper, we completely settle the computational complexity of deciding whether @l"p(G) is equal to @D+p-1 or to @D+p when G is bipartite. This is trivial when @D@?p, polynomial when @D=3 and p=2, and NP-complete in the remaining cases.

Published
2009
Full Text
View/download PDF

37. Choosability of the square of planar subcubic graphs with large girth

Author

Frédéric Havet, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), 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), 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, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Planar graph, Theoretical Computer Science, Choice number, Combinatorics, symbols.namesake, Planar, List colouring, 010201 computation theory & mathematics, Square of a graph, symbols, Discrete Mathematics and Combinatorics, 0101 mathematics, Bounded density, Mathematics
Abstract

International audience; We show that the choice number of the square of a subcubic graph with maximum average degree less than 18/7 is at most 6. As a corollary, we get that the choice number of the square of a subcubic planar graph with girth at least 9 is at most 6. We then show that the choice number of the square of a subcubic planar graph with girth at least 13 is at most 5.

Published
2009
Full Text
View/download PDF

38. Hoàng–Reed conjecture holds for tournaments

Author

Stéphan Thomassé, Frédéric Havet, and Anders Yeo

Subjects
Discrete mathematics, Class (set theory), Conjecture, 010102 general mathematics, Structure (category theory), Digraph, 0102 computer and information sciences, Directed graph, 01 natural sciences, Theoretical Computer Science, Combinatorics, 010201 computation theory & mathematics, Triangle structure, Discrete Mathematics and Combinatorics, Tournament, 0101 mathematics, Mathematics
Abstract

Hoang-Reed conjecture asserts that every digraph D has a collection C of circuits C"1,...,C"@d"^"+, where @d^+ is the minimum outdegree of D, such that the circuits of C have a forest-like structure. Formally, |V(C"i)@?(V(C"1)@?...@?V(C"i"-"1))|=

Published
2008
Full Text
View/download PDF

39. (p,1)-Total labelling of graphs

Author

Min-Li Yu and Frédéric Havet

Subjects
Discrete mathematics, Combinatorics, Conjecture, Integer, Labelling, Maximum difference, Incident edge, Discrete Mathematics and Combinatorics, Upper and lower bounds, Graph, Theoretical Computer Science, Mathematics, Vertex (geometry)
Abstract

A (p,1)-total labelling of a graph G is an assignment of integers to V(G)@?E(G) such that: (i) any two adjacent vertices of G receive distinct integers, (ii) any two adjacent edges of G receive distinct integers, and (iii) a vertex and its incident edge receive integers that differ by at least p in absolute value. The span of a (p,1)-total labelling is the maximum difference between two labels. The minimum span of a (p,1)-total labelling of G is called the (p,1)-total number and denoted by @l"p^T(G). We provide lower and upper bounds for the (p,1)-total number. In particular, generalizing the Total Colouring Conjecture, we conjecture that @l"p^T=

Published
2008
Full Text
View/download PDF

40. Finding good 2-partitions of digraphs I. Hereditary properties

Author

Frédéric Havet, Jørgen Bang-Jensen, Department of Mathematics and Computer Science [Odense] (IMADA), 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 (... - 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), Labex UCN@Sophia, Sophia Antipolis, 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
Strongly connected component, General Computer Science, polynomial, 0102 computer and information sciences, Vertex partition, Disjoint sets, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, semicomplete digraph, out-branching, Theoretical Computer Science, Combinatorics, Computer Science::Discrete Mathematics, Partition (number theory), Tournament, splitting digraphs, 0101 mathematics, Mathematics, minimum degree, NP-complete, Discrete mathematics, oriented, 2-partition, 010102 general mathematics, acyclic, Digraph, feedback vertex set, partition, tournament, Has property, 010201 computation theory & mathematics, Feedback vertex set
Abstract

We study the complexity of deciding whether a given digraph D has a vertex-partition into two disjoint subdigraphs with given structural properties. Let H and E denote the following two sets of natural properties of digraphs: H = {acyclic, complete, arcless, oriented (no 2-cycle), semicomplete, symmetric, tournament} and E = {strongly connected, connected, minimum out-degree at least 1, minimum in-degree at least 1, minimum semi-degree at least 1, minimum degree at least 1, having an out-branching, having an in-branching}. In this paper, we determine the complexity of deciding, for any fixed pair of positive integers k 1 , k 2 , whether a given digraph has a vertex partition into two digraphs D 1 , D 2 such that | V ( D i ) | ź k i and D i has property P i for i = 1 , 2 when P 1 ź H and P 2 ź H ź E . We also classify the complexity of the same problems when restricted to strongly connected digraphs.The complexity of the 2-partition problems where both P 1 and P 2 are in E is determined in the companion paper 2.

Published
2016
Full Text
View/download PDF

41. Subidvisions de cycles orientés dans les graphes dirigés de fort nombre chromatique

Author

Nicolas Nisse, Frédéric Havet, Nathann Cohen, William Lochet, Laboratoire de Recherche en Informatique (LRI), 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 (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), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), 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), LRI-GALAC, ANR-13-BS02-0007,Stint,Structures Interdites(2013), École normale supérieure de Lyon (ENS de Lyon), LRI - CNRS, University Paris-Sud, LIP - ENS Lyon, INRIA Sophia Antipolis - I3S, Graphes, Algorithmes et Combinatoire (LRI) (GALaC - 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), 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), École normale supérieure - Lyon (ENS Lyon), 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), É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 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)

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Strongly connected component, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, Orientation (graph theory), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, Computer Science::Discrete Mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Chromatic scale, 0101 mathematics, Mathematics, Subdivision, Mathematics::Combinatorics, business.industry, 010102 general mathematics, Digraph, Arbitrarily large, 010201 computation theory & mathematics, Geometry and Topology, Combinatorics (math.CO), business
Abstract

An {\it oriented cycle} is an orientation of a undirected cycle.We first show that for any oriented cycle $C$, there are digraphs containing no subdivision of $C$ (as a subdigraph) and arbitrarily large chromatic number.In contrast, we show that for any $C$ is a cycle with two blocks, every strongly connected digraph with sufficiently large chromatic number contains a subdivision of $C$. We prove a similar result for the antidirected cycle on four vertices (in which two vertices have out-degree $2$ and two vertices have in-degree $2$).; Un {\it cycle orienté} est l'orientation d'un cycle. Nous prouvons que pour tout cycle orienté $C$ il existe des graphes dirigés sans subdivisions de $C$ (en tant que sous graphe) et de nombre chromatique arbitrairement grand. Par ailleurs, nous prouvons que pour tout cycle a deux bloques, tout graphe dirigé fortement connexe de nombre chromatique suffisamment grand contient une subdivision de $C$. Nous prouvons aussi un resultat semblable sur le cycle antidirigé de taille quatre (avec deux sommets de degré sortant $2$ et deux sommets de degré entrant $2$).

Published
2016
Full Text
View/download PDF

42. Minimum-Density Identifying Codes in Square Grids

Author

Frédéric Havet, Myriam Preissmann, Marwane Bouznif, Optimisation Combinatoire (G-SCOP_OC ), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), 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), Riccardo Dondi, ANR-13-BS02-0007,Stint,Structures Interdites(2013), 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 INRIA Sophia Antipolis - I3S

Subjects
Square tiling, Discrete mathematics, Discharging method, Neighbourhood (graph theory), square grid, 010103 numerical & computational mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Vertex (geometry), Combinatorics, identifying code, 010201 computation theory & mathematics, discharging method, 0101 mathematics, Minimum density, Mathematics
Abstract

An identifying code in a graph $G$ is a subset of vertices with the property that for each vertex $v \in V(G)$, the collection of elements of $C$ at distance at most $1$ from $v$ is non-empty and distinct from the collection of any other vertex. We consider the minimum density $d^*({\cal S}_k)$ of an identifying code in the square grid ${\cal S}_k$ of height $k$ (i.e. with vertex set $ \mathbb{Z} \times \{1, \dots , k\}$).Using the Discharging Method, we prove $\displaystyle \frac{7}{20} + \frac{1}{20k} \leq d^*({\cal S}_k) \leq \min \left\{\frac{2}{5}, \frac{7}{20} + \frac{3}{10k} \right\}$, and $\displaystyle d^*({\cal S}_3) =\frac{3}{7}$.

Published
2016
Full Text
View/download PDF

43. Complexity of greedy edge-colouring

Author

A. Karolinna Maia, Min-Li Yu, Frédéric Havet, 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), Universidade Federal do Ceará = Federal University of Ceará (UFC), University of the Fraser Valley (UFV), CNRS-FUNCAP GAIATO, Université Nice Sophia Antipolis (... - 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 (... - 2019) (UNS)

Subjects
Mathematical optimization, General Computer Science, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Data structure, 01 natural sciences, Graph, law.invention, Combinatorics, Greedy coloring, 010201 computation theory & mathematics, law, Line graph, 0202 electrical engineering, electronic engineering, information engineering, NP-complete, Greedy algorithm, Computer Science(all), Mathematics
Abstract

International audience; The Grundy index of a graph G = (V, E) is the greatest number of colours that the greedy edge-colouring algorithm can use on G. We prove that the problem of determining the Grundy index of a graph G = (V, E) is NP-hard for general graphs. We also show that this problem is polynomial-time solvable for caterpillars. More specifically, we prove that the Grundy index of a caterpillar is (G) or (G) + 1 and present a polynomial-time algorithm to determine it exactly.

Published
2015
Full Text
View/download PDF

44. Compressing two-dimensional routing tables with order

Author

Frédéric Havet, Joanna Moulierac, Frédéric Giroire, 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), ANR-11-LABX-0031,UCN@SOPHIA,Réseau orienté utilisateur(2011), 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), INRIA Sophia Antipolis, INRIA, and ANR-13-BS02-0007,Stint,Structures Interdites(2013)

Subjects
Dynamic Source Routing, Theoretical computer science, Equal-cost multi-path routing, FPT, Geographic routing, 0102 computer and information sciences, 02 engineering and technology, Source routing, 01 natural sciences, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, compact tables, approximation algorithm, routing tables, Mathematics, Static routing, Applied Mathematics, Path vector protocol, DSRFLOW, 020206 networking & telecommunications, Routing domain, routing, 010201 computation theory & mathematics, complexity, software defined networks
Abstract

International audience; A communication in a network is a pair of nodes (s, t). The node s is called the source source and t the destination. A communication set is a set of distinct communications, i.e. two communications might have the same source or the same destination, but they cannot have both same source and same destination. A routing of a communication (s, t) is a path in the network from s to t. A routing of a communication set is a union of routings of its communications. At each node, there is a set X of communications whose routing path goes through this node. The node needs to be able to find for each communication (s,t) in X, the port that the routing path of (s,t) uses to leave it. An easy way of doing it is to store the list of all triples (s,t,k), where (s, t) ∈ X and k is the port used by the (s, t)-path to leave the node. Such triples are called communication triples. However, such a list might be very large. Motivated by routing in telecommunication network using Software Defined Network Technologies, we consider the problem of compacting this list using aggregation rules. Indeed, SDN routers use specific memory which is expensive and of small capacity. Hence, in addition, we can use some additional triples, called ∗-triples. As an example, a t-destination triple (∗, t, p), means that every communication with destination t leaves on port p. We carry out in this work a study of the problem complexity, providing results of NP-completeness, of Fixed-Parameter Tractability and approximation algorithms.

Published
2015

45. On the proper orientation number of bipartite graphs

Author

Júlio Araújo, Frédéric Havet, Phablo F. S. Moura, Nathann Cohen, Susanna F. de Rezende, Universidade Federal do Ceará = Federal University of Ceará (UFC), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Instituto de Matemática e Estatística (IME), Universidade de São Paulo (USP), 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), Parallelism, Graphs and Optimization Research Group (ParGO), CNPq-Brazil (477203/2012-4), FUNCAP/CNRS INC-0083-00047.01.00/13, FAPESP-Brazil (Proc. 2011/16348-0, 2013/19179-0, 2013/03447-6), ANR-13-BS02-0007,Stint,Structures Interdites(2013), INRIA, Universidade de São Paulo = University of São Paulo (USP), 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, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], graph colouring, General Computer Science, Graph colouring, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Digraph, Graph, hardness, Theoretical Computer Science, Combinatorics, Edge-transitive graph, Graph power, bipartite graph, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Bipartite graph, proper orientation, Bound graph, Graph coloring, Mathematics
Abstract

An {\it orientation} of a graph~$G$ is a digraph~$D$ obtained from~$G$ by replacing each edge by exactly one of the two possible arcs with the same endvertices. For each~$v \in V(G)$, the \emph{indegree} of~$v$ in~$D$, denoted by~$d^-_D(v)$, is the number of arcs with head~$v$ in~$D$. An orientation~$D$ of~$G$ is \emph{proper} if~$d^-_D(u)\neq d^-_D(v)$, for all~$uv\in E(G)$. The \emph{proper orientation number} of a graph~$G$, denoted by~$\po(G)$, is the minimum of the maximum indegree over all its proper orientations. In this paper, we prove that~$\po(G) \leq \left\lfloor \left(\Delta(G) + \sqrt{\Delta(G)}\right)/2 \right\rfloor+ 1$ if~$G$ is a bipartite graph, and~$\po(G)\leq 4$ if~$G$ is a tree. % Moreover, we show that deciding whether the proper orientation number is at most~2 and at most~3 % is an $\NP$-complete problem for planar subcubic graphs and planar bipartite graphs, respectively. It is well-known that~$\po(G)\leq \Delta(G)$, for every graph~$G$. However, we prove that deciding whether~$\po(G)\leq \Delta(G)-1$ is already an~$\NP$-complete problem. We also show that it is~$\NP$-complete to decide whether~$\po(G)\leq 2$, for planar \emph{subcubic} graphs~$G$. Moreover, we prove that it is~$\NP$-complete to decide whether $\po(G)\leq 3$, for planar bipartite graphs~$G$ with maximum degree~5.; Une {\it orientation} d'un graphe~$G$ est un digraphe~$D$ obtenu á partir de $G$ en remplaçant chaque arête par exactement un des deux arcs possibles avec les mêmes extremités. Pour tout $v\in V(G)$, le {\it dégré entrant} de $v$ dans $D$, noté $d^-_D(v)$, est le nombre d'arcs de $D$ ayant $v$ pour tête. Une orientation~$D$ de $G$ est {\it propre} si~$d^-_D(u)\neq d^-_D(v)$, pour tout~$uv\in E(G)$. L'{\it indice d'orientation propre} d'un graphe $G$, noté~$\po(G)$, est le plus petit dégré maximum d'une orientation propre de $G$. Dans ce papier, nous prouvons que $\po(G) \leq \left\lfloor \left(\Delta(G) + \sqrt{\Delta(G)}\right)/2 \right\rfloor+ 1$ si~$G$ est un graphe biparti, et~$\po(G)\leq 4$ si~$G$ est un arbre. Il est connu que~$\po(G)\leq \Delta(G)$, pour tout graphe~$G$. En revancche, nous prouvons que décider si~$\po(G)\leq \Delta(G)-1$ est déjá un probléme $\NP$-complet. Nous montrons aussi qu'il est $\NP$-complet de décider si~$\po(G)\leq 2$ pour un graphe planaire subcubique~$G$. Enfin nous montrons qu'il est $\NP$-complet de décider si $\po(G)\leq 3$ pour un graphe planaire biparti~$G$ de dégré maximum~5.

Published
2015
Full Text
View/download PDF

46. REPARTITORS, SELECTORS AND SUPERSELECTORS

Author

Frédéric Havet

Subjects
Vertex (graph theory), Discrete mathematics, 021103 operations research, Computer Networks and Communications, 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, Disjoint sets, 01 natural sciences, Graph, Combinatorics, 010201 computation theory & mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics
Abstract

An (n, p, f)-network G is a graph (V, E) where the vertex set V is partitioned into four subsets [Formula: see text] and [Formula: see text] called respectively the priorities, the ordinary inputs, the outputs and the switches, satisfying the following constraints: there are p priorities, n - p ordinary inputs and n + f outputs; each priority, each ordinary input and each output is connected to exactly one switch; switches have degree at most 4. An (n, p, f)-network is an (n, p, f)-repartitor if for any disjoint subsets [Formula: see text] and [Formula: see text] of [Formula: see text] with [Formula: see text] and [Formula: see text], there exist in G, n edge-disjoint paths, p of them from [Formula: see text] to [Formula: see text] and the n - p others joining [Formula: see text] to [Formula: see text]. The problem is to determine the minimum number R(n, p, f) of switches of an (n, p, f)-repartitor and to construct a repartitor with the smallest number of switches. In this paper, we show how to build general repartitors from (n, 0, f)-repartitors also called (n, n + f)-selectors. We then consrtuct selectors using more powerful networks called superselectors. An (n, 0, 0)-network is an n-superselector if for any subsets [Formula: see text] and [Formula: see text] with [Formula: see text], there exist in G, [Formula: see text] edge-disjoint paths joining [Formula: see text] to [Formula: see text]. We show that the minimum number of switches of an n-superselector S+ (n) is at most 17n + O(log(n)). We then deduce that [Formula: see text] if [Formula: see text], R(n, p, f) ≤ 18n + 34f + O( log (n + f)), if [Formula: see text] and [Formula: see text] if [Formula: see text]. Finally, we give lower bounds for R(n, 0, f) and S+ (n) and show optimal networks for small value of n.

Published
2006
Full Text
View/download PDF

47. Improper Colourings of Unit Disk Graphs

Author

Jean-Sébastien Sereni, Frédéric Havet, and Ross J. Kang

Subjects
Combinatorics, Discrete mathematics, Block graph, Indifference graph, Chordal graph, Unit disk graph, Applied Mathematics, Outerplanar graph, Discrete Mathematics and Combinatorics, Graph coloring, Unit disk, 1-planar graph, Mathematics
Published
2005
Full Text
View/download PDF

48. Trees with three leaves are (n+1)-unavoidable

Author

Frédéric Havet and S. Ceroi

Subjects
Combinatorics, Unavoidable, Conjecture, Degree (graph theory), Applied Mathematics, Discrete Mathematics and Combinatorics, Order (group theory), Tournament, Tree (set theory), Tree, Mathematics
Abstract

We prove that every tree of order n⩾5 with three leaves is (n+1)-unavoidable. More precisely, we prove that every tree A with three leaves of order n is contained in every tournament T of order n+1 except if (T;A) is (R5;S3+) or its dual, where R5 is the regular tournament on five vertices and S3+ is the outstar of degree three, i.e. the tree consisting of a root dominating three leaves. We then deduce that Sumner's conjecture is true for trees with four leaves, i.e. every tree of order n with four leaves is (2n−2)-unavoidable.

Published
2004
Full Text
View/download PDF

49. On Unavoidability of Trees with k Leaves

Author

Frédéric Havet

Subjects
Combinatorics, Discrete mathematics, Vertex (graph theory), Conjecture, Discrete Mathematics and Combinatorics, Digraph, Tournament, Upper and lower bounds, Theoretical Computer Science, Mathematics
Abstract

A digraph is said to be n-unavoidable if every tournament of order n contains it as a subgraph. Let f(n) be the smallest integer such that every oriented tree of order n is f(n)-unavoidable. Sumner (see [6]) noted that f(n)≥2n−2 and conjectured that equality holds. Havet and Thomasse [4] established the upper bound . Sumner's conjecture is implied by a stronger one due to Havet and Thomasse: g(k)≤k−1 where g(k) is the smallest integer such that every oriented tree of order n with k leaves is (n+g(k)) -unavoidable. Haggkvist and Thomason [1] proved that g(k)≤2 512k3 and Havet [2] proved g(3)≤5. A node is a vertex with sum of out- and indegree at least three in an oriented tree. An oriented tree is constructible if every path from a node to another node is not directed with first and last block (maximal directed subpath) of length at least two and every path from node to a leaf has first block of length at least two. In this paper, we prove that Havet and Thomasse's conjecture is true for constructible trees.

Published
2003
Full Text
View/download PDF

50. Finding a subdivision of a digraph

Author

Frédéric Havet, A. Karolinna Maia, Jørgen Bang-Jensen, Department of Mathematics and Computer Science [Odense] (IMADA), 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 (... - 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-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), 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, Polynomial, General Computer Science, business.industry, 010102 general mathematics, Digraph, 0102 computer and information sciences, Directed graph, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 16. Peace & justice, Mathematical proof, 01 natural sciences, Theoretical Computer Science, Combinatorics, 010201 computation theory & mathematics, 0101 mathematics, business, Subdivision, Mathematics
Abstract

International audience; We consider the following problem for oriented graphs and digraphs: Given a directed graph D, does it contain a subdivision of a prescribed digraph F? We give a number of examples of polynomial instances, several NP-completeness proofs as well as a number of conjectures and open problems.

Published
2015
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results