Author: "ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)" - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)"' showing total 53 results

Start Over Author "ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)"

53 results on '"ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)"'

1. Deciding the Erdős-Pósa property in 3-connected digraphs ⋆

Author: Bensmail, Julien, Campos, Victor, Maia, Ana, Nisse, Nicolas, Silva, Ana, 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), Parallelism, Graphs and Optimization Research Group (ParGO), Universidade Federal do Ceará = Federal University of Ceará (UFC), Inria EA CANOE, projet Stic Am-Sud GALOP, projet CAPES-Cofecub Graphs, Optimization, Combinatorics and Algorithms, ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), ANR-17-CE22-0016,MultiMod,Routage dans les grands réseaux de transports multi-modal(2017), and ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015)
Subjects: Erdős-Pósa property Planar digraphs Butterfly minor, Butterfly minor, Planar digraphs, [INFO]Computer Science [cs], Erdős-Pósa property
Abstract: International audience; A (di)graph H has the Erdős-Pósa (EP) property for (butterfly) minors if there exists a function f : N → N such that, for any k ∈ N and any (di)graph G, either G contains at least k pairwise vertexdisjoint copies of H as (butterfly) minor, or there exists a subset T of at most f (k) vertices such that H is not a (butterfly) minor of G − T. It is a well known result of Robertson and Seymour that an undirected graph has the EP property if and only if it is planar. This result was transposed to digraphs by Amiri, Kawarabayashi, Kreutzer and Wollan, who proved that a strong digraph has the EP property for butterfly minors if, and only if, it is a butterfly minor of a cylindrical grid. Contrary to the undirected case where a graph is planar if, and only if, it is the minor of some grid, not all planar digraphs are butterfly minors of a cylindrical grid. In this work, we characterize the planar digraphs that have a butterfly model in a cylindrical grid. In particular, this leads to a linear-time algorithm that decides whether a weakly 3-connected strong digraph has the EP property.
Published: 2023

2. From branchings to flows: a study of an Edmonds' like property to arc-disjoint branching flows

Author: Carvalho, Cláudio, Costa, Jonas, Lopes, Raul, Maia, Ana Karolinna, Nisse, Nicolas, Sales, Cláudia, Universidade Federal do Ceará = Federal University of Ceará (UFC), Departamento de Computaçãos [Ceará] (DC/UFC), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), UFC - Universidade Federal do Ceará = Federal University of Ceará, Université Côte d'Azur (UCA), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria), Centre National de la Recherche Scientifique (CNRS), 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), STIC-AmSud project GALOP (Graphs ALgorithms for Optimization Problems), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), and ANR-18-CE40-0025,ASSK,Algorithmes avec décomposition moins connu: graphes et matroids(2018)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Branchings, General Computer Science, Digraphs, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Arc-disjoint flows, Discrete Mathematics and Combinatorics, Branching flows, [MATH]Mathematics [math], Theoretical Computer Science
Abstract: An s-branching flow f in a network N = (D, u), where u is the capacity function, is a flow thatreaches every vertex in V(D) from s while loosing exactly one unit of flow in each vertex other thans. Bang-Jensen and Bessy [TCS, 2014] showed that, when every arc has capacity n − 1, a network Nadmits k arc-disjoint s-branching flows if and only if its associated digraph D contains k arc-disjoints-branchings. Thus a classical result by Edmonds stating that a digraph contains k arc-disjoints-branchings if and only if the indegree of every set X ⊆ V (D) \ {s} is at least k also characterizesthe existence of k arc-disjoint s-branching flows in those networks, suggesting that the larger thecapacities are, the closer an s-branching flow is from simply being an s-branching. This observationis further implied by results by Bang-Jensen et al. [DAM, 2016] showing that there is a polynomialalgorithm to find the flows (if they exist) when every arc has capacity n − c, for every fixed c ≥ 1,and that such an algorithm is unlikely to exist for most other choices of the capacities. In this paper,we investigate how a property that is a natural extension of the characterization by Edmonds’ relatesto the existence of k arc-disjoint s-branching flows in networks. Although this property is alwaysnecessary for the existence of the flows, we show that it is not always sufficient and that it is hardto decide if the desired flows exist even if we know beforehand that the network satisfies it. On thepositive side, we show that it guarantees the existence of the desired flows in some particular casesdepending on the choice of the capacity function or on the structure of the underlying graph of D,for example. We remark that, in those positive cases, polynomial time algorithms to find the flowscan be extracted from the constructive proofs.
Published: 2023

3. ( #» P 6 , triangle)-free digraphs have bounded dichromatic number

Author: Aboulker, Pierre, Aubian, Guillaume, Charbit, Pierre, Thomassé, Stéphan, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL), UFR Mathématiques et informatique [Sciences] - Université Paris Cité, Université Paris Cité (UPCité), École normale supérieure de Lyon (ENS de Lyon), group Casino/ENS Chair on Algorithmics andMachine Learning, ANR-21-CE48-0012,DAGDigDec,DAGs et Decompositions des Digraphes(2021), and ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
Subjects: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: The dichromatic number of an oriented graph is the minimum size of a partition of its vertices into acyclic induced subdigraphs. We prove that oriented graphs with no induced directed path on six vertices and no triangle have bounded dichromatic number. This is one (small) step towards the general conjecture asserting that for every oriented tree T and every integer k, any oriented graph that does not contain an induced copy of T nor a clique of size k has dichromatic number at most some function of k and T .
Published: 2023

4. Twin-width I: Tractable FO Model Checking

Author: Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant, 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), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), 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), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)
Subjects: FOS: Computer and information sciences, Model checking, Computer Science - Logic in Computer Science, Discrete Mathematics (cs.DM), 02 engineering and technology, 0102 computer and information sciences, 01 natural sciences, Combinatorics, Artificial Intelligence, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], Ball (mathematics), 0101 mathematics, Invariant (mathematics), Time complexity, Mathematics, Discrete mathematics, Sequence, 010102 general mathematics, 68Q25, Function (mathematics), Logic in Computer Science (cs.LO), 010201 computation theory & mathematics, Hardware and Architecture, Control and Systems Engineering, Bounded function, Embedding, 020201 artificial intelligence & image processing, F.2.2, Unit (ring theory), Software, Computer Science - Discrete Mathematics, Information Systems
Abstract: Inspired by a width invariant defined on permutations by Guillemot and Marx [SODA '14], we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width graphs, map graphs, $K_t$-free unit $d$-dimensional ball graphs, posets with antichains of bounded size, and proper subclasses of dimension-2 posets all have bounded twin-width. On all these classes (except map graphs without geometric embedding) we show how to compute in polynomial time a sequence of $d$-contractions, witness that the twin-width is at most $d$. We show that FO model checking, that is deciding if a given first-order formula $\phi$ evaluates to true for a given binary structure $G$ on a domain $D$, is FPT in $|\phi|$ on classes of bounded twin-width, provided the witness is given. More precisely, being given a $d$-contraction sequence for $G$, our algorithm runs in time $f(d,|\phi|) \cdot |D|$ where $f$ is a computable but non-elementary function. We also prove that bounded twin-width is preserved by FO interpretations and transductions (allowing operations such as squaring or complementing a graph). This unifies and significantly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes, such as the FPT algorithm on bounded-width posets by Gajarsk\'y et al. [FOCS '15]., Comment: 49 pages, 9 figures
Published: 2021

5. Pathlength of Outerplanar graphs

Author: Thomas Dissaux, Nicolas Nisse, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Springer, ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), ANR-17-EURE-0004,UCA DS4H,UCA Systèmes Numériques pour l'Homme(2017), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), and Inria & Université Nice Sophia Antipolis, CNRS, I3S, Sophia Antipolis, France
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], [INFO]Computer Science [cs], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: International audience; A path-decomposition of a graph G = (V, E) is a sequence of subsets of V , called bags, that satisfy some connectivity properties. The length of a path-decomposition of a graph G is the greatest distance between two vertices that belong to a same bag and the pathlength, denoted by p (G), of G is the smallest length of its path-decompositions. This parameter has been studied for its algorithmic applications for several classical metric problems like the minimum eccentricity shortest path problem, the line-distortion problem, etc. However, deciding if the pathlength of a graph G is at most 2 is NP-complete, and the best known approximation algorithm has a ratio 2 (there is no c-approximation with c < 3 2 unless P = N P). In this work, we focus on the study of the pathlength of simple sub-classes of planar graphs. We start by designing a linear-time algorithm that computes the pathlength of trees. Then, we show that the pathlength of cycles with n vertices is equal to n 2. Finally, our main result is a (+1)-approximation algorithm for the pathlength of outerplanar graphs. This algorithm is based on a characterization of almost optimal (of length at most p (G)+1) path-decompositions of outerplanar graphs. * This work is partially funded by the project UCA JEDI (ANR-15-IDEX-01) and EUR DS4H Investments in the Future (ANR-17-EURE-004).
Published: 2022

6. Deciding twin-width at most 4 is NP-complete

Author: Bergé, Pierre, Bonnet, Édouard, Déprés, Hugues, 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), ANR-21-CE48-0014,TWIN-WIDTH,Twin-width: théorie et applications(2021), and ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
Subjects: FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Computational Complexity (cs.CC), 68Q17, Computer Science - Computational Complexity, lower bounds, Theory of computation → Fixed parameter tractability, Theory of computation → Graph algorithms analysis, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], Combinatorics (math.CO), F.2.2, Computer Science - Discrete Mathematics, Twin-width
Abstract: We show that determining if an $n$-vertex graph has twin-width at most 4 is NP-complete, and requires time $2^{\Omega(n/\log n)}$ unless the Exponential-Time Hypothesis fails. Along the way, we give an elementary proof that $n$-vertex graphs subdivided at least $2 \log n$ times have twin-width at most 4. We also show how to encode trigraphs $H$ (2-edge colored graphs involved in the definition of twin-width) into graphs $G$, in the sense that every $d$-sequence (sequence of vertex contractions witnessing that the twin-width is at most $d$) of $G$ inevitably creates $H$ as an induced subtrigraph, whereas there exists a partial $d$-sequence that actually goes from $G$ to $H$. We believe that these facts and their proofs can be of independent interest., Comment: 30 pages, 17 figures
Published: 2022

7. Twin-width IV: ordered graphs and matrices

Author: Bonnet, Édouard, Giocanti, Ugo, de Mendez, Patrice Ossona, Simon, Pierre, Thomassé, Stéphan, Toruńczyk, Szymon, 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), Centre d'Analyse et de Mathématique sociales (CAMS), École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS), Computer Science Institute of Charles University [Prague] (IUUK), Charles University [Prague] (CU), University of California [Berkeley] (UC Berkeley), University of California (UC), University of Varsaw, ANR-21-CE48-0014,TWIN-WIDTH,Twin-width: théorie et applications(2021), and ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
Subjects: FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Computer Science - Logic in Computer Science, Discrete Mathematics (cs.DM), Computational Complexity (cs.CC), 05A05, 05A16, 05C30, Logic in Computer Science (cs.LO), Computer Science - Computational Complexity, Computer Science - Data Structures and Algorithms, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], Combinatorics (math.CO), F.2.2, Computer Science - Discrete Mathematics
Abstract: We establish a list of characterizations of bounded twin-width for hereditary, totally ordered binary structures. This has several consequences. First, it allows us to show that a (hereditary) class of matrices over a finite alphabet either contains at least $n!$ matrices of size $n \times n$, or at most $c^n$ for some constant $c$. This generalizes the celebrated Stanley-Wilf conjecture/Marcus-Tardos theorem from permutation classes to any matrix class over a finite alphabet, answers our small conjecture [SODA '21] in the case of ordered graphs, and with more work, settles a question first asked by Balogh, Bollob\'as, and Morris [Eur. J. Comb. '06] on the growth of hereditary classes of ordered graphs. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width., Comment: 53 pages, 18 figures
Published: 2022

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

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

9. Good orientations of unions of edge‐disjoint spanning trees

Author: Jing Huang, Matthias Kriesell, Stéphane Bessy, Jørgen Bang-Jensen, 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), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), University of Victoria [Canada] (UVIC), Institute of Mathematics - Technical University of Ilmenau, Ilmenau University of Technology [Germany] (TU), and ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
Subjects: acyclic orientation, 0102 computer and information sciences, Disjoint sets, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Edge (geometry), 01 natural sciences, Polynomial algorithm, 2T-graph, branchings, Combinatorics, vertex ordering, NP-complete problem, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], acyclic digraph, Discrete Mathematics and Combinatorics, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, Spanning tree, rigidity matroid, 010102 general mathematics, polynomial algorithm, generic circuit, spanning trees, 010201 computation theory & mathematics, Geometry and Topology, Acyclic orientation, NP-complete, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: In this paper, we exhibit connections between the following subjects: Tree packing in graphs and digraphs (both behave completely different), the rigidity matroid of a graph, Henneberg moves on trees, the conjectures of Thomassen and Matthews and Sumner, and (s,t)-orderings of digraphs. We do this by studying graphs which admit acyclic orientations that contain an out-branching and in-branching which are arc-disjoint (such an orientation is called good). A 2T-graph is a graph whose edge set can be decomposed into two edge-disjoint spanning trees. It is a well-known result due to Tutte and Nash-Williams, respectively, that every 4-edge-connected graph contains a spanning 2T-graph. Vertex-minimal 2T-graphs with at least two vertices which are known as generic circuits play an important role in rigidity theory for graphs. We prove that every generic circuit has a good orientation. Using this result we prove that if (Formula presented.) is 2T-graph whose vertex set has a partition (Formula presented.) so that each (Formula presented.) induces a generic circuit (Formula presented.) of (Formula presented.) and the set of edges between different (Formula presented.) 's form a matching in (Formula presented.), then (Formula presented.) has a good orientation. We also obtain a characterization for the case when the set of edges between different (Formula presented.) 's form a double tree, that is, if we contract each (Formula presented.) to one vertex, and delete parallel edges we obtain a tree. All our proofs are constructive and imply polynomial algorithms for finding the desired good orderings and the pairs of arc-disjoint branchings which certify that the orderings are good. We identify a structure which can be used to certify that a given 2T-graph does not have a good orientation.
Published: 2020

10. The (theta, wheel)-free graphs Part III: Cliques, stable sets and coloring

Author: Marko Radovanović, Kristina Vušković, Nicolas Trotignon, 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-19-CE48-0013,DIGRAPHS,Digraphes(2019), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), É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), 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), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)
Subjects: 010102 general mathematics, Induced subgraph, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Theoretical Computer Science, Vertex (geometry), Combinatorics, Part iii, Computational Theory and Mathematics, Computer Science::Discrete Mathematics, 010201 computation theory & mathematics, Independent set, Bounded function, FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Combinatorics (math.CO), Chromatic scale, 0101 mathematics, Time complexity, Mathematics
Abstract: International audience; A hole in a graph is a chordless cycle of length at least 4. A theta is a graph formed by three paths between the same pair of distinct vertices so that the union of any two of the paths induces a hole. A wheel is a graph formed by a hole and a node that has at least 3 neighbors in the hole. In this series of papers we study the class of graphs that do not contain as an induced subgraph a theta nor a wheel. In Part II of the series we prove a decomposition theorem for this class, that uses clique cutsets and 2-joins, and consequently obtain a polynomial time recognition algorithm for the class. In this paper we further use this decomposition theorem to obtain polynomial time algorithms for maximum weight clique, maximum weight stable set and coloring problems. We also show that for a graph $G$ in the class, if its maximum clique size is $\omega$, then its chromatic number is bounded by max$\{\omega,3\}$, and that the class is 3-clique-colorable.
Published: 2020

11. Twin-width VI: the lens of contraction sequences

Author: Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, 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é Paris Dauphine-PSL, Université Paris sciences et lettres (PSL), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), ANR-18-CE40-0025,ASSK,Algorithmes avec décomposition moins connu: graphes et matroids(2018), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), ANR-21-CE48-0014,TWIN-WIDTH,Twin-width: théorie et applications(2021), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), École normale supérieure - Lyon (ENS Lyon), Bonnet, Édouard, APPEL À PROJETS GÉNÉRIQUE 2018 - Algorithmes avec décomposition moins connu: graphes et matroids - - ASSK2018 - ANR-18-CE40-0025 - AAPG2018 - VALID, Digraphes - - DIGRAPHS2019 - ANR-19-CE48-0013 - AAPG2019 - VALID, and Twin-width: théorie et applications - - TWIN-WIDTH2021 - ANR-21-CE48-0014 - AAPG2021 - VALID
Subjects: FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Discrete Mathematics (cs.DM), [INFO] Computer Science [cs], Logic in Computer Science (cs.LO), 68R10, 05C85, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], Combinatorics (math.CO), F.2.2, Computer Science - Discrete Mathematics
Abstract: A contraction sequence of a graph consists of iteratively merging two of its vertices until only one vertex remains. The recently introduced twin-width graph invariant is based on contraction sequences. More precisely, if one puts red edges between two vertices representing non-homogeneous subsets, the twin-width is the minimum integer $d$ such that a contraction sequence keeps red degree at most $d$. By changing the condition imposed on the trigraphs (i.e., graphs with some edges being red) and possibly slightly tweaking the notion of contractions, we show how to characterize the well-established bounded rank-width, tree-width, linear rank-width, path-width, and proper minor-closed classes by means of contraction sequences. As an application we give a transparent alternative proof of the celebrated Courcelle's theorem (actually of its generalization by Courcelle, Makowsky, and Rotics), that MSO$_2$ (resp. MSO$_1$) model checking on graphs with bounded tree-width (resp. bounded rank-width) is fixed-parameter tractable in the size of the input sentence. We then explore new avenues along the general theme of contraction sequences both in order to refine the landscape between bounded tree-width and bounded twin-width (via spanning twin-width) and to capture more general classes than bounded twin-width. To this end, we define an oriented version of twin-width, where appearing red edges are oriented away from the newly contracted vertex, and the mere red out-degree should remain bounded. Surprisingly, classes of bounded oriented twin-width coincide with those of bounded twin-width. Finally we examine, from an algorithmic standpoint, the concept of partial contraction sequences, where, instead of terminating on a single-vertex graph, the sequence ends when reaching a particular target class., Comment: 27 pages, 3 figures
Published: 2022

12. On the minimum number of arcs in $k$-dicritical oriented graphs

Author: Aboulker, Pierre, Bellitto, Thomas, Havet, Frédéric, Rambaud, Clément, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL), Sorbonne Université (SU), 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é Côte d'Azur (UCA), group Casino/ENS Chair on Algorithmics and Machine Learning, ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), and ANR-21-CE48-0012,DAGDigDec,DAGs et Decompositions des Digraphes(2021)
Subjects: FOS: Computer and information sciences, Discrete Mathematics (cs.DM), FOS: Mathematics, Mathematics - Combinatorics, 05C20, Combinatorics (math.CO), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Computer Science - Discrete Mathematics
Abstract: The dichromatic number $\dic(D)$ of a digraph $D$ is the least integer $k$ such that $D$ can be partitioned into $k$ directed acyclic digraphs. A digraph is $k$-dicritical if $\dic(D) = k$ and each proper subgraph $D'$ of $D$ satisfies $\dic(D') \leq k-1$. An oriented graph is a digraph with no directed cycle of length $2$. For integers $k$ and $n$, we denote by $o_k(n)$ the minimum number of edges of a $k$-critical oriented graph on $n$ vertices (with the convention $o_k(n)=+\infty$ if there is no $k$-dicritical oriented graph of order $n$). The main result of this paper is a proof that $o_3(n) \geq \frac{7n+2}{3}$ together with a construction witnessing that $o_3(n) \leq \left \lceil \frac{5n}{2} \right \rceil$ for all $n \geq 12$. We also give a construction showing that for all sufficiently large $n$ and all $k\geq 3$, $o_k(n) < (2k-3)n$, disproving a conjecture of Hoshino and Kawarabayashi. Finally, we prove that, for all $k\geq 2$, $o_k(n) \geq \pth{ k - \frac{3}{4}-\frac{1}{4k-6}} n + \frac{3}{4(2k-3)}$, improving the previous best known lower bound of Bang-Jensen, Bellitto, Schweser and Stiebitz.
Published: 2022
Full Text: View/download PDF

13. Strengthening a theorem of Meyniel

Author: Deschamps, Quentin, Feghali, Carl, Kardoš, František, Legrand-Duchesne, Clément, Pierron, Théo, 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), 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), Faculty of Mathematics, Physics and Informatics [Bratislava] (FMPH/UNIBA), Comenius University in Bratislava, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), and ANR-18-CE40-0032,GrR,Reconfiguration de Graphes(2018)
Subjects: FOS: Computer and information sciences, Discrete Mathematics (cs.DM), General Mathematics, FOS: Mathematics, Mathematics - Combinatorics, [INFO]Computer Science [cs], Combinatorics (math.CO), Computer Science - Discrete Mathematics
Abstract: For an integer $k \geq 1$ and a graph $G$, let $\mathcal{K}_k(G)$ be the graph that has vertex set all proper $k$-colorings of $G$, and an edge between two vertices $\alpha$ and~$\beta$ whenever the coloring~$\beta$ can be obtained from $\alpha$ by a single Kempe change. A theorem of Meyniel from 1978 states that $\mathcal{K}_5(G)$ is connected with diameter $O(5^{|V(G)|})$ for every planar graph $G$. We significantly strengthen this result, by showing that there is a positive constant $c$ such that $\mathcal{K}_5(G)$ has diameter $O(|V(G)|^c)$ for every planar graph $G$., Comment: 9 pages, 1 figure
Published: 2022
Full Text: View/download PDF

14. Metric Dimension: from Graphs to Oriented Graphs

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

15. Spanning eulerian subdigraphs in semicomplete digraphs

Author: Havet, Frédéric, Bang-Jensen, Jørgen, Yeo, Anders, 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), University of Southern Denmark (SDU), This research was also supported by the Danish research council under grant number DFF 7014-00037B, Inria, CNRS, I3S, Université côte d'azur, DISCO, PICS, ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), 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: Semicomplete digraph, Mathematics::Combinatorics, Eulerian subdigraph, Computer Science::Discrete Mathematics, polynomial algorithm, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Tournament, Arc-connectivity
Abstract: A digraph is eulerian if it is connected and every vertex has its in-degree equal to its outdegree. Having a spanning eulerian subdigraph is thus a weakening of having a hamiltonian cycle. In this paper, we first characterize the pairs (D, a) of a semicomplete digraph D and an arc a such that D has a spanning eulerian subdigraph containing a. In particular, we show that if D is 2-arc-strong, then every arc is contained in a spanning eulerian subdigraph. We then characterize the pairs (D, a) of a semicomplete digraph D and an arc a such that D has a spanning eulerian subdigraph avoiding a. In particular, we prove that every 2-arc-strong semicomplete digraph has a spanning eulerian subdigraph avoiding any prescribed arc. We also prove the existence of a (minimum) function f (k) such that every f (k)-arc-strong semicomplete digraph contains a spanning eulerian subdigraph avoiding any prescribed set of k arcs. We conjecture that f (k) = k + 1 and establish this conjecture for k ≤ 3 and when the k arcs that we delete form a forest of stars. A digraph D is eulerian-connected if for any two distinct vertices x, y, the digraph D has a spanning (x, y)-trail. We prove that every 2-arc-strong semicomplete digraph is eulerianconnected. All our results may be seen as arc analogues of well-known results on hamiltonian paths and cycles in semicomplete digraphs.
Published: 2021

16. De la difficulté de trouver des chemins dissimilaires

Author: Al Zoobi, Ali, Coudert, David, Nisse, Nicolas, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), This work has been supported by the UCAJEDI Investments in the Future project managed by the National Research Agency (ANR-15-IDEX-01), project MULTIMOD (ANR-17-CE22-0016), project Digraphs (ANR-19-CE48-0013), and by Region Sud PACA., ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), ANR-17-CE22-0016,MultiMod,Routage dans les grands réseaux de transports multi-modal(2017), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], $k$ plus courts chemins simples, Similarité entre chemins
Abstract: International audience; Lorsque l'on demande à son GPS un chemin pour aller à La Rochelle, celui-ci propose généralement plusieurs chemins assez différents les uns des autres : l'un par l'autoroute, l'autre par la côte, un pas cher, etc. La notion de (dis)similarité entre deux chemins a été définie, dans la littérature, de différentes manières qui toutes sont liées à un ratio entre la longueur de leur intersection et une certaine fonction de leurs longueurs. Nous étudions la complexité de plusieurs variantes du problème du calcul de chemins "dissimilaires" (dont la mesure de similarité n'excède pas un certain seuil) entre deux sommets d'un graphe orienté et pondéré. Pour quatre des mesures les plus étudiées dans la littérature, nous donnons une preuve unifiée et simple du fait que trouver $k$ plus courts chemins dissimilaires est NP-complet. En pratique, ce que l'on cherche est une alternative à un ou des chemins que l'on connait a priori. Nos résultats principaux concernent ce type de problème. Plus précisément, pour chacune des quatre mesures considérées, nous montrons que si $k\geq 2 $chemins sont donnés, en trouver un nouveau qui soit dissimilaire des premiers est NP-complet. Enfin, nous montrons que si un chemin $P$ est donné, trouver un plus court chemin parmi ceux qui sont dissimilaires de $P$ est NP-complet. Ce dernier résultat est à mettre en contraste avec le fait que, pour l'une des mesures, trouver un chemin dissimilaire à un chemin donné peut être résolu très simplement en temps polynomial.
Published: 2021

17. Twin-width and polynomial kernels

Author: Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, Rémi Watrigant, 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é Paris Dauphine-PSL, Université Paris sciences et lettres (PSL), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), ANR-21-CE48-0014,TWIN-WIDTH,Twin-width: théorie et applications(2021), ANR-18-CE40-0025,ASSK,Algorithmes avec décomposition moins connu: graphes et matroids(2018), Bonnet, Édouard, Digraphes - - DIGRAPHS2019 - ANR-19-CE48-0013 - AAPG2019 - VALID, Twin-width: théorie et applications - - TWIN-WIDTH2021 - ANR-21-CE48-0014 - AAPG2021 - VALID, APPEL À PROJETS GÉNÉRIQUE 2018 - Algorithmes avec décomposition moins connu: graphes et matroids - - ASSK2018 - ANR-18-CE40-0025 - AAPG2018 - VALID, École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and École normale supérieure - Lyon (ENS Lyon)
Subjects: FOS: Computer and information sciences, General Computer Science, Discrete Mathematics (cs.DM), Applied Mathematics, Theory of computation �� Graph algorithms analysis, Theory of computation �� Fixed parameter tractability, [INFO] Computer Science [cs], Computational Complexity (cs.CC), Dominating Set, Computer Science Applications, Computer Science - Computational Complexity, lower bounds, Computer Science - Data Structures and Algorithms, kernelization, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), 05C85, [INFO]Computer Science [cs], Combinatorics (math.CO), F.2.2, Computer Science - Discrete Mathematics, Twin-width
Abstract: We study the existence of polynomial kernels for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twin-width. It was previously observed in [Bonnet et al., ICALP'21] that the problem k-Independent Set allows no polynomial kernel on graph of bounded twin-width by a very simple argument, which extends to several other problems such as k-Independent Dominating Set, k-Path, k-Induced Path, k-Induced Matching. In this work, we examine the k-Dominating Set and variants of k-Vertex Cover for the existence of polynomial kernels. As a main result, we show that k-Dominating Set does not admit a polynomial kernel on graphs of twin-width at most 4 under a standard complexity-theoretic assumption. The reduction is intricate, especially due to the effort to bring the twin-width down to 4, and it can be tweaked to work for Connected k-Dominating Set and Total k-Dominating Set with a slightly worse bound on the twin-width. On the positive side, we obtain a simple quadratic vertex kernel for Connected k-Vertex Cover and Capacitated k-Vertex Cover on graphs of bounded twin-width. These kernels rely on that graphs of bounded twin-width have Vapnik-Chervonenkis (VC) density 1, that is, for any vertex set X, the number of distinct neighborhoods in X is at most c��|X|, where c is a constant depending only on the twin-width. Interestingly the kernel applies to any graph class of VC density 1, and does not require a witness sequence. We also present a more intricate O(k^{1.5}) vertex kernel for Connected k-Vertex Cover. Finally we show that deciding if a graph has twin-width at most 1 can be done in polynomial time, and observe that most graph optimization/decision problems can be solved in polynomial time on graphs of twin-width at most 1., LIPIcs, Vol. 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), pages 10:1-10:16
Published: 2021

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

19. Twin-width III: Max Independent Set and Coloring

Author: Edouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant, 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), Warsaw University of Technology [Warsaw], Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), and ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
Subjects: [INFO]Computer Science [cs], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: 33 pages, 6 figures; International audience; We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time $f(d,k)n$ for $n$-vertex graphs given with a witness that the twin-width is at most $d$, called $d$-contraction sequence or $d$-sequence, and formulas of size $k$ [Bonnet et al., FOCS '20]. The inevitable price to pay for such a general result is that $f$ is a tower of exponentials of height roughly $k$. In this paper, we show that algorithms based on twin-width need not be impractical. We present $2^{O(k)}n$-time algorithms for $k$-Independent Set, $r$-Scattered Set, $k$-Clique, and $k$-Dominating Set when an $O(1)$-sequence is provided. We further show how to solve weighted $k$-Independent Set, Subgraph Isomorphism, and Induced Subgraph Isomorphism, in time $2^{O(k \log k)}n$. These algorithms are based on a dynamic programming scheme following the sequence of contractions forward. We then show a second algorithmic use of the contraction sequence, by starting at its end and rewinding it. As an example of this reverse scheme, we present a polynomial-time algorithm that properly colors the vertices of a graph with relatively few colors, establishing that bounded twin-width classes are $\chi$-bounded. This significantly extends the $\chi$-boundedness of bounded rank-width classes, and does so with a very concise proof. The third algorithmic use of twin-width builds on the second one. Playing the contraction sequence backward, we show that bounded twin-width graphs can be edge-partitioned into a linear number of bicliques, such that both sides of the bicliques are on consecutive vertices, in a fixed vertex ordering. Given that biclique edge-partition, we show how to solve the unweighted Single-Source Shortest Paths and hence All-Pairs Shortest Paths in sublinear time $O(n \log n)$ and time $O(n^2 \log n)$, respectively.
Published: 2021

20. Twin-width III: Max Independent Set, Min Dominating Set, and Coloring

Author: Bonnet, Édouard, Geniet, Colin, Kim, Eun Jung, Thomassé, Stéphan, Watrigant, Rémi, École normale supérieure de Lyon (ENS de Lyon), Warsaw University of Technology [Warsaw], Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), and ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
Subjects: FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Parameterized Algorithms, Computational Complexity (cs.CC), Exact Algorithms, Max Independent Set, Min Dominating Set, Theory of computation → Fixed parameter tractability, Computer Science - Computational Complexity, Theory of computation → Graph algorithms analysis, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Coloring, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), 05C85, [INFO]Computer Science [cs], Combinatorics (math.CO), F.2.2, Approximation Algorithms, Twin-width, Computer Science - Discrete Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: We recently introduced the notion of twin-width, a novel graph invariant, and showed that first-order model checking can be solved in time f(d,k)n for n-vertex graphs given with a witness that the twin-width is at most d, called d-contraction sequence or d-sequence, and formulas of size k [Bonnet et al., FOCS '20]. The inevitable price to pay for such a general result is that f is a tower of exponentials of height roughly k. In this paper, we show that algorithms based on twin-width need not be impractical. We present 2^{O(k)}n-time algorithms for k-Independent Set, r-Scattered Set, k-Clique, and k-Dominating Set when an O(1)-sequence of the graph is given in input. We further show how to solve the weighted version of k-Independent Set, Subgraph Isomorphism, and Induced Subgraph Isomorphism, in the slightly worse running time 2^{O(k log k)}n. Up to logarithmic factors in the exponent, all these running times are optimal, unless the Exponential Time Hypothesis fails. Like our FO model checking algorithm, these new algorithms are based on a dynamic programming scheme following the sequence of contractions forward. We then show a second algorithmic use of the contraction sequence, by starting at its end and rewinding it. As an example of such a reverse scheme, we present a polynomial-time algorithm that properly colors the vertices of a graph with relatively few colors, thereby establishing that bounded twin-width classes are χ-bounded. This significantly extends the χ-boundedness of bounded rank-width classes, and does so with a very concise proof. It readily yields a constant approximation for Max Independent Set on K_t-free graphs of bounded twin-width, and a 2^{O(OPT)}-approximation for Min Coloring on bounded twin-width graphs. We further observe that a constant approximation for Max Independent Set on bounded twin-width graphs (but arbitrarily large clique number) would actually imply a PTAS. The third algorithmic use of twin-width builds on the second one. Playing the contraction sequence backward, we show that bounded twin-width graphs can be edge-partitioned into a linear number of bicliques, such that both sides of the bicliques are on consecutive vertices, in a fixed vertex ordering. This property is trivially shared with graphs of bounded average degree. Given that biclique edge-partition, we show how to solve the unweighted Single-Source Shortest Paths and hence All-Pairs Shortest Paths in time O(n log n) and time O(n² log n), respectively. In sharp contrast, even Diameter does not admit a truly subquadratic algorithm on bounded twin-width graphs, unless the Strong Exponential Time Hypothesis fails. The fourth algorithmic use of twin-width builds on the so-called versatile tree of contractions [Bonnet et al., SODA '21], a branching and more robust witness of low twin-width. We present constant-approximation algorithms for Min Dominating Set and related problems, on bounded twin-width graphs, by showing that the integrality gap is constant. This is done by going down the versatile tree and stopping accordingly to a problem-dependent criterion. At the reached node, a greedy approach yields the desired approximation., LIPIcs, Vol. 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pages 35:1-35:20
Published: 2021

21. 4 vs 7 sparse undirected unweighted Diameter is SETH-hard at time n^4/3

Author: Édouard Bonnet, 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), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), ANR-21-CE48-0014,TWIN-WIDTH,Twin-width: théorie et applications(2021), and École normale supérieure de Lyon (ENS de Lyon)
Subjects: FOS: Computer and information sciences, inapproximability, SETH lower bounds, Computational Complexity (cs.CC), k-Orthogonal Vectors, Computer Science - Computational Complexity, Mathematics (miscellaneous), Theory of computation → Graph algorithms analysis, Diameter, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), 05C85, [INFO]Computer Science [cs], Combinatorics (math.CO), F.2.2, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: We show, assuming the Strong Exponential Time Hypothesis, that for every $\varepsilon > 0$, approximating undirected unweighted Diameter on $n$-vertex $n^{1+o(1)}$-edge graphs within ratio $7/4 - \varepsilon$ requires $m^{4/3 - o(1)}$ time. This is the first result that conditionally rules out a near-linear time $5/3$-approximation for undirected Diameter., 15 pages, 3 figures
Published: 2021

22. (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth

Author: Nicolas Trotignon, Ni Luh Dewi Sintiari, Stéphan Thomassé, Marcin Pilipczuk, 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), University of Warsaw (UW), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), É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), 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), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)
Subjects: FOS: Computer and information sciences, Even-hole-free graph, Discrete Mathematics (cs.DM), 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Treewidth, Combinatorics, 010201 computation theory & mathematics, Computer Science::Discrete Mathematics, Independent set, FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, Geometry and Topology, Combinatorics (math.CO), 0101 mathematics, Computer Science - Discrete Mathematics, Mathematics
Abstract: International audience; A {\em theta} is a graph made of three internally vertex-disjoint chordless paths $P_1 = a \dots b$, $P_2 = a \dots b$, $P_3 = a \dots b$ of length at least~2 and such that no edges exist between the paths except the three edges incident to $a$ and the three edges incident to $b$. A {\em pyramid} is a graph made of three chordless paths $P_1 = a \dots b_1$, $P_2 = a \dots b_2$, $P_3 = a \dots b_3$ of length at least~1, two of which have length at least 2, vertex-disjoint except at $a$, and such that $b_1b_2b_3$ is a triangle and no edges exist between the paths except those of the triangle and the three edges incident to~$a$. An \emph{even hole} is a chordless cycle of even length. For three non-negative integers $i\leq j\leq k$, let $S_{i,j,k}$ be the tree with a vertex $v$, from which start three paths with $i$, $j$, and $k$ edges respectively. We denote by $K_t$ the complete graph on $t$ vertices. We prove that for all non-negative integers $i, j, k$, the class of graphs that contain no theta, no $K_3$, and no $S_{i, j, k}$ as induced subgraphs have bounded treewidth. We prove that for all non-negative integers $i, j, k, t$, the class of graphs that contain no even hole, no pyramid, no $K_t$, and no $S_{i, j, k}$ as induced subgraphs have bounded treewidth. To bound the treewidth, we prove that every graph of large treewidth must contain a large clique or a minimal separator of large cardinality.
Published: 2021

23. On finding $k$ earliest arrival time journeys in public transit networks

Author: Coudert, David, Al Zoobi, Ali, Finkelstein, Arthur, 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), Instant System, This work has been supported by the French government, through the UCAjedi Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-15-IDEX-01, the ANR project MULTIMOD with the reference number ANR-17-CE22-0016, the ANR project Digraphs with the reference number ANR-19-CE48-0013, and by Région Sud PACA., Inria, ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), ANR-17-CE22-0016,MultiMod,Routage dans les grands réseaux de transports multi-modal(2017), 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: shortest path, routing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], timetables, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Journey planning
Abstract: Journey planning in (schedule-based) public transit networks has attracted interest from researchers in the last decade. In particular, many algorithms aiming at efficiently answering queries of journey planning have been proposed. However, most of the proposed methods give the user a single or a limited number of journeys in practice, which is undesirable in a transportation context. In this paper, we consider the problem of finding $k$ earliest arrival time journeys in public transit networks from a given origin to a given destination, i.e, an earliest arrival journey from the origin to the destination, a second earliest arrival journey, etc. until the $k^{th}$ earliest arrival journey. For this purpose, we propose an algorithm, denoted by Yen-Public Transit (Y-PT), that extends to public transit networks the algorithm proposed by Yen to find the top-$k$ shortest simple paths in a graph. Moreover, we propose a more refined algorithm, called Postponed Yen-Public Transit (PY-PT), enabling a considerable speed up in practice. Our experiments on several public transit networks show that, in practice, PY-PT is faster than Y-PT by an order of magnitude.
Published: 2021

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

25. Finding the k Shortest Simple Paths: Time and Space trade-offs

Author: Al Zoobi, Ali, Coudert, David, Nisse, Nicolas, 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), Région Sud PACA, Inria, I3S, Université Côte d'Azur, ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), ANR-17-CE22-0016,MultiMod,Routage dans les grands réseaux de transports multi-modal(2017), 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: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], space-time trade-off, graph algorithm, [INFO]Computer Science [cs], k shortest simple paths, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract: The k shortest simple path problem (kSSP) asks to compute a set of top-k shortest simple paths from a source to a sink in a digraph. Yen (1971) proposed an algorithm with the best known polynomial time complexity for this problem. Since then, the problem has been widely studied from an algorithm engineering perspective. The most noticeable proposals are the node-classification (NC) algorithm (Feng, 2014) and the sidetracks-based (SB) algorithm (Kurz, Mutzel, 2016). The latest offers the best running time at the price of a significant working memory. We first show how to speed up the SB algorithm using dynamic updates of shortest path trees resulting in a faster algorithm (SB*) with same working memory. We then propose the parsimonious SB (PSB) algorithm that significantly reduces the working memory of SB at the cost of a small increase of the running time. Furthermore, we propose the postponed nodeclassification (PNC) algorithm that combines the best of NC and SB. It offers a significant speed up compared to NC while using the same amount of working memory of NC. Our experimental results on complex networks show that all of the considered algorithms have low working memory, and that the PSB algorithm is the fastest. On road networks, the SB* algorithm is the fastest (on median) among the considered algorithms, but it suffers from a large working memory. The PNC algorithm has comparable running time to SB* on road networks while using the same working memory as NC.
Published: 2021

26. Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio

Author: Bonnet, Édouard, 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), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and École normale supérieure de Lyon (ENS de Lyon)
Subjects: FOS: Computer and information sciences, inapproximability, SETH lower bounds, Computational Complexity (cs.CC), k-Orthogonal Vectors, Computer Science - Computational Complexity, Theory of computation → Graph algorithms analysis, Diameter, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), 05C85, [INFO]Computer Science [cs], Combinatorics (math.CO), F.2.2
Abstract: We show, assuming the Strong Exponential Time Hypothesis, that for every $\varepsilon > 0$, approximating directed Diameter on $m$-arc graphs within ratio $7/4 - \varepsilon$ requires $m^{4/3 - o(1)}$ time. Our construction uses nonnegative edge weights but even holds for sparse digraphs, i.e., for which the number of vertices $n$ and the number of arcs $m$ satisfy $m = n \log^{O(1)} n$. This is the first result that conditionally rules out a near-linear time $5/3$-approximation for Diameter., 13 pages, 4 figures, expanded introduction and discussion on follow-up works
Published: 2021

27. Twin-width II: small classes

Author: Edouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant, 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), Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), É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), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Discrete Mathematics (cs.DM), 010102 general mathematics, G.2.2, 0102 computer and information sciences, 16. Peace & justice, 01 natural sciences, Logic in Computer Science (cs.LO), 010201 computation theory & mathematics, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], Combinatorics (math.CO), 68R10, 05C30, 05C48, 0101 mathematics, Computer Science - Discrete Mathematics
Abstract: The twin-width of a graph $G$ is the minimum integer $d$ such that $G$ has a $d$-contraction sequence, that is, a sequence of $|V(G)|-1$ iterated vertex identifications for which the overall maximum number of red edges incident to a single vertex is at most $d$, where a red edge appears between two sets of identified vertices if they are not homogeneous in $G$. We show that if a graph admits a $d$-contraction sequence, then it also has a linear-arity tree of $f(d)$-contractions, for some function $f$. First this permits to show that every bounded twin-width class is small, i.e., has at most $n!c^n$ graphs labeled by $[n]$, for some constant $c$. This unifies and extends the same result for bounded treewidth graphs [Beineke and Pippert, JCT '69], proper subclasses of permutations graphs [Marcus and Tardos, JCTA '04], and proper minor-free classes [Norine et al., JCTB '06]. The second consequence is an $O(\log n)$-adjacency labeling scheme for bounded twin-width graphs, confirming several cases of the implicit graph conjecture. We then explore the "small conjecture" that, conversely, every small hereditary class has bounded twin-width. Inspired by sorting networks of logarithmic depth, we show that $\log_{\Theta(\log \log d)}n$-subdivisions of $K_n$ (a small class when $d$ is constant) have twin-width at most $d$. We obtain a rather sharp converse with a surprisingly direct proof: the $\log_{d+1}n$-subdivision of $K_n$ has twin-width at least $d$. Secondly graphs with bounded stack or queue number (also small classes) have bounded twin-width. Thirdly we show that cubic expanders obtained by iterated random 2-lifts from $K_4$~[Bilu and Linial, Combinatorica '06] have bounded twin-width, too. We suggest a promising connection between the small conjecture and group theory. Finally we define a robust notion of sparse twin-width and discuss how it compares with other sparse classes., Comment: 37 pages, 9 figures
Published: 2021

28. EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs

Author: Paweł Rzążewski, Panos Giannopoulos, Marthe Bonamy, Stéphan Thomassé, Nicolas Bousquet, Édouard Bonnet, Pierre Charbit, Florian Sikora, Eun Jung Kim, Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), City University of London, Warsaw University of Technology [Warsaw], École normale supérieure de Lyon (ENS de Lyon), and ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
Subjects: Computational Geometry (cs.CG), FOS: Computer and information sciences, Unit sphere, QA75, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Induced subgraph, 0102 computer and information sciences, Computational Complexity (cs.CC), Clique (graph theory), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Artificial Intelligence, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Ball (mathematics), 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, Exponential time hypothesis, 010102 general mathematics, Intersection graph, Unit disk, Computer Science - Computational Complexity, Disjoint union (topology), 010201 computation theory & mathematics, Hardware and Architecture, Control and Systems Engineering, Computer Science - Computational Geometry, Algorithm, Software, Information Systems
Abstract: A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Clique} on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics '90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show that the disjoint union of two odd cycles is never the complement of a disk graph nor of a unit (3-dimensional) ball graph. From that fact and existing results, we derive a simple QPTAS and a subexponential algorithm running in time $2^{\tilde{O}(n^{2/3})}$ for \textsc{Maximum Clique} on disk and unit ball graphs. We then obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. This, in combination with our structural results, yields a randomized EPTAS for \textsc{Max Clique} on disk and unit ball graphs. \textsc{Max Clique} on unit ball graphs is equivalent to finding, given a collection of points in $\mathbb R^3$, a maximum subset of points with diameter at most some fixed value. In stark contrast, \textsc{Maximum Clique} on ball graphs and unit $4$-dimensional ball graphs, as well as intersection graphs of filled ellipses (even close to unit disks) or filled triangles is unlikely to have such algorithms. Indeed, we show that, for all those problems, there is a constant ratio of approximation which cannot be attained even in time $2^{n^{1-\varepsilon}}$, unless the Exponential Time Hypothesis fails., arXiv admin note: substantial text overlap with arXiv:1712.05010, arXiv:1803.01822
Published: 2021

29. Coloring graphs with no induced subdivision of $K_4^+$

Author: Esperet, Louis, Trotignon, Nicolas, Optimisation Combinatoire (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), 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-19-CE48-0013,DIGRAPHS,Digraphes(2019), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS), 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 - 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: Mathematics::Combinatorics, Computer Science::Discrete Mathematics, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: Let $K_4^+$ be the 5-vertex graph obtained from $K_4$, the complete graph on four vertices, by subdividing one edge precisely once (i.e. by replacing one edge by a path on three vertices). We prove that if the chromatic number of some graph $G$ is much larger than its clique number, then $G$ contains a subdivision of $K_4^+$ as an induced subgraph., 4 pages - v2 corrected typos
Published: 2021

30. On Tutte polynomial expansion formulas in perspectives of matroids and oriented matroids

Author: Gioan, Emeric, 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), ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017), and ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
Subjects: Mathematics::Combinatorics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Combinatorics (math.CO), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Theoretical Computer Science
Abstract: We introduce the active partition of the ground set of an oriented matroid perspective (or quotient, or strong map) on a linearly ordered ground set. The reorientations obtained by arbitrarily reorienting parts of the active partition share the same active partition. This yields an equivalence relation for the set of reorientations of an oriented matroid perspective, whose classes are enumerated by coefficients of the Tutte polynomial, and a remarkable partition of the set of reorientations into boolean lattices, from which we get a short direct proof of a 4-variable expansion formula for the Tutte polynomial in terms of orientation activities. This formula was given in the last unpublished preprint by Michel Las Vergnas; the above equivalence relation and notion of active partition generalize a former construction in oriented matroids by Michel Las Vergnas and the author; and the possibility of such a proof technique in perspectives was announced in the aforementioned preprint. We also briefly highlight how the 5-variable expansion of the Tutte polynomial in terms of subset activities in matroid perspectives comes in a similar way from the known partition of the power set of the ground set into boolean lattices related to subset activities (and we complete the proof with a property which was missing in the literature). In particular, the paper applies to matroids and oriented matroids on a linearly ordered ground set., 17 pages
Published: 2021

31. On the complexity of finding $k$ shortest dissimilar paths in a graph

Author: Al Zoobi, Ali, Coudert, David, Nisse, Nicolas, 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), This work was supported by the UCA JEDI Investments in the Future project managed by the National Research Agency (ANR-15-IDEX-01), the project MULTIMOD (ANR-17-CE22-0016), the project Digraphs (ANR-19-CE48-0013), the Région Sud PACA., Inria, CNRS, I3S, Université Côte d’Azur, ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), ANR-17-CE22-0016,MultiMod,Routage dans les grands réseaux de transports multi-modal(2017), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), COMUE Université Côte d'Azur (2015 - 2019) (COMUE 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), UCA, Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
Abstract: The similarity between two paths can be measured according to the proportion of arcs they share. We study the complexity of several variants of the problem of computing "dissimilar" paths (whose measure of similarity does not exceed a certain threshold) between two given vertices of a weighted directed graph. For four of the most studied measures in the literature, we give a unified and simple proof of the fact that finding $k$ shortest dissimilar paths is NP-complete. We then consider the problem of finding an alternative to one or more given paths. We show that finding a path that is dissimilar to another given path can be done in polynomial time for one of the four considered measures while it is NP-complete for the three remaining measures. In addition, we show that if $k$ = 2 paths are given, finding a new path that is dissimilar to the given ones is NP-complete even on DAGs for the four considered measures. Moreover, for the four considered measures, we show that if a path $P$ is given, finding a shortest path among those that are dissimilar to P is NP-complete in DAGs.
Published: 2021

32. (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels

Author: Nicolas Trotignon, Pegah Pournajafi, 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-19-CE48-0013,DIGRAPHS,Digraphes(2019), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), É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), 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), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)
Subjects: Sequence, Plane (geometry), 010102 general mathematics, Induced subgraph, Boundary (topology), 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Intersection graph, 01 natural sciences, Combinatorics, Line segment, Intersection, 010201 computation theory & mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology, Rectangle, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics
Abstract: The Burling sequence is a sequence of triangle-free graphs of increasing chromatic number. Each of them is isomorphic to the intersection graph of a set of axis-parallel boxes in $R^3$. These graphs were also proved to have other geometrical representations: intersection graphs of line segments in the plane, and intersection graphs of frames, where a frame is the boundary of an axis-aligned rectangle in the plane. We call Burling graph every graph that is an induced subgraph of some graph in the Burling sequence. We give five new equivalent ways to define Burling graphs. Three of them are geometrical, one is of a more graph-theoretical flavour and one is more axiomatic.
Published: 2021

33. On the dichromatic number of surfaces

Author: Aboulker, Pierre, Havet, Frédéric, Knauer, Kolja, Rambaud, Clément, Département d'informatique de l'École normale supérieure (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), Aix Marseille Université (AMU), Inria, CNRS, I3S, Université Côte D'Azur, ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), Département d'informatique - ENS Paris (DI-ENS), É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), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: 25 pages, 5 figures, improved asymptotic bounds; In this paper, we give bounds on the dichromatic number $\vec{\chi}(\Sigma)$ of a surface $\Sigma$, which is the maximum dichromatic number of an oriented graph embeddable on $\Sigma$. We determine the asymptotic behaviour of $\vec{\chi}(\Sigma)$ by showing that there exist constants $a_1$ and $a_2$ such that, $ a_1\frac{\sqrt{-c}}{\log(-c)} \leq \vec{\chi}(\Sigma) \leq a_2 \frac{\sqrt{-c}}{\log(-c)} $ for every surface $\Sigma$ with Euler characteristic $c\leq -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$. We also consider the complexity of deciding whether a given digraph or oriented graph embedabble in a fixed surface is $k$-dicolourable. In particular, we show that for any surface, deciding whether a digraph embeddable on this surface is $2$-dicolourable is NP-complete, and that deciding whether a planar oriented graph is $2$-dicolourable is NP-complete unless all planar oriented graphs are $2$-dicolourable (which was conjectured by Neumann-Lara).
Published: 2021

34. The (theta, wheel)-free graphs Part IV: Induced paths and cycles

Author: Nicolas Trotignon, Kristina Vušković, Marko Radovanović, 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-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), 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 - 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: 010102 general mathematics, Induced subgraph, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Theoretical Computer Science, Combinatorics, Computational Theory and Mathematics, 010201 computation theory & mathematics, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Combinatorics (math.CO), 0101 mathematics, Mathematics, Decomposition theorem
Abstract: International audience; A hole in a graph is a chordless cycle of length at least 4. A theta is a graph formed by three internally vertex-disjoint paths of length at least 2 between the same pair of distinct vertices. A wheel is a graph formed by a hole and a node that has at least 3 neighbors in the hole. In this series of papers we study the class of graphs that do not contain as an induced subgraph a theta nor a wheel. In Part II of the series we prove a decomposition theorem for this class, that uses clique cutsets and 2-joins. In this paper we use this decomposition theorem to solve several problems related to finding induced paths and cycles in our class.
Published: 2021

35. Compromis espace-temps pour le problème de k plus courts chemins simples

Author: Al Zoobi, Ali, Coudert, David, Nisse, Nicolas, 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), Région Sud PACA, ANR-17-CE22-0016,MultiMod,Routage dans les grands réseaux de transports multi-modal(2017), ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], k plus courts chemins simples, compromis complexité espace-temps, algorithmes de graphes
Abstract: International audience; Le problème de trouver k plus courts chemins simples (sans répétition de sommets) entre deux sommets dans un graphe a été largement étudié du point de vue de l'ingénierie algorithmique. Kurz et Mutzel (2016) ont proposé l'algorithme SB (pour Sidetrack Based) basé sur le concept de déviations, qui est actuellement la méthode la plus rapide en pratique. Dans ce travail, nous proposons deux améliorations de cet algorithme. Nous montrons tout d'abord comment accélérer l'algorithme SB en utilisant des mises à jour dynamiques d'arbres de plus courts chemins. Nos simulations réalisées sur certains réseaux routiers avec environ un demi-million de sommets et un million d'arcs montrent que notre amélioration donnent une accélération moyenne d'un facteur 1,5 à 2 avec une consommation de mémoire similaire à celle de l'algorithme SB. Notre principale contribution est un second algorithme réalisant un compromis entre temps d'exécution et mémoire utilisée. Notre algorithme permet de réduire significativement la mémoire de travail (d'un facteur 1, 5 à 2) au prix d'une légère augmentation du temps d'exécution.
Published: 2020

36. On the complexity of colouring antiprismatic graphs

Author: Nicolas Trotignon, Cléophée Robin, Myriam Preissmann, Optimisation Combinatoire (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), 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-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), 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), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)
Subjects: FOS: Computer and information sciences, Vertex (graph theory), Discrete Mathematics (cs.DM), General Computer Science, Applied Mathematics, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Computer Science Applications, Combinatorics, Computer Science::Robotics, 010201 computation theory & mathematics, Theory of computation, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Mathematics - Combinatorics, 020201 artificial intelligence & image processing, Combinatorics (math.CO), Time complexity, Clique cover, Mathematics, Computer Science - Discrete Mathematics
Abstract: International audience; A graph G is prismatic if for every triangle T of G, every vertex of G not in T has a unique neighbour in T. The complement of a prismatic graph is called \emph{antiprismatic}. The complexity of colouring antiprismatic graphs is still unknown. Equivalently, the complexity of the clique cover problem in prismatic graphs is not known. Chudnovsky and Seymour gave a full structural description of prismatic graphs. They showed that the class can be divided into two subclasses: the orientable prismatic graphs, and the non-orientable prismatic graphs. We give a polynomial time algorithm that solves the clique cover problem in every non-orientable prismatic graph. It relies on the the structural description and on later work of Javadi and Hajebi. We give a polynomial time algorithm which solves the vertex-disjoint triangles problem for every prismatic graph. It does not rely on the structural description.
Published: 2020

37. Inversion number of an oriented graph and related parameters

Author: Bang-Jensen, Jørgen, Ferreira da Silva, Jonas, Havet, Frédéric, Department of Mathematics and Computer Science [Odense] (IMADA), University of Southern Denmark (SDU), 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), This research was supported by the Independent Research Fund Denmark under grant number DFF 7014-00037B, and by the french Agence Nationale de la Recherche under contract Digraphs ANR-19-CE48-0013-01. This work was done while Joergen Bang-Jensen was visiting team Coati, I3S and INRIA Sophia Antipolis. Hospitality and financial support is gratefully acknowledged. Ce travail a bénéficié d’une aide du gouvernement français, gérée par l’Agence Nationale de la Recherche au titre du projet Investissements d’Avenir UCAJEDI portant la référence no ANR-15-IDEX-01. This work was done while Jonas Costa Ferreira da Silva was spending his second year of PhD as 'sandwich' in team Coati, I3S and INRIA Sophia Antipolis., ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), 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: Feedback arc set, Inversion, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Intercyclic digraph, Feedback vertex set, Tournament, Oriented graph
Abstract: International audience; 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 inv(D), is the minimum number of inversions needed to make D acyclic. Denoting by τ (D), τ (D), and ν(D) the cycle transversal number, the cycle arc-transversal number and the cycle packing number of D respectively, one shows that inv(D) ≤ τ (D), inv(D) ≤ 2τ (D) and there exists a function g such that inv(D) ≤ g(ν(D)). We conjecture that for any two oriented graphs L and R, inv(L → R) = inv(L) + inv(R) where L → R is the dijoin of L and R. This would imply that the first two inequalities are tight. We prove this conjecture when inv(L) ≤ 1 and inv(R) ≤ 2 and when inv(L) = inv(R) = 2 and L and R are strongly connected. We also show that the function g of the third inequality satisfies g(1) ≤ 4. We then consider the complexity of deciding whether inv(D) ≤ 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. [6] which states that deciding whether inv(T) ≤ k for a given tournament T is polynomial-time solvable.
Published: 2020

38. On the tree-width of even-hole-free graphs

Author: Pierre Aboulker, Nicolas Trotignon, Eun Jung Kim, Ni Luh Dewi Sintiari, Isolde Adler, 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-19-CE48-0013,DIGRAPHS,Digraphes(2019), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), 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), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)
Subjects: FOS: Computer and information sciences, Property testing, Class (set theory), Discrete Mathematics (cs.DM), Induced subgraph, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, law.invention, Combinatorics, law, Line graph, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, Conjecture, Degree (graph theory), 010102 general mathematics, 16. Peace & justice, Treewidth, 010201 computation theory & mathematics, Bounded function, Combinatorics (math.CO), Computer Science - Discrete Mathematics
Abstract: The class of all even-hole-free graphs has unbounded tree-width, as it contains all complete graphs. Recently, a class of (even-hole, K 4 )-free graphs was constructed, that still has unbounded tree-width (Sintiari and Trotignon, 2019). The class has unbounded degree and contains arbitrarily large clique-minors. We ask whether this is necessary. We prove that for every graph G , if G excludes a fixed graph H as a minor, then G either has small tree-width, or G contains a large wall or the line graph of a large wall as induced subgraph. This can be seen as a strengthening of Robertson and Seymour’s excluded grid theorem for the case of minor-free graphs. Our theorem implies that every class of even-hole-free graphs excluding a fixed graph as a minor has bounded tree-width. In fact, our theorem applies to a more general class: (theta, prism)-free graphs. This implies the known result that planar even hole-free graphs have bounded tree-width (Silva et al., 2010). We conjecture that even-hole-free graphs of bounded degree have bounded tree-width. If true, this would mean that even-hole-freeness is testable in the bounded-degree graph model of property testing. We prove the conjecture for subcubic graphs and we give a bound on the tree-width of the class of (even hole, pyramid)-free graphs of degree at most 4.
Published: 2020

39. Space and Time Trade-Off for the k Shortest Simple Paths Problem

Author: Al Zoobi, Ali, Coudert, David, Nisse, Nicolas, 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), Région Sud PACA, ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), ANR-17-CE22-0016,MultiMod,Routage dans les grands réseaux de transports multi-modal(2017), 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), COMUE Université Côte d'Azur (2015-2019) (COMUE 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 Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France
Subjects: [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], space-time trade-off, graph algorithm, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], k shortest simple paths, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: The k shortest simple path problem (kSSP) asks to compute a set of top-k shortest simple paths from a vertex s to a vertex t in a digraph. Yen (1971) proposed the first algorithm with the best known theoretical complexity of O(kn(m+n log n)) for a digraph with n vertices and m arcs. Since then, the problem has been widely studied from an algorithm engineering perspective, and impressive improvements have been achieved. In particular, Kurz and Mutzel (2016) proposed a sidetracks-based (SB) algorithm which is currently the fastest solution. In this work, we propose two improvements of this algorithm. We first show how to speed up the SB algorithm using dynamic updates of shortest path trees. We did experiments on some road networks of the 9th DIMAC'S challenge with up to about half a million nodes and one million arcs. Our computational results show an average speed up by a factor of 1.5 to 2 with a similar working memory consumption as SB. We then propose a second algorithm enabling to significantly reduce the working memory at the cost of an increase of the running time (up to two times slower). Our experiments on the same data set show, on average, a reduction by a factor of 1.5 to 2 of the working memory., LIPIcs, Vol. 160, 18th International Symposium on Experimental Algorithms (SEA 2020), pages 18:1-18:13
Published: 2020

40. Arc-disjoint in- and out-branchings in digraphs of independence number at most 2

Author: Jørgen Bang‐Jensen, Stéphane Bessy, Frédéric Havet, Anders Yeo, 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), 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), and ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
Subjects: Mathematics::Combinatorics, in-branching, arc-disjoint branchings, out-branching, Computer Science::Discrete Mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, digraphs of independence number 2, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Arc-disjoint branchings, Combinatorics (math.CO), arc-connectivity, Geometry and Topology, 05c20
Abstract: International audience; We prove that every digraph of independence number at most 2 and arc-connectivity at least 2 has an out-branching $B+$ and an in-branching $B−$ which are arc-disjoint (we call such branchings a good pair). This is best possible in terms of the arc-connectivity as there are infinitely many strong digraphs with independence number 2 and arbitrarily high minimum in- and out-degrees that have no good pair. The result settles a conjecture by Thomassen for digraphs of independence number 2. We prove that every digraph on at most 6 vertices and arc-connectivity at least 2 has a good pair and give an example of a 2-arc-strong digraph $D$ on 10 vertices with independence number 4 that has no good pair. We also show that there are infinitely many digraphs with independence number 7 and arc-connectivity 2 that have no good pair. Finally we pose a number of open problems.
Published: 2020

41. Treelength of Series-parallel graphs

Author: Dissaux, Thomas, Ducoffe, Guillaume, Nisse, Nicolas, Nivelle, Simon, 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 Bucharest (UniBuc), National Institute for Research and Development in Informatics and Research Institute of the University of Bucharest, Institut national supérieur du professorat et de l'éducation - Académie de Paris (INSPÉ Paris), Sorbonne Université (SU), Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France, STIC-AmSud project GALOP (Graphs ALgorithms for Optimization Problems), PHC Xu Guangqi project DESPROGES (DEcompositionS arborescentes et PROblèmes de GraphES), ANR-17-CE22-0016,MultiMod,Routage dans les grands réseaux de transports multi-modal(2017), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), Université Politehnica [Bucarest, Roumanie], Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Subjects: General Earth and Planetary Sciences, [INFO]Computer Science [cs], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], General Environmental Science
Abstract: International audience; The length of a tree-decompositionof a graph is the maximum distance between two vertices of a same bag of the decomposition. The treelength of a graph is the minimum length among its tree-decomposition. Treelength of graphs has been studied for its algorithmic applications in classical metric problems such as Traveling Salesman Problem or metric dimension of graphs and also, in compact routing in the context of distributed computing. Deciding whether the treelength of a general graph is at most 2 is NP-complete (graphs of treelength one are precisely the chordal graphs), and it is known that the treelength of agraph cannot be approximated up to a factor less than3/2 (the best known approximation algorithm for treelength has an approximation ratio of 3). However, nothing is known on the computational complexity of treelength in planar graphs, except that the treelength of any outerplanar graph is equal to the third of the maximum size of its isometric cycles. This work initiates the study of treelength in planar graphs by considering its next natural subclass, namely the one of series-parallel graphs. We first fully describe the treelength of melon graphs (set of pairwise internally disjointpaths linking two vertices), showing that, even in such a restricted graph class, the expression of the treelength is not trivial. Then, we show that treelength can be approximated up toa factor 3/2 in series-parallel graphs. Our main result is a polynomial-time algorithm for deciding whether a series-parallel graph has treelength at most 2. Our latter result relies on a characterization of series-parallel graphs with treelength 2 in terms of an infinite family of forbidden isometric subgraphs.
Published: 2020

42. Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth

Author: Bergougnoux, Benjamin, Bonnet, Édouard, Brettell, Nick, Kwon, O-joung, 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), Victoria University of Wellington, Incheon National University, ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), École normale supérieure - Lyon (ENS Lyon), Bonnet, Édouard, and Digraphes - - DIGRAPHS2019 - ANR-19-CE48-0013 - AAPG2019 - VALID
Subjects: FOS: Computer and information sciences, Parameterized Algorithms, Vertex Deletion Problems, 68Q27, 05C85, Multiway Cut, Treewidth, Graph Modification, [INFO] Computer Science [cs], Computational Complexity (cs.CC), Theory of computation → Fixed parameter tractability, Computer Science - Computational Complexity, Theory of computation → Graph algorithms analysis, Computer Science - Data Structures and Algorithms, [INFO]Computer Science [cs], Data Structures and Algorithms (cs.DS), F.2.2, Subset Feedback Vertex Set, Computer Science::Data Structures and Algorithms
Abstract: The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time $2^{O(tw)}n^{O(1)}$, for Feedback Vertex Set and connected versions of the classical graph problems (such as Vertex Cover and Dominating Set). We show that Subset Feedback Vertex Set, Subset Odd Cycle Transversal, Restricted Edge-Subset Feedback Edge Set, Node Multiway Cut, and Multiway Cut are unlikely to have such running times. More precisely, we match algorithms running in time $2^{O(tw \log tw)}n^{O(1)}$ with tight lower bounds under the Exponential-Time Hypothesis (ETH), ruling out $2^{o(tw \log tw)}n^{O(1)}$, where $n$ is the number of vertices and $tw$ is the treewidth of the input graph. Our algorithms extend to the weighted case, while our lower bounds also hold for the larger parameter pathwidth and do not require weights. We also show that, in contrast to Odd Cycle Transversal, there is no $2^{o(tw \log tw)}n^{O(1)}$-time algorithm for Even Cycle Transversal under the ETH., 25 pages, 5 figures
Published: 2020
Full Text: View/download PDF

43. Out‐colourings of digraphs

Author: Noga Alon, Stéphane Bessy, Jørgen Bang-Jensen, Tel Aviv University [Tel Aviv], 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), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), and ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
Subjects: FOS: Computer and information sciences, Paley tournament, Discrete Mathematics (cs.DM), Generalization, semicomplete digraphs, 0102 computer and information sciences, Astrophysics::Cosmology and Extragalactic Astrophysics, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, out-colourings, degree constrained partitioning of digraphs, Integer, Computer Science::Discrete Mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Discrete Mathematics and Combinatorics, Partition (number theory), probabilistic method, Tournament, 0101 mathematics, Astrophysics::Galaxy Astrophysics, tournaments, Mathematics, Mathematics::Combinatorics, 010102 general mathematics, Digraph, polynomial algorithm, 16. Peace & justice, Vertex (geometry), 010201 computation theory & mathematics, Bipartite graph, Geometry and Topology, Constant (mathematics), Computer Science - Discrete Mathematics
Abstract: We study vertex colourings of digraphs so that no out-neighbourhood is monochromatic and call such a colouring an out-colouring. The problem of deciding whether a given digraph has an out-colouring with only two colours (called a 2-out-colouring) is (Formula presented.) -complete. We show that for every choice of positive integers (Formula presented.) there exists a (Formula presented.) -strong bipartite tournament, which needs at least (Formula presented.) colours in every out-colouring. Our main results are on tournaments and semicomplete digraphs. We prove that, except for the Paley tournament (Formula presented.), every strong semicomplete digraph of minimum out-degree at least three has a 2-out-colouring. Furthermore, we show that every semicomplete digraph on at least seven vertices has a 2-out-colouring if and only if it has a balanced such colouring, that is, the difference between the number of vertices that receive colour 1 and colour 2 is at most one. In the second half of the paper, we consider the generalization of 2-out-colourings to vertex partitions (Formula presented.) of a digraph (Formula presented.) so that each of the three digraphs induced by respectively, the vertices of (Formula presented.), the vertices of (Formula presented.) and all arcs between (Formula presented.) and (Formula presented.), have minimum out-degree (Formula presented.) for a prescribed integer (Formula presented.). Using probabilistic arguments, we prove that there exists an absolute positive constant (Formula presented.) so that every semicomplete digraph of minimum out-degree at least (Formula presented.) has such a partition. This is tight up to the value of (Formula presented.).
Published: 2020

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

45. Graphs with polynomially many minimal separators

Author: Maria Chudnovsky, Nicolas Trotignon, Kristina Vušković, Stéphan Thomassé, Tara Abrishami, Cemil Dibek, 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-19-CE48-0013,DIGRAPHS,Digraphes(2019), and ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010)
Subjects: Class (set theory), 021103 operations research, 0211 other engineering and technologies, Induced subgraph, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, Combinatorics, Prism (geometry), Computational Theory and Mathematics, 010201 computation theory & mathematics, Independent set, Pyramid, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, [INFO]Computer Science [cs], Combinatorics (math.CO), Time complexity, Mathematics
Abstract: We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the sense that there are graphs with exponentially many minimal separators if only three of the four induced subgraphs are excluded. As a consequence, there is a polynomial time algorithm to solve the maximum weight independent set problem for the class of (theta, pyramid, prism, turtle)-free graphs. Since every prism, theta, and turtle contains an even hole, this also implies a polynomial time algorithm to solve the maximum weight independent set problem for the class of (pyramid, even hole)-free graphs.
Published: 2020
Full Text: View/download PDF

46. Maximum Clique in Disk-Like Intersection Graphs

Author: Bonnet, Édouard, Miltzow, T., Grelier, Nicolas, Saxena, Nitin, Simon, Sunil, Sub Geometric Computing, Geometric Computing, Bonnet, Édouard, Digraphes - - DIGRAPHS2019 - ANR-19-CE48-0013 - AAPG2019 - VALID, 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), Department of Computer Science [ETH Zürich] (D-INFK), Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich] (ETH Zürich), Utrecht University [Utrecht], ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), École normale supérieure de Lyon (ENS de Lyon), Nitin, Saxena, and Sunil, Simon
Subjects: Computational Geometry (cs.CG), FOS: Computer and information sciences, Maximum Clique, Mathematics of computing → Graph algorithms, Intersection Graphs, Theory of computation → Computational geometry, Computational Complexity (cs.CC), Disk Graphs, [INFO] Computer Science [cs], 16. Peace & justice, APX-hardness, Computer Science - Computational Complexity, Disk graphs, Intersection graphs, Maximum clique, Algorithms, NP-hardness, Computer Science - Data Structures and Algorithms, 68Q25, 68U05, Computer Science - Computational Geometry, [INFO]Computer Science [cs], Data Structures and Algorithms (cs.DS), F.2.2, MathematicsofComputing_DISCRETEMATHEMATICS, NPhardness
Abstract: We study the complexity of Maximum Clique in intersection graphs of convex objects in the plane. On the algorithmic side, we extend the polynomial-time algorithm for unit disks [Clark '90, Raghavan and Spinrad '03] to translates of any fixed convex set. We also generalize the efficient polynomial-time approximation scheme (EPTAS) and subexponential algorithm for disks [Bonnet et al. '18, Bonamy et al. '18] to homothets of a fixed centrally symmetric convex set. The main open question on that topic is the complexity of Maximum Clique in disk graphs. It is not known whether this problem is NP-hard. We observe that, so far, all the hardness proofs for Maximum Clique in intersection graph classes $\mathcal I$ follow the same road. They show that, for every graph $G$ of a large-enough class $\mathcal C$, the complement of an even subdivision of $G$ belongs to the intersection class $\mathcal I$. Then they conclude invoking the hardness of Maximum Independent Set on the class $\mathcal C$, and the fact that the even subdivision preserves that hardness. However there is a strong evidence that this approach cannot work for disk graphs [Bonnet et al. '18]. We suggest a new approach, based on a problem that we dub Max Interval Permutation Avoidance, which we prove unlikely to have a subexponential-time approximation scheme. We transfer that hardness to Maximum Clique in intersection graphs of objects which can be either half-planes (or unit disks) or axis-parallel rectangles. That problem is not amenable to the previous approach. We hope that a scaled down (merely NP-hard) variant of Max Interval Permutation Avoidance could help making progress on the disk case, for instance by showing the NP-hardness for (convex) pseudo-disks., Comment: 23 pages, 5 figures
Published: 2020

47. On finding the best and worst orientations for the metric dimension

Author: Araujo, Julio, Bensmail, Julien, Campos, Victor, Havet, Frédéric, Maia de Oliviera, Ana Karolinna, Nisse, Nicolas, Silva, Ana, Universidade Federal do Ceará = Federal University of Ceará (UFC), 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), Inria, ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), 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: Resolving sets, Digraphs, Undirected graphs, Metric dimension, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract: The (directed) metric dimension of a digraph D, denoted by MD(D), is the size of a smallest subset S of vertices such that every two vertices of D are distinguished via their distances from the vertices in S. In this paper, we investigate the graph parameters BOMD(G) and WOMD(G) which are respectively the smallest and largest metric dimension over all orientations of G. We show that those parameters are related to several classical notions of graph theory and investigate the complexity of determining those parameters. We show that BOMD(G) = 1 if and only if G is hypotraceable (that is has a path spanning all vertices but one), and deduce that deciding whether BOMD(G) ≤ k is NP-complete for every positive integer k. We also show that WOMD(G) ≥ α(G) − 1, where α(G) is the stability number of G. We then deduce that for every fixed positive integer k, we can decide in polynomial time whether WOMD(G) ≤ k. The most significant results deal with oriented forests. We provide a linear-time algorithm to compute the metric dimension of an oriented forest and a linear-time algorithm that, given a forest F , computes an orientation D − with smallest metric dimension (i.e. such that MD(D −) = BOMD(F)) and an orientation D + with largest metric dimension (i.e. such that MD(D +) = WOMD(F)).
Published: 2020

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

49. Decomposing degenerate graphs into locally irregular subgraphs

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

50. Gossiping with interference in radio ring networks

Author: Bermond, Jean-Claude, Kodate, Takako, Yu, Joseph, 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), Tokyo Woman's Christian University (TWCU), Department of Mathematics and Statistics [Fraser Valley], University College of the Fraser Valley (UFV), 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), Unversity of the Fraser Valley, B.C. Canada, ANR-13-BS02-0007,Stint,Structures Interdites(2013), ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), and ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
Subjects: [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Rings, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Gossiping, Interference, Radio Networks, ring, [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI]
Abstract: International audience; In this paper, we study the problem of gossiping with interference constraint in radio ring networks. Gossiping (or total exchange information) is a protocol where each node in the network has a message and wants to distribute its own message to every other node in the network. The gossiping problem consists in finding the minimum running time (makespan) of a gossiping protocol and efficient algorithms that attain this makespan.Transmission model A radio network consists of communication devices equipped with an half duplex interface. The network is assumed to be synchronous and the time is slotted into rounds. The half-duplex hypothesis implies that a node can transmit or receive at most one message during a round. The network is modeled as a digraph, where the vertices represent the nodes and the arcs represent the possible communications. The messages are transmitted through the communication over the arcs and we will denote a call such a transmission.Interference model We use a binary asymmetric model of interference based on the distance in the communication digraph like the ones used in [1, 2, 5]. Let d(u,v) denote the distance, that is the length of a shortest directed path, from u to v in G and dI be a non negative integer. We assume that when a node u transmits, all nodes v such that d(u,v) ≤ dI are subject to the interference from u’s transmission. So two calls (u, v) and (u′, v′) do not interfere if d(u, v′) > dI and d(u′,v) > dI.This problem has been studied in [4] where approximation results are given (see also the survey [3]). Here we focus on the case where the transmisson network is a ring network Cn on n nodes with the interference distance dI = 1. We presented some partial results at JCDCG^G 2013, and we have now solved completely the gossiping problem by giving the minimum running time (makespan). We show lower bounds and then give gossiping algorithms which meet these lower bounds and so are optimal.
Published: 2019

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

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

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

53 results on '"ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources