Descriptor: "Pathwidth" / Publisher: hal ccsd - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Pathwidth"' showing total 168 results

Start Over Descriptor "Pathwidth" Publisher hal ccsd

168 results on '"Pathwidth"'

1. Sur la largeur des décompositions JSJ compliquées

Author: Huszár, Kristóf, Spreer, Jonathan, 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 National de la Recherche Scientifique (CNRS), The University of Sydney, Chambers, Erin W., Gudmundsson, Joachim, ANR-19-P3IA-0002,3IA@cote d'azur,3IA Côte d'Azur(2019), ANR-20-CE48-0007,AlgoKnot,Aspects algorithmiques et combinatoires de la théorie des nœuds(2020), ANR-18-CE40-0032,GrR,Reconfiguration de Graphes(2018), ANR-21-CE48-0014,TWIN-WIDTH,Twin-width: théorie et applications(2021), and ANR-10-LABX-0059,CARMIN,Centers of Hosting and International Mathematical Encounters(2010)
Subjects: Computational Geometry (cs.CG), FOS: Computer and information sciences, F.2.2, G.2.2, generalized Heegaard splittings, 57Q15, 57N10, 05C75, 57M15, Theory of computation → Problems, reductions and completeness, pathwidth, triangulations, Geometric Topology (math.GT), MSC: 57Q15, 57N10, 05C75, 57M15, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], Mathematics of computing → Geometric topology, computational 3-manifold topology, Theory of computation → Fixed parameter tractability, Mathematics - Geometric Topology, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory, ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems, fixed-parameter tractability, JSJ decompositions, [MATH.MATH-GT]Mathematics [math]/Geometric Topology [math.GT], FOS: Mathematics, treewidth, Computer Science - Computational Geometry
Abstract: Motivated by the algorithmic study of 3-dimensional manifolds, we explore the structural relationship between the JSJ decomposition of a given 3-manifold and its triangulations. Building on work of Bachman, Derby-Talbot and Sedgwick, we show that a "sufficiently complicated" JSJ decomposition of a 3-manifold enforces a "complicated structure" for all of its triangulations. More concretely, we show that, under certain conditions, the treewidth (resp. pathwidth) of the graph that captures the incidences between the pieces of the JSJ decomposition of an irreducible, closed, orientable 3-manifold M yields a linear lower bound on its treewidth tw (M) (resp. pathwidth pw(M)), defined as the smallest treewidth (resp. pathwidth) of the dual graph of any triangulation of M. We present several applications of this result. We give the first example of an infinite family of bounded-treewidth 3-manifolds with unbounded pathwidth. We construct Haken 3-manifolds with arbitrarily large treewidth - previously the existence of such 3-manifolds was only known in the non-Haken case. We also show that the problem of providing a constant-factor approximation for the treewidth (resp. pathwidth) of bounded-degree graphs efficiently reduces to computing a constant-factor approximation for the treewidth (resp. pathwidth) of 3-manifolds., LIPIcs, Vol. 258, 39th International Symposium on Computational Geometry (SoCG 2023), pages 42:1-42:18
Published: 2023

2. Parameterized complexity of a single machine scheduling problem

Author: Mallem, Maher and Sciencesconf.org, CCSD
Subjects: [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], pathwidth, single machine scheduling, parameterized complexity
Abstract: Many scheduling problems, even seemingly basic ones such as P2|chains|Cmax, have been proved (strongly) NP-hard over the years. This problem was even showed to remain weakly NP-hard with three chains. Upon reaching NP-hardness this quickly, it becomes difficult to establish anything deeper about these scheduling problems within the scope of classical com-plexity theory.To answer this, parameterized complexity theory gives additional tools for a refined analysis of such hard scheduling problems. Given a parameter k and denoting n the input size, a problem is called fixed−parameter tractable (FPT) parameterized by k if it can be solved in time O(poly(n)×f(k)) with f an arbitrary function. The idea is to identify k as the limiting property and give a polynomial time algorithm for all instances with a bounded value of k. When the studied problem is believed to not be FPT, the W-hierarchy is usually used to evaluate its difficulty relative to the considered parameter. We have FPT=W[0]⊆W[1]⊆W[2]⊆etc. and unless P=NP, all the inclusions are believed to be strict.While parameterized complexity theory has been successfully applied to a lot of computerscience areas, it has started to be studied extensively on scheduling only quite recently. The pathwidth - noted μ - which we define as the maximum number of overlapping job time windows at any given time, has recently received increasing interest. However to the best of our knowledge this parameter has had no hardness result relative to it proved yet. Such a result would help refining the frontier between which problems are FPT with this parameter and which ones are not.We consider the decision problem with a single machine, chains as precendence relations, release dates, deadlines, unit time processing times and exact delays between consecutive nodes in a chain. We show that this problem is W[1]-hard parameterized by μ. We reduce from INDEPENDENT SET which is a well-known W[1]-complete problem parameterized by the size k of the independent set. The ideas behind this reduction have potential to be reinvested in other parameterized scheduling problems involving delays.
Published: 2022

3. Weighted Total Acquisition

Author: Guillaume Bagan, Marc Heinrich, Fionn Mc Inerney, Valentin Gledel, Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Optimisation Combinatoire (G-SCOP_OC), 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), School of Computing [Leeds], University of Leeds, Algorithmique, Combinatoire et Recherche Opérationnelle (ACRO), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), ANR-14-CE25-0006,GAG,Jeux et graphes(2014), ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), and Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Unary operation, Degree (graph theory), Applied Mathematics, Treewidth, 010102 general mathematics, Parameterized complexity, 0102 computer and information sciences, Complexity, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Dynamic programming, 01 natural sciences, Planar graph, Vertex (geometry), Combinatorics, symbols.namesake, Pathwidth, 010201 computation theory & mathematics, Bounded function, symbols, Discrete Mathematics and Combinatorics, [INFO]Computer Science [cs], Total acquisition, 0101 mathematics, Mathematics
Abstract: International audience; In the Weighted Total Acquisition problem (WTA) on a weighted graph $G$ (only positive non-zero weights), a vertex $v$ can acquire the total weight of a neighbour $u$ if and only if the current weight of $v$ is at least that of $u$. The new weight of $u$ is then zero, and the new weight of $v$ is then the sum of the weights at $u$ and $v$ just before the acquisition. Over all possible acquisition sequences in $G$ with weight function $w$, the minimum number of vertices with a non-zero weight at the end is denoted by $a_t(G,w)$. Given a graph $G$, a weighting $w$, and an integer $k\geq 1$, the WTA problem asks whether $a_t(G,w)\leq k$. The Binary (Unary resp.) WTA problem corresponds to the WTA problem when the weights are encoded in binary (unary resp.).We prove that Unary WTA is polynomial-time solvable in graphs of bounded treewidth and degree. When only the treewidth is bounded, this algorithm is quasi-polynomial, i.e., it runs in time $W^{O(\log W)}$, where $W$ is the sum of the weights of the vertices. Moreover, we show that Unary WTA is FPT in trees when parameterized by the maximum degree. On the negative side, we show that WTA is NP-complete in trivially perfect graphs and split graphs, even when $k=1$ in the latter.We prove that the Binary WTA problem is NP-complete in trees of bounded degree, trees of bounded depth, and wheels, but that it is in XP for trees and wheels when parameterized by the solution size. Moreover, we show that Binary WTA is NP-complete in $K_{3,n}$, planar graphs of pathwidth 2, and unit interval graphs even when $k=1$, and in trivially perfect graphs when $k\geq 2$ (but polynomial-time solvable when $k=1$).
Published: 2021

4. A Fixed-Parameter Algorithm for Scheduling Unit Dependent Tasks on Parallel Machines with Time Windows

Author: Munier Kordon Alix, Architecture et Logiciels pour Systèmes Embarqués sur Puce (ALSOC), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), and Munier Kordon, Alix
Subjects: Binary search algorithm, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Applied Mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, Interval graph, makespan, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 021107 urban & regional planning, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Decision problem, 01 natural sciences, parallel identical machines, Scheduling (computing), Dynamic programming, Pathwidth, maximum lateness, 010201 computation theory & mathematics, Time windows, Discrete Mathematics and Combinatorics, Algorithm, Mathematics, parameterized complexity
Abstract: This paper proves that the existence of a feasible schedule for a set of dependent tasks of unit execution times with release dates and deadlines on a limited number of processors is a fixed-parameter tractable problem. The parameter considered is the pathwidth of the interval graph associated with the time windows of the tasks. A fixed-parameter algorithm based on a dynamic programming approach is developed and proved to solve this decision problem. Fixed-parameter algorithms for the two classical problems P | p r e c , p i = 1 , r i | C max and P | p r e c , p i = 1 , r i | L max are then derived using a binary search. They are, as far as we know, the first fixed-parameter algorithms for these scheduling problems.
Published: 2020

5. Grundy Distinguishes Treewidth from Pathwidth

Author: Belmonte, Rémy, Kim, Eun Jung, Lampis, Michael, Mitsou, Valia, Otachi, Yota, Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, Grundy Coloring, Clique-width, Treewidth, Mathematics of computing → Graph algorithms, General Mathematics, Computer Science - Data Structures and Algorithms, Theory of computation → Parameterized complexity and exact algorithms, Pathwidth, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs]
Abstract: Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to understand the "price of generality" of these widths: as we transition from more restrictive to more general notions, which are the problems that see their complexity status deteriorate from fixed-parameter tractable to intractable? This type of question is by now very well-studied, but, somewhat strikingly, the algorithmic frontier between the two (arguably) most central width notions, treewidth and pathwidth, is still not understood: currently, no natural graph problem is known to be W-hard for one but FPT for the other. Indeed, a surprising development of the last few years has been the observation that for many of the most paradigmatic problems, their complexities for the two parameters actually coincide exactly, despite the fact that treewidth is a much more general parameter. It would thus appear that the extra generality of treewidth over pathwidth often comes "for free". Our main contribution in this paper is to uncover the first natural example where this generality comes with a high price. We consider Grundy Coloring, a variation of coloring where one seeks to calculate the worst possible coloring that could be assigned to a graph by a greedy First-Fit algorithm. We show that this well-studied problem is FPT parameterized by pathwidth; however, it becomes significantly harder (W[1]-hard) when parameterized by treewidth. Furthermore, we show that Grundy Coloring makes a second complexity jump for more general widths, as it becomes para-NP-hard for clique-width. Hence, Grundy Coloring nicely captures the complexity trade-offs between the three most well-studied parameters. Completing the picture, we show that Grundy Coloring is FPT parameterized by modular-width., Comment: Conference version appeared in ESA 2020. This is the full version which has been accepted for publication at SIDMA
Published: 2020

6. Connecting Knowledge Compilation Classes and Width Parameters

Author: Mikaël Monet, Pierre Senellart, Antoine Amarilli, Florent Capelli, Data, Intelligence and Graphs (DIG), Laboratoire Traitement et Communication de l'Information (LTCI), Institut Mines-Télécom [Paris] (IMT)-Télécom Paris-Institut Mines-Télécom [Paris] (IMT)-Télécom Paris, Linking Dynamic Data (LINKS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Value from Data (VALDA ), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, 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)-É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)-Inria de Paris, Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Paris (ENS-PSL), and 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)-École normale supérieure - Paris (ENS-PSL)
Subjects: FOS: Computer and information sciences, Boolean circuit, Treewidth, H.2, Pathwidth, 0102 computer and information sciences, 02 engineering and technology, Arity, 01 natural sciences, Upper and lower bounds, Theoretical Computer Science, Computer Science - Databases, 020204 information systems, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, Knowledge compilation, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], Boolean circuits, Mathematics, Discrete mathematics, Degree (graph theory), Databases (cs.DB), OBDDs, d-DNNFs, Monotone polygon, Computational Theory and Mathematics, 010201 computation theory & mathematics
Abstract: The field of knowledge compilation establishes the tractability of many tasks by studying how to compile them to Boolean circuit classes obeying some requirements such as structuredness, decomposability, and determinism. However, in other settings such as intensional query evaluation on databases, we obtain Boolean circuits that satisfy some width bounds, e.g., they have bounded treewidth or pathwidth. In this work, we give a systematic picture of many circuit classes considered in knowledge compilation and show how they can be systematically connected to width measures, through upper and lower bounds. Our upper bounds show that bounded-treewidth circuits can be constructively converted to d-SDNNFs, in time linear in the circuit size and singly exponential in the treewidth; and that bounded-pathwidth circuits can similarly be converted to uOBDDs. We show matching lower bounds on the compilation of monotone DNF or CNF formulas to structured targets, assuming a constant bound on the arity (size of clauses) and degree (number of occurrences of each variable): any d-SDNNF (resp., SDNNF) for such a DNF (resp., CNF) must be of exponential size in its treewidth, and the same holds for uOBDDs (resp., n-OBDDs) when considering pathwidth. Unlike most previous work, our bounds apply to any formula of this class, not just a well-chosen family. Hence, we show that pathwidth and treewidth respectively characterize the efficiency of compiling monotone DNFs to uOBDDs and d-SDNNFs with compilation being singly exponential in the corresponding width parameter. We also show that our lower bounds on CNFs extend to unstructured compilation targets, with an exponential lower bound in the treewidth (resp., pathwidth) when compiling monotone CNFs of constant arity and degree to DNNFs (resp., nFBDDs)., 46 pages. Extended version of arXiv:1709.06188. Up to the stylesheet, page/environment numbering, minor formatting, and publisher-induced changes, this is the exact content of the paper in Theory of Computing Systems . The difference in the titles (missing "and") is an error introduced by the publisher
Published: 2020

7. The Inverse Voronoi Problem in Graphs I: Hardness

Author: Bojan Mohar, Hebert Pérez-Rosés, Édouard Bonnet, Sergio Cabello, 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), Faculty of Mathematics and Physics [Ljubljana] (FMF), University of Ljubljana, Simon Fraser University (SFU.ca), Universitat Rovira i Virgili, 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 de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Bonnet, Édouard
Subjects: General Computer Science, Inverse, Parameterized complexity, 0102 computer and information sciences, 02 engineering and technology, [INFO] Computer Science [cs], Computer Science::Computational Geometry, 01 natural sciences, distances in graphs, inverse Voronoi problem, Combinatorics, symbols.namesake, Pathwidth, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], Voronoi diagram, Mathematics, NP-complete, parameterized complexity, Applied Mathematics, Graph, Computer Science Applications, Planar graph, 010201 computation theory & mathematics, Theory of computation, symbols, 020201 artificial intelligence & image processing, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: We introduce the inverse Voronoi diagram problem in graphs: given a graph G with positive edge-lengths and a collection $${\mathbb {U}}$$ of subsets of vertices of V(G), decide whether $${\mathbb {U}}$$ is a Voronoi diagram in G with respect to the shortest-path metric. We show that the problem is NP-hard, even for planar graphs where all the edges have unit length. We also study the parameterized complexity of the problem and show that the problem is W[1]-hard when parameterized by the number of Voronoi cells or by the pathwidth of the graph.
Published: 2020

8. On the Complexity of Computing Treebreadth

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

9. Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2

Author: Daniël Paulusma, Pinar Heggernes, Paloma T. Lima, Dieter Kratsch, Petr A. Golovach, Laboratoire de Génie Informatique, de Production et de Maintenance (LGIPM), and Université de Lorraine (UL)
Subjects: Class (set theory), General Computer Science, Applied Mathematics, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Graph, Computer Science Applications, [SPI.AUTO]Engineering Sciences [physics]/Automatic, Perspective (geometry), Pathwidth, Square root, 010201 computation theory & mathematics, Outerplanar graph, Theory of computation, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Algorithm, ComputingMilieux_MISCELLANEOUS, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics
Abstract: Deciding if a graph has a square root is a classical problem, which has been studied extensively both from graph-theoretic and algorithmic perspective. As the problem is NP-complete, substantial effort has been dedicated to determining the complexity of deciding if a graph has a square root belonging to some specific graph class $${{\mathcal {H}}}$$ . There are both polynomial-time solvable and NP-complete results in this direction, depending on $${{\mathcal {H}}}$$ . We present a general framework for the problem if $$\mathcal{H}$$ is a class of sparse graphs. This enables us to generalize a number of known results and to give polynomial-time algorithms for the cases where $${{\mathcal {H}}}$$ is the class of outerplanar graphs and $${{\mathcal {H}}}$$ is the class of graphs of pathwidth at most 2.
Published: 2019

10. Parameterized Complexity of Safe Set

Author: Michael Lampis, Ioannis Katsikarelis, Tesshu Hanaka, Rémy Belmonte, Yota Otachi, Hirotaka Ono, autre, AUTRES, Chuo University (Chuo University), 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), Department of Mathematical Informatics, The University of Tokyo (UTokyo), Kumamoto Gakuen University, Gakuen University, University of Electro-Communications [Tokyo] (UEC), and Nagoya University
Subjects: FOS: Computer and information sciences, General Computer Science, 0211 other engineering and technologies, Vertex cover, Parameterized complexity, Pathwidth, 0102 computer and information sciences, 02 engineering and technology, Computational Complexity (cs.CC), 01 natural sciences, Theoretical Computer Science, Vulnerability parameter, Combinatorics, Set (abstract data type), Polynomial kernel, Clique-width, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], ComputingMilieux_MISCELLANEOUS, Mathematics, Connected component, 021103 operations research, Safe set, Double exponential function, 020206 networking & telecommunications, Graph, Computer Science Applications, Computer Science - Computational Complexity, Computational Theory and Mathematics, 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Geometry and Topology
Abstract: In this paper we study the problem of finding a small safe set S in a graph G, i.e. a non-empty set of vertices such that no connected component of G[S] is adjacent to a larger component in $G - S$. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is W[2]-hard when parameterized by the pathwidth $\mathsf {pw}$ and cannot be solved in time $n^{o(\mathsf {pw})}$ unless the ETH is false, (2) it admits no polynomial kernel parameterized by the vertex cover number $\mathsf {vc}$ unless $\mathrm {PH} = \varSigma ^{\mathrm {p}}_{3}$, but (3) it is fixed-parameter tractable (FPT) when parameterized by the neighborhood diversity $\mathsf {nd}$, and (4) it can be solved in time $n^{f(\mathsf {cw})}$ for some double exponential function f where $\mathsf {cw}$ is the clique-width. We also present (5) a faster FPT algorithm when parameterized by solution size.
Published: 2019

11. Sequentialization and Procedural Complexity in Automata Networks

Author: Florian Bridoux, Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), and Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)
Subjects: FOS: Computer and information sciences, Discrete Mathematics (cs.DM), General Computer Science, parallel update schedule, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Upper and lower bounds, Theoretical Computer Science, 03 medical and health sciences, 0302 clinical medicine, Pathwidth, Order (group theory), Automata networks, sequential update schedules, 030304 developmental biology, Mathematics, Discrete mathematics, 0303 health sciences, Finite-state machine, Exact relation, Construct (python library), Automaton, Graph (abstract data type), intrinsic simulation, procedural complexity, 030217 neurology & neurosurgery, Computer Science - Discrete Mathematics
Abstract: International audience; In this article we consider finite automata networks (ANs) with two kinds of update schedules: the parallel one (all automata are updated all together) and the sequential ones (the automata are updated periodically one at a time according to a total order w). The cost of sequentialization of a given AN h is the number of additional automata required to simulate h by a sequential AN with the same alphabet. We construct, for any n and q, an AN h of size n and alphabet size q whose cost of sequentialization is at least n/3. We also show that, if q ≥ 4, we can find one whose cost is at least n/2 − log q (n). We prove that n/2 + log q (n/2 + 1) is an upper bound for the cost of sequentialization of any AN h of size n and alphabet size q. Finally, we exhibit the exact relation between the cost of sequentialization of h and its procedural complexity with unlimited memory and prove that its cost of sequentialization is less than or equal to the pathwidth of its interaction graph.
Published: 2018

12. From tree-decompositions to clique-width terms

Author: Bruno Courcelle, 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), ANR-15-CE40-0009,GraphEn,Enumération dans les graphes et les hypergraphes: algorithmes et complexité(2015), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2, ANR: GraphEn,Enumeration on Graphs and Hypergraphs: Algorithms and Complexity, Courcelle, Bruno, and Enumération dans les graphes et les hypergraphes: algorithmes et complexité - - GraphEn2015 - ANR-15-CE40-0009 - AAPG2015 - VALID
Subjects: [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], planar graph, 0102 computer and information sciences, 02 engineering and technology, Tree-depth, 01 natural sciences, Combinatorics, tree-width, Pathwidth, Chordal graph, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Split graph, Mathematics, Block graph, Discrete mathematics, Trémaux tree, sparse graph, Applied Mathematics, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 020206 networking & telecommunications, Treewidth, 010201 computation theory & mathematics, Independent set, MathematicsofComputing_DISCRETEMATHEMATICS, clique-width
Abstract: Tree-width and clique-width are two important graph complexity measures that serve as parameters in many fixed-parameter tractable algorithms. We give two algorithms that transform tree-decompositions represented by normal trees into clique-width terms (a rooted tree is normal for a graph if its nodes are the vertices of the graph and every two adjacent vertices are on a path of the tree starting at the root). As a consequence, we obtain that, for certain classes of sparse graphs, clique-width is polynomially bounded in terms of tree-width. It is even linearly bounded for planar graphs and incidence graphs. These results are useful in the construction of model-checking algorithms for problems described by monadic second-order formulae, including those allowing edge set quantifications.
Published: 2018

13. On the forbidden induced subgraph probe and sandwich problems

Author: Luerbio Faria, Sulamita Klein, Fernanda Couto, Sylvain Gravier, Universidade do Estado do Rio de Janeiro [Rio de Janeiro] (UERJ), Institut Fourier (IF ), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia (COPPE-UFRJ), Universidade Federal do Rio de Janeiro (UFRJ), Institut Fourier (IF), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), COPPE - Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia (COPPE-UFRJ), and Universidade Federal do Rio de Janeiro [Rio de Janeiro] (UFRJ)
Subjects: Discrete mathematics, Applied Mathematics, 010102 general mathematics, 0102 computer and information sciences, 01 natural sciences, Combinatorics, Indifference graph, Pathwidth, 010201 computation theory & mathematics, Graph sandwich problem, Chordal graph, Discrete Mathematics and Combinatorics, Cograph, Split graph, 0101 mathematics, [MATH]Mathematics [math], ComputingMilieux_MISCELLANEOUS, Mathematics, Universal graph, Forbidden graph characterization
Abstract: In this work we compare the complexities of graph sandwich problems, partitioned and unpartitioned probe problems. Particularly, we consider the problem of recognizing probe graphs with respect to a class of graphs defined by excluding induced subgraphs. Our main result is: for F-free graphs, where F is a 3-connected, non complete graph, we prove that if F-free graph sandwich problem is NP-complete, then partitioned probeF-free problem and probeF-free problem are NP-complete. We also compare partitioned and unpartitioned versions of probe problems dealing with 2-connected graphs. Besides that, we consider Ck-free and (C4,…,C∣N∣)-free graphs and we prove that both problems in both versions of probe problems are NP-complete. In contrast, we prove that probe (Kr∖e)-free is polynomially solvable, where Kr∖e means a complete graph of size r without one edge. Finally, motivated by probeC4-free, we analyze the complexity of finding a stable set that touches every even cycle of size 2k exactly k times, which we call k-stableC2ktransversal. We prove that finding a k-stable C2k transversal can be done in polynomial time.
Published: 2018

14. Branching Measures and Nearly Acyclic NFAs

Author: Chris Keeler, Kai Salomaa, Queen's University [Kingston, Canada], Giovanni Pighizzini, Cezar Câmpeanu, TC 1, and WG 1.2
Subjects: Discrete mathematics, Path width, Finite-state machine, Computation, 020207 software engineering, 0102 computer and information sciences, 02 engineering and technology, 16. Peace & justice, 01 natural sciences, Branching (linguistics), High Energy Physics::Theory, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Pathwidth, 010201 computation theory & mathematics, Computer Science (miscellaneous), 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], Nondeterministic finite automaton, Computer Science::Formal Languages and Automata Theory, Mathematics
Abstract: To get a more comprehensive understanding of the amount of branching in computations of a nondeterministic finite automaton (NFA), we introduce and study the string path width and depth path width measures. For a given NFA, the string path width on a string [Formula: see text] counts the number of all complete computations on [Formula: see text], and the depth path width on an integer [Formula: see text] counts the number of complete computations on all strings of length [Formula: see text]. We give an algorithm to decide the finiteness of the depth path width of an NFA. Deciding finiteness of string path width can be reduced to the corresponding question on ambiguity. An NFA is nearly acyclic if any computation can pass through at most one cycle. The class of nearly acyclic NFAs consists of exactly all NFAs with finite depth path width. Using this characterization we show that the finite depth path width of an [Formula: see text]-state NFA over a [Formula: see text]-letter alphabet is at most [Formula: see text] and that this bound is tight. The nearly acyclic NFAs recognize exactly the class of constant density regular languages.
Published: 2017

15. On the Number of Labeled Graphs of Bounded Treewidth

Author: Ignasi Sau, Marc Noy, Julien Baste, 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), Universitat Politècnica de Catalunya [Barcelona] (UPC), ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016), 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 ), Universitat Politècnica de Catalunya [Barcelona] ( UPC ), Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. MD - Matemàtica Discreta, and Universidade Federal do Ceará = Federal University of Ceará (UFC)
Subjects: FOS: Computer and information sciences, [ MATH ] Mathematics [math], [ INFO ] Computer Science [cs], Discrete Mathematics (cs.DM), G.2.1, G.2.2, 0102 computer and information sciences, 01 natural sciences, Upper and lower bounds, enumeration, Combinatorics, Pathwidth, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Computer Science - Data Structures and Algorithms, FOS: Mathematics, Enumeration, treewidth, Discrete Mathematics and Combinatorics, Order (group theory), Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Direct consequence, 05C85, [INFO]Computer Science [cs], 0101 mathematics, Absolute constant, [MATH]Mathematics [math], ComputingMilieux_MISCELLANEOUS, Mathematics, Physics, 010102 general mathematics, pathwidth, Order (ring theory), 05C30, 05C85, Treewidth, proper-pathwidth, 010201 computation theory & mathematics, Bounded function, 05C30, partial k-trees, Combinatorics (math.CO), properpathwidth, Computer Science - Discrete Mathematics
Abstract: We focus on counting the number of labeled graphs on $n$ vertices and treewidth at most $k$ (or equivalently, the number of labeled partial $k$-trees), which we denote by $T_{n,k}$. So far, only the particular cases $T_{n,1}$ and $T_{n,2}$ had been studied. We show that $$ \left(c \cdot \frac{k\cdot 2^k \cdot n}{\log k} \right)^n \cdot 2^{-\frac{k(k+3)}{2}} \cdot k^{-2k-2}\ \leq\ T_{n,k}\ \leq\ \left(k \cdot 2^k \cdot n\right)^n \cdot 2^{-\frac{k(k+1)}{2}} \cdot k^{-k}, $$ for $k > 1$ and some explicit absolute constant $c > 0$. The upper bound is an immediate consequence of the well-known number of labeled $k$-trees, while the lower bound is obtained from an explicit algorithmic construction. It follows from this construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at most $k$., 12 pages, 3 figures
Published: 2017

16. Knowledge Discovery in Graphs Through Vertex Separation

Author: Catherine Mancel, Marc Queudot, Marc Sarfati, Marie-Jean Meurs, Université du Québec à Montréal = University of Québec in Montréal (UQAM), École polytechnique (X), and Ecole Nationale de l'Aviation Civile (ENAC)
Subjects: 021103 operations research, Theoretical computer science, [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Computer science, Graph partitioning, 0211 other engineering and technologies, Vertex cover, Vertex Separator Problem, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Longest path problem, Modular decomposition, Indifference graph, Pathwidth, Knowledge discovery, 010201 computation theory & mathematics, Chordal graph, Maximal independent set, Graph product, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; This paper presents our ongoing work on the Vertex Separator Problem (VSP), and its application to knowledge discovery in graphs representing real data. The classic VSP is modeled as an integer linear program. We propose several variants to adapt this model to graphs with various properties. To evaluate the relevance of our approach on real data, we created two graphs of different size from the IMDb database. The model was applied to the separation of these graphs. The results demonstrate how the model is able to semantically separate graphs into clusters.
Published: 2017

17. On the complexity of finding a potential community

Author: Thomas Pontoizeau, Zsolt Tuza, Cristina Bazgan, 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), Department of Computer Science - University of Pannonia (DCS), and University of Pannonia
Subjects: Discrete mathematics, Combinatorial optimization, 05 social sciences, Independent set, 050401 social sciences methods, 0102 computer and information sciences, Complexity, 01 natural sciences, 1-planar graph, Metric dimension, Combinatorics, Algorithm, Indifference graph, Pathwidth, 0504 sociology, 010201 computation theory & mathematics, Chordal graph, Bipartite graph, Maximal independent set, [INFO]Computer Science [cs], Split graph, Approximation, Inapproximability, Mathematics, Partition
Abstract: LNCS, volume 10236; International audience; An independent 2-clique of a graph is a subset of vertices that is an independent set and such that any two vertices inside have a common neighbor outside. In this paper, we study the complexity of finding an independent 2-clique of maximum size in several graph classes and we compare its complexity with the complexity of maximum independent set. We prove that this problem is NP-hard on apex graphs, APX-hard on line graphs, not n1/2−ϵ-approximable on bipartite graphs and not n1−ϵ-approximable on split graphs, while it is polynomial-time solvable on graphs of bounded degree and their complements, graphs of bounded treewidth, planar graphs, (C3,C6)-free graphs, threshold graphs, interval graphs and cographs.
Published: 2017

18. Exclusive Graph Searching

Author: Nicolas Nisse, Janna Burman, Lélia Blin, Networks and Performance Analysis (NPA), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Université d'Évry-Val-d'Essonne (UEVE), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), 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: 0209 industrial biotechnology, Modeling software, Theoretical computer science, General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, Monotonic function, 0102 computer and information sciences, 02 engineering and technology, Strength of a graph, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, 020901 industrial engineering & automation, Pathwidth, Graph power, Graph property, Complement graph, Mathematics, Distributed Computing Environment, 021103 operations research, Applied Mathematics, Tree decomposition, Computer Science Applications, Graph bandwidth, 010201 computation theory & mathematics, Graph (abstract data type), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Null graph
Abstract: International audience; This paper tackles the well known graph searching problem, where a team of searchers aims at capturing an intruder in a network, modeled as a graph. This problem has been mainly studied for its relationship with the pathwidth of graphs. All variants of this problem assume that any node can be simultaneously occupied by several searchers. This assumption may be unrealistic, e.g., in the case of searchers modeling physical searchers, or may require each individual node to provide additional resources, e.g., in the case of searchers modeling software agents. We thus introduce and investigate exclusive graph searching, in which no two or more searchers can occupy the same node at the same time. As for the classical variants of graph searching, we study the minimum number of searchers required to capture the intruder. This number is called the exclusive search number of the considered graph. Exclusive graph searching appears to be considerably more complex than classical graph searching, for at least two reasons: (1) it does not satisfy the monotonicity property, and (2) it is not closed under minor. Moreover, we observe that the exclusive search number of a tree may differ exponentially from the values of classical search numbers (e.g., pathwidth). Nevertheless, we design a polynomial-time algorithm which, given any n-node tree T , computes the exclusive search number of T in time O(n 3). Moreover, for any integer k, we provide a characterization of the trees T with exclusive search number at most k. Finally, we prove that the ratio between the exclusive search number and the pathwidth of a graph is bounded by its maximum degree.
Published: 2017

19. The firefighter problem: Further steps in understanding its complexity

Author: Morgan Chopin, Janka Chlebíková, School of Computing, University of Portsmouth, DECISION, Laboratoire d'Informatique de Paris 6 (LIP6), and Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)
Subjects: bandwidth, Vertex deletion, General Computer Science, Parameterized complexity, Pathwidth, firefighter problem, 0102 computer and information sciences, 02 engineering and technology, Time step, 01 natural sciences, Theoretical Computer Science, Trees, Combinatorics, parametrised complexity, Computer Science::Discrete Mathematics, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], Mathematics, Discrete mathematics, cutwidth, Degree (graph theory), Bandwidth (signal processing), pathwidth, trees, Graph, 010201 computation theory & mathematics, Bounded function, Firefighter problem, 020201 artificial intelligence & image processing
Abstract: We consider the complexity of the firefighter problem where a budget of b≥1 firefighters are available at each time step. This problem is known to be NP-complete even on trees of degree at most three and b=1 [S. Finbow, A. King, G. MacGillivray, and R. Rizzi. The firefighter problem for graphs of maximum degree three. Discrete Mathematics, 307(16):2094-2105, 2007] and on trees of bounded degree (b+3 for any fixed b≥2 [C. Bazgan, M. Chopin, and B. Ries. The firefighter problem with more than one firefighter on trees. Discrete Applied Mathematics, 161(7-8):899-908, 2013]. In this paper we provide further insight into the complexity landscape of the problem by showing a complexity dichotomy result with respect to the parameters pathwidth and maximum degree of the input graph. More precisely, first, we prove that the problem is NP-complete even on trees of pathwidth at most three for any b≥1. Then we show that the problem turns out to be fixed parameter-tractable with respect to the combined parameter "pathwidth" and "maximum degree" of the input graph. Finally, we show that the problem remains NP-complete on very dense graphs, namely co-bipartite graphs, but is fixed-parameter tractable with respect to the parameter "cluster vertex deletion".
Published: 2017

20. Les graphes planaires sans triangle ont-ils un nombre exponentiel de 3-colorations ?

Author: Jean-Sébastien Sereni, Zdeněk Dvořák, Computer Science Institute of Charles University [Prague] (IUUK), Charles University [Prague] (CU), Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Les Hôpitaux Universitaires de Strasbourg (HUS)-Centre National de la Recherche Scientifique (CNRS)-Matériaux et Nanosciences Grand-Est (MNGE), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Réseau nanophotonique et optique, and Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Grötzsch's theorem, Planar straight-line graph, triangle-free graphs, Request graphs, 05C15, 05C10, 0102 computer and information sciences, Computer Science::Computational Geometry, 01 natural sciences, Theoretical Computer Science, Combinatorics, Indifference graph, symbols.namesake, Pathwidth, Chordal graph, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, 0101 mathematics, Equivalence (measure theory), Mathematics, Discrete mathematics, Conjecture, Applied Mathematics, 05C15, O5C10, 010102 general mathematics, planar graphs, Planar graph, Computational Theory and Mathematics, 010201 computation theory & mathematics, symbols, Geometry and Topology
Abstract: Thomassen conjectured that triangle-free planar graphs have an exponential number of $3$-colorings. We show this conjecture to be equivalent to the following statement: there exists a positive real $\alpha$ such that whenever $G$ is a planar graph and $A$ is a subset of its edges whose deletion makes $G$ triangle-free, there exists a subset $A'$ of $A$ of size at least $\alpha|A|$ such that $G-(A\setminus A')$ is $3$-colorable. This equivalence allows us to study restricted situations, where we can prove the statement to be true.
Published: 2017

21. Large Scale Density-friendly Graph Decomposition via Convex Programming

Author: Maximilien Danisch, Mauro Sozio, T.-H. Hubert Chan, Sozio, Mauro, Fields: Recherche d'événements intéressants dans les grands réseaux sociaux - - FIELDS2015 - ANR-15-CE23-0006 - AAPG2015 - VALID, Laboratoire Traitement et Communication de l'Information (LTCI), Institut Mines-Télécom [Paris] (IMT)-Télécom Paris, Department of Computer Science [Hong Kong], City University of Hong Kong [Hong Kong] (CUHK), and ANR-15-CE23-0006,FIELDS,Fields: Recherche d'événements intéressants dans les grands réseaux sociaux(2015)
Subjects: Factor-critical graph, Theoretical computer science, Computer science, Voltage graph, 02 engineering and technology, Strength of a graph, [INFO] Computer Science [cs], Tree-depth, Tree decomposition, Graph, Modular decomposition, Treewidth, Graph bandwidth, Pathwidth, 020204 information systems, Clique-width, Convex optimization, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], 020201 artificial intelligence & image processing, Complement graph, Graph product, ComputingMilieux_MISCELLANEOUS, Distance-hereditary graph, Hopcroft–Karp algorithm
Abstract: Algorithms for finding dense regions in an input graph have proved to be effective tools in graph mining and data analysis. Recently, Tatti and Gionis [WWW 2015] presented a novel graph decomposition (known as the locally-dense decomposition) that is similar to the well-known k-core decomposition, with the additional property that its components are arranged in order of their densities. Such a decomposition provides a valuable tool in graph mining. Unfortunately, their algorithm for computing the exact decomposition is based on a maximum-flow algorithm which cannot scale to massive graphs, while the approximate decomposition defined by the same authors misses several interesting properties. This calls for scalable algorithms for computing such a decomposition. In our work, we devise an efficient algorithm which is able to compute exact locally-dense decompositions in real-world graphs containing up to billions of edges. Moreover, we provide a new definition of approximate locally-dense decomposition which retains most of the properties of an exact decomposition, for which we devise an algorithm that can scale to real-world graphs containing up to tens of billions of edges. Our algorithm is based on the classic Frank-Wolfe algorithm which is similar to gradient descent and can be efficiently implemented in most of the modern architectures dealing with massive graphs. We provide a rigorous study of our algorithms and their convergence rates. We conduct an extensive experimental evaluation on multi-core architectures showing that our algorithms converge much faster in practice than their worst-case analysis. Our algorithm is even more efficient for the more specialized problem of computing a densest subgraph.
Published: 2017

22. Efficient maximum matching algorithms for trapezoid graphs

Author: Phan-Thuan Do, Van-Thieu Vu, Ngoc-Khang Le, Thomassé, Stéphan, Hanoi University of Science and Technology (HUST), 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), É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::General Mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Mathematics::Classical Analysis and ODEs, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO] Computer Science [cs], Mathematics::Numerical Analysis, Combinatorics, Indifference graph, Pathwidth, Chordal graph, Hardware_INTEGRATEDCIRCUITS, QA1-939, Discrete Mathematics and Combinatorics, Cograph, [INFO]Computer Science [cs], ComputingMilieux_MISCELLANEOUS, Hopcroft–Karp algorithm, Mathematics, Discrete mathematics, trapezoid graphs, maximum matching, Applied Mathematics, Trapezoid graph, Computer Science::Numerical Analysis, Bipartite graph, Maximal independent set, Algorithm, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: Trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. Many NP-hard problems can be solved in polynomial time if they are restricted on trapezoid graphs. A matching in a graph is a set of pairwise disjoint edges, and a maximum matching is a matching of maximum size. In this paper, we first propose an $O(n(\log n)^3)$ algorithm for finding a maximum matching in trapezoid graphs, then improve the complexity to $O(n(\log n)^2)$. Finally, we generalize this algorithm to a larger graph class, namely $k$-trapezoid graphs. To the best of our knowledge, these are the first efficient maximum matching algorithms for trapezoid graphs.
Published: 2017

23. An Indexing Framework for Queries on Probabilistic Graphs

Author: Reynold Cheng, Pierre Senellart, Silviu Maniu, Données et Connaissances Massives et Hétérogènes (LRI) (LaHDAK - LRI), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), The University of Hong Kong (HKU), Value from Data (VALDA ), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), 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)-É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)-Inria de 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), École normale supérieure - Paris (ENS-PSL), and 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)-École normale supérieure - Paris (ENS-PSL)
Subjects: shortest path, Correctness, Theoretical computer science, Computer science, tree decomposition, Probabilistic database, 02 engineering and technology, Pathwidth, Reachability, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, treewidth, ComputingMilieux_MISCELLANEOUS, [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Probabilistic logic, Data structure, Tree decomposition, Longest path problem, Graph, Vertex (geometry), Treewidth, Shortest path problem, 020201 artificial intelligence & image processing, uncertain graph, triconnected component, Information Systems, SPQR, reachability
Abstract: Information in many applications, such as mobile wireless systems, social networks, and road networks, is captured by graphs. In many cases, such information is uncertain. We study the problem of querying a probabilistic graph, in which vertices are connected to each other probabilistically. In particular, we examine “source-to-target” queries (ST-queries), such as computing the shortest path between two vertices. The major difference with the deterministic setting is that query answers are enriched with probabilistic annotations. Evaluating ST-queries over probabilistic graphs is #P-hard, as it requires examining an exponential number of “possible worlds”—database instances generated from the probabilistic graph. Existing solutions to the ST-query problem, which sample possible worlds, have two downsides: (i) a possible world can be very large and (ii) many samples are needed for reasonable accuracy. To tackle these issues, we study the ProbTree , a data structure that stores a succinct, or indexed , version of the possible worlds of the graph. Existing ST-query solutions are executed on top of this structure, with the number of samples and sizes of the possible worlds reduced. We examine lossless and lossy methods for generating the ProbTree, which reflect the tradeoff between the accuracy and efficiency of query evaluation. We analyze the correctness and complexity of these approaches. Our extensive experiments on real datasets show that the ProbTree is fast to generate and small in size. It also enhances the accuracy and efficiency of existing ST-query algorithms significantly.
Published: 2017

24. An efficient exact algorithm for triangle listing in large graphs

Author: Hamida Seba, Sofiane Lagraa, Heterogeneous and Adaptive distributed DAta management Systems (HADAS), Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), and Seba, Hamida
Subjects: Computer Networks and Communications, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], modular decomposition, Comparability graph, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Triangle listing, large graphs, law.invention, Pathwidth, law, Outerplanar graph, Line graph, 0202 electrical engineering, electronic engineering, information engineering, massive graphs, graph compression, Mathematics, Discrete mathematics, Block graph, Computer Science Applications, Modular decomposition, 010201 computation theory & mathematics, Topological graph theory, 020201 artificial intelligence & image processing, Graph product, Information Systems, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; This paper presents a new efficient exact algorithm for listing triangles in a large graph. While the problem of listing triangles in a graph has been considered before, dealing with large graphs continues to be a challenge. Although previous research has attempted to tackle the challenge, this is the first contribution that addresses this problem on a compressed copy of the input graph. In fact, the proposed solution lists the triangles without decompressing the graph. This yields interesting improvements in both storage requirement of the graphs and their time processing.
Published: 2016
Full Text: View/download PDF

25. Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs

Author: George B. Mertzios, Florent Foucaud, Reza Naserasr, Aline Parreau, Petru Valicov, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Mayr, Ernst W., Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS), School of Engineering and Computing Sciences, Durham University, Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), 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), Département de Mathématiques [Liège], Université de Liège, Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Naserasr, Reza, SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), and Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)
Subjects: 0209 industrial biotechnology, Metric dimension, 0102 computer and information sciences, 02 engineering and technology, [INFO] Computer Science [cs], 01 natural sciences, Combinatorics, Indifference graph, 020901 industrial engineering & automation, Pathwidth, Identifying codes, Chordal graph, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Permutation graph, [NLIN] Nonlinear Sciences [physics], [INFO]Computer Science [cs], [NLIN]Nonlinear Sciences [physics], ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete mathematics, Trapezoid graph, Interval graph, Complexity, 010201 computation theory & mathematics, Interval graphs, Maximal independent set, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; We study the problems Locating-Dominating Set and Metric Dimension, which consist of determining a minimum-size set of vertices that distinguishes the vertices of a graph using either neighbourhoods or distances. We consider these problems when restricted to interval graphs and permutation graphs. We prove that both decision problems are NP-complete, even for graphs that are at the same time interval graphs and permutation graphs and have diameter 2. While Locating-Dominating Set parameterized by solution size is trivially fixed-parameter-tractable, it is known that Metric Dimension is W [2]-hard. We show that for interval graphs, this parameterization of Metric Dimension is fixed-parameter-tractable.
Published: 2016

26. Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition

Author: Prosenjit Bose, Anna Lubiw, Paz Carmi, Irina Kostitsyna, Nicolas Bonichon, Sander Verdonschot, 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), Carleton University, David R. Cheriton School of Computer Science, University of Waterloo [Waterloo], School of Computer Science (Carleton, Ottawa), ANR-10-IDEX-0003,IDEX BORDEAUX,Initiative d'excellence de l'Université de Bordeaux(2010), Bonichon, Nicolas, and Initiative d'excellence de l'Université de Bordeaux - - IDEX BORDEAUX2010 - ANR-10-IDEX-0003 - IDEX - VALID
Subjects: Discrete mathematics, Computational Geometry (cs.CG), FOS: Computer and information sciences, 0102 computer and information sciences, 02 engineering and technology, Computer Science::Computational Geometry, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, 1-planar graph, Longest path problem, Vertex (geometry), Combinatorics, Indifference graph, Spatial network, Pathwidth, [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], 010201 computation theory & mathematics, Chordal graph, 0202 electrical engineering, electronic engineering, information engineering, Computer Science - Computational Geometry, 020201 artificial intelligence & image processing, Maximal independent set, Mathematics
Abstract: A geometric graph is angle-monotone if every pair of vertices has a path between them that---after some rotation---is $x$- and $y$-monotone. Angle-monotone graphs are $\sqrt 2$-spanners and they are increasing-chord graphs. Dehkordi, Frati, and Gudmundsson introduced angle-monotone graphs in 2014 and proved that Gabriel triangulations are angle-monotone graphs. We give a polynomial time algorithm to recognize angle-monotone geometric graphs. We prove that every point set has a plane geometric graph that is generalized angle-monotone---specifically, we prove that the half-$\theta_6$-graph is generalized angle-monotone. We give a local routing algorithm for Gabriel triangulations that finds a path from any vertex $s$ to any vertex $t$ whose length is within $1 + \sqrt 2$ times the Euclidean distance from $s$ to $t$. Finally, we prove some lower bounds and limits on local routing algorithms on Gabriel triangulations., Comment: Appears in the Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)
Published: 2016

27. More Results on the Complexity of Identifying Problems in Graphs

Author: Olivier Hudry, Antoine Lobstein, Mathématiques discrètes, Codage et Cryptographie (MC2), Laboratoire Traitement et Communication de l'Information (LTCI), Institut Mines-Télécom [Paris] (IMT)-Télécom Paris-Institut Mines-Télécom [Paris] (IMT)-Télécom Paris, Département Informatique et Réseaux (INFRES), and Télécom ParisTech
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], General Computer Science, 0102 computer and information sciences, Descriptive complexity theory, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Identifying Codes, Theoretical Computer Science, Combinatorics, 03 medical and health sciences, Structural complexity theory, 0302 clinical medicine, Pathwidth, Complexity Classes, Chordal graph, Hardness, Polyno- mial Hierarchy, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Complexity class, Graph isomorphism, Mathematics, Polynomial hierarchy, Discrete mathematics, Complexity, PH, 010201 computation theory & mathematics, Twin-Free Graphs, Graph Theory, 030221 ophthalmology & optometry, NP-Completeness
Abstract: International audience; We investigate the complexity of several problems linked with identification in graphs, such as, given an integer r >= 1 and a graph G = (V;E), the existence of, or search for, optimal r-identifying codes in G, or optimal r-identifying codes in G containing a given subset of vertices. We locate these problems in the complexity classes of the polynomial hierarchy.
Published: 2016

28. Three ways to cover a graph

Author: Torsten Ueckerdt, Kolja Knauer, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Algorithmique, Combinatoire et Recherche Opérationnelle (ACRO), Laboratoire d'Informatique et Systèmes (LIS), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), Karlsruhe Institute of Technology (KIT), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), and Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Discrete mathematics, Dense graph, Arboricity, 010102 general mathematics, 0102 computer and information sciences, Covering number, 01 natural sciences, 1-planar graph, Theoretical Computer Science, Planar graph, Combinatorics, symbols.namesake, Indifference graph, Pathwidth, 010201 computation theory & mathematics, Covering graph, symbols, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, [INFO]Computer Science [cs], Combinatorics (math.CO), 0101 mathematics, Mathematics
Abstract: We consider the problem of covering an input graph $H$ with graphs from a fixed covering class $G$. The classical covering number of $H$ with respect to $G$ is the minimum number of graphs from $G$ needed to cover the edges of $H$ without covering non-edges of $H$. We introduce a unifying notion of three covering parameters with respect to $G$, two of which are novel concepts only considered in special cases before: the local and the folded covering number. Each parameter measures "how far'' $H$ is from $G$ in a different way. Whereas the folded covering number has been investigated thoroughly for some covering classes, e.g., interval graphs and planar graphs, the local covering number has received little attention. We provide new bounds on each covering number with respect to the following covering classes: linear forests, star forests, caterpillar forests, and interval graphs. The classical graph parameters that result this way are interval number, track number, linear arboricity, star arboricity, and caterpillar arboricity. As input graphs we consider graphs of bounded degeneracy, bounded degree, bounded tree-width or bounded simple tree-width, as well as outerplanar, planar bipartite, and planar graphs. For several pairs of an input class and a covering class we determine exactly the maximum ordinary, local, and folded covering number of an input graph with respect to that covering class., Comment: 20 pages, 4 figures
Published: 2016

29. On the Monotonicity of Process Number

Author: Ronan Pardo Soares, Nicolas Nisse, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Universidade Federal do Ceará = Federal University of Ceará (UFC), 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), Inria Chile, Universidad Diego Portales [Santiago] (UDP)-Universidad de la frontera [Chile]-Pontificia Universidad Católica de Chile (UC)-Institut National de Recherche en Informatique et en Automatique (Inria)-Pontificia Universidad Católica de Valparaíso (PUCV)-Universidad Adolfo Ibáñez [Santiago]-Universidad de Valparaiso [Chile]-Universidad Tecnica Federico Santa Maria [Valparaiso] (UTFSM)-Universidad de Concepción - University of Concepcion [Chile], Parallelism, Graphs and Optimization Research Group (ParGO), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), INRIA, Universidad Diego Portales [Santiago] (UDP)-Universidad de la frontera [Chile]-Universidad de Concepción [Chile]-Pontificia Universidad Católica de Chile (UC)-Institut National de Recherche en Informatique et en Automatique (Inria)-Pontificia Universidad Católica de Valparaíso (PUCV)-Universidad Adolfo Ibáñez [Santiago]-Universidad de Valparaiso [Chile]-Universidad Tecnica Federico Santa Maria [Valparaiso] (UTFSM), and Universidad de Valparaiso [Chile]-Universidad Tecnica Federico Santa Maria [Valparaiso] (UTFSM)-Universidad Adolfo Ibáñez [Santiago]-Pontificia Universidad Católica de Valparaíso (PUCV)-Institut National de Recherche en Informatique et en Automatique (Inria)-Pontificia Universidad Católica de Chile (UC)-Universidad de Concepción [Chile]-Universidad de la frontera [Chile]-Universidad Diego Portales [Santiago] (UDP)
Subjects: Strongly connected component, Computer Science::Computer Science and Game Theory, Monotonicity, Theoretical computer science, 0211 other engineering and technologies, 050801 communication & media studies, Monotonic function, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph Searching, 0508 media and communications, Pathwidth, Discrete Mathematics and Combinatorics, Game tree, Mathematics, Discrete mathematics, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Applied Mathematics, 05 social sciences, ComputingMilieux_PERSONALCOMPUTING, Control reconfiguration, 021107 urban & regional planning, Digraph, Directed graph, 16. Peace & justice, Modular decomposition, Monotone polygon, 010201 computation theory & mathematics, Process Number, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: Graph searching games involve a team of searchers that aims at capturing a fugitive in a graph. These games have been widely studied for their relationships with tree- and path-decomposition of graphs. In order to define decompositions for directed graphs, similar games have been proposed in directed graphs. In this paper, we consider such a game that has been defined and studied in the context of routing reconfiguration problems in WDM networks. Namely, in the processing game, the fugitive is invisible, arbitrary fast, it moves in the opposite direction of the arcs of a digraph, but only as long as it has access to a strongly connected component free of searchers. We prove that the processing game is monotone which leads to its equivalence with a new digraph decomposition.; Les jeux de capture impliquent une équipe d'agents qui doivent capturer un fugitif se déplaçant dans un graphe. Ces jeux ont été très étudiés pour leur interprétation en termes de décompositions de graphes (tree-decomposition, path-decomposition). Dans le but de définir de "bonnes" décompositions pour les graphes orientés, des jeux similaires ont été définis et étudiés dans les graphes orientés. Dans ce travail, nous considérons un jeu qui a été défini dans le contexte du routage dans les réseaux WDM. Dans ce jeu, le processing game, le fugitif est invisible, arbitrairement rapide et se déplace dans le sens opposé des arcs. De plus, le fugitif est capturé dès qu'il lui est impossible d'accéder à une composante fortement connexe sans agents. Nous prouvons que ce jeu est monotone. Cela permet de montrer l'équivalence du processing game et d'une nouvelle décomposition de graphes orientés.
Published: 2016

30. Experimental Evaluation of a Branch and Bound Algorithm for Computing Pathwidth and Directed Pathwidth

Author: Dorian Mazauric, David Coudert, Nicolas Nisse, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Algorithms, Biology, Structure (ABS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-13-BS02-0007,Stint,Structures Interdites(2013), ANR-11-LABX-0031,UCN@SOPHIA,Réseau orienté utilisateur(2011), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Discrete mathematics, 021103 operations research, Branch and bound, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, Time limit, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Theoretical Computer Science, Dynamic programming, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Pathwidth, Graph bandwidth, 010201 computation theory & mathematics, Bounded function, Preprocessor, Mathematics
Abstract: Path decompositions of graphs are an important ingredient of dynamic programming algorithms for solving efficiently many NP-hard problems. Therefore, computing the pathwidth and associated path decomposition of graphs has both a theoretical and practical interest. In this article, we design a branch-and-bound algorithm that computes the exact pathwidth of graphs and a corresponding path decomposition. Our main contribution consists of several nontrivial techniques to reduce the size of the input graph (preprocessing) and to cut the exploration space during the search phase of the algorithm. We evaluate experimentally our algorithm by comparing it to existing algorithms of the literature. It appears from the simulations that our algorithm offers a significant gain with respect to previous work. In particular, it is able to compute the exact pathwidth of any graph with less than 60 nodes in a reasonable running time (≤ 10min on a standard laptop). Moreover, our algorithm achieves good performance when used as a heuristic (i.e., when returning best result found within bounded time limit). Our algorithm is not restricted to undirected graphs since it actually computes the directed pathwidth that generalizes the notion of pathwidth to digraphs.
Published: 2016

31. A new self-stabilizing algorithm for maximal p-star decomposition of general graphs

Author: Brahim Neggazi, Mohammed Haddad, Hamamache Kheddouci, Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), and Université de Lyon-Université Lumière - Lyon 2 (UL2)
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, law.invention, Combinatorics, Pathwidth, law, 020204 information systems, Outerplanar graph, Line graph, 0202 electrical engineering, electronic engineering, information engineering, Cograph, Graph coloring, ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete mathematics, Voltage graph, 1-planar graph, Computer Science Applications, Modular decomposition, 010201 computation theory & mathematics, Signal Processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Algorithm, Information Systems
Abstract: We address the decomposition of graphs into stars in a distributed way.We propose a new self-stabilizing algorithm for decomposing arbitrary graphs into stars having same size.The proposed algorithm has polynomial moves complexity.Formal proofs for correctness and convergence are provided. A p-star is a complete bipartite graph K 1 , p with one center node and p leaves. In this paper, we propose a polynomial self-stabilizing algorithm for maximal graph decomposition into p-stars. Given an arbitrary graph G and a positive integer p ? 1 , this decomposition provides disjoint components of G, such that each component induces a p-star in G. Under the unfair distributed scheduler, the algorithm converges within O ( Δ 2 m ) moves where m is the number of edges and Δ is maximum node degree in the graph G.
Published: 2015

32. Nonlinear operators on graphs via stacks

Author: Jesús Angulo, Santiago Velasco-Forero, Centre de Morphologie Mathématique (CMM), MINES ParisTech - École nationale supérieure des mines de Paris, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)
Subjects: Discrete mathematics, Dense graph, Trapezoid graph, ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, 020207 software engineering, 02 engineering and technology, 01 natural sciences, Graph, Modular decomposition, Indifference graph, Pathwidth, Chordal graph, 0103 physical sciences, 0202 electrical engineering, electronic engineering, information engineering, Maximal independent set, Mathematical Morphology, 010306 general physics, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, Graph product, Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS, ComputingMethodologies_COMPUTERGRAPHICS
Abstract: International audience; We consider a framework for nonlinear operators on functions evaluated on graphs via stacks of level sets. We investigate a family of transformations on functions evaluated on graph which includes adaptive flat and non-flat erosions and dilations in the sense of mathematical morphology. Additionally, the connection to mean motion curvature on graphs is noted. Proposed operators are illustrated in the cases of functions on graphs, textured meshes and graphs of images.
Published: 2015

33. Toward An Uncertainty Principle For Weighted Graphs

Author: Bastien Pasdeloup, Vincent Gripon, Michael G. Rabbat, Réda Alami, Lab-STICC_TB_CID_TOMS, Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance ( Lab-STICC ), École Nationale d'Ingénieurs de Brest ( ENIB ) -Université de Bretagne Sud ( UBS ) -Université de Brest ( UBO ) -Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques ( IBNM ), Université de Brest ( UBO ) -Université européenne de Bretagne ( UEB ) -ENSTA Bretagne-Institut Mines-Télécom [Paris]-Centre National de la Recherche Scientifique ( CNRS ) -École Nationale d'Ingénieurs de Brest ( ENIB ) -Université de Bretagne Sud ( UBS ) -Université de Brest ( UBO ) -Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques ( IBNM ), Université de Brest ( UBO ) -Université européenne de Bretagne ( UEB ) -ENSTA Bretagne-Institut Mines-Télécom [Paris]-Centre National de la Recherche Scientifique ( CNRS ), Département Electronique ( ELEC ), Université européenne de Bretagne ( UEB ) -Télécom Bretagne-Institut Mines-Télécom [Paris], Département Image et Traitement Information ( ITI ), Institut Mines-Télécom [Paris]-Université européenne de Bretagne ( UEB ) -Télécom Bretagne, Département Signal et Communications ( SC ), Institut Mines-Télécom [Paris]-Télécom Bretagne-Université européenne de Bretagne ( UEB ), Télécom Bretagne (Institut Mines-Télécom), Lab-STICC_TB_CACS_IAS, Department of Electrical and Computer Engineering [Montreal], McGill University, Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC), École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS), Département Electronique (ELEC), Université européenne de Bretagne - European University of Brittany (UEB)-Institut Mines-Télécom [Paris] (IMT)-Télécom Bretagne, Département Image et Traitement Information (ITI), Université européenne de Bretagne - European University of Brittany (UEB)-Télécom Bretagne-Institut Mines-Télécom [Paris] (IMT), Département Signal et Communications (SC), Department of Electrical and Computer Engineering [Montréal], and McGill University = Université McGill [Montréal, Canada]
Subjects: FOS: Computer and information sciences, [ INFO.INFO-TS ] Computer Science [cs]/Signal and Image Processing, Discrete Mathematics (cs.DM), Comparability graph, [ SPI.SIGNAL ] Engineering Sciences [physics]/Signal and Image processing, law.invention, Combinatorics, Pathwidth, [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, law, Uncertainty principle, Line graph, Weighted graphs, Cograph, Split graph, Forbidden graph characterization, Mathematics, Discrete mathematics, Block graph, Signal processing on graphs, [SPI.TRON]Engineering Sciences [physics]/Electronics, [ SPI.TRON ] Engineering Sciences [physics]/Electronics, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, Graph product, Computer Science - Discrete Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: The uncertainty principle states that a signal cannot be localized both in time and frequency. With the aim of extending this result to signals on graphs, Agaskar&Lu introduce notions of graph and spectral spreads. They show that a graph uncertainty principle holds for some families of unweighted graphs. This principle states that a signal cannot be simultaneously localized both in graph and spectral domains. In this paper, we aim to extend their work to weighted graphs. We show that a naive extension of their definitions leads to inconsistent results such as discontinuity of the graph spread when regarded as a function of the graph structure. To circumvent this problem, we propose another definition of graph spread that relies on an inverse similarity matrix. We also discuss the choice of the distance function that appears in this definition. Finally, we compute and plot uncertainty curves for families of weighted graphs., 23rd European Signal Processing Conference (EUSIPCO)
Published: 2015

34. Contraction Blockers for Graphs with Forbidden Induced Paths

Author: Öznur Yaşar Diner, Bernard Ries, Daniël Paulusma, Christophe Picouleau, 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), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Department of Computer Science, Durham University, KADIR HAS UNIVERSITY, Kadir Has University (KHAS), Diner, Öznur Yaşar, Paschos, Vangelis Th., and Widmayer, Peter
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Graphique, 0102 computer and information sciences, 01 natural sciences, Graph, Combinatorics, Indifference graph, Pathwidth, Chordal graph, Cograph, [INFO]Computer Science [cs], Split graph, Complexité, 0101 mathematics, Mathematics, Discrete mathematics, Algorithmes, Clique-sum, 010102 general mathematics, Complexity, 16. Peace & justice, 1-planar graph, Treewidth, Blocker, 010201 computation theory & mathematics, Bloqueur, Graphs, Algorithms, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: CIAC 2015, Paris, France, May 20-22, 2015; International audience; We consider the following problem: can a certain graph parameter of some given graph be reduced by at least d for some integer d via at most k edge contractions for some given integer k? We examine three graph parameters: the chromatic number, clique number and independence number. For each of these graph parameters we show that, when d is part of the input, this problem is polynomial-time solvable on P4-free graphs and NP-complete as well as W[1]-hard, with parameter d, for split graphs. As split graphs form a subclass of P5-free graphs, both results together give a complete complexity classification for Pℓ-free graphs. The W[1]-hardness result implies that it is unlikely that the problem is fixed-parameter tractable for split graphs with parameter d. But we do show, on the positive side, that the problem is polynomial-time solvable, for each parameter, on split graphs if d is fixed, i.e., not part of the input. We also initiate a study into other subclasses of perfect graphs, namely cobipartite graphs and interval graphs.
Published: 2015

35. Component-cardinality-constrained critical node problem in graphs

Author: Mohammed Amin Tahraoui, Mohammed Lalou, Hamamache Kheddouci, Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), and Université de Lyon-Université Lumière - Lyon 2 (UL2)
Subjects: Block graph, Discrete mathematics, Vertex cover problem, 021103 operations research, Critical nodes, Applied Mathematics, 0211 other engineering and technologies, Interval graph, 0102 computer and information sciences, 02 engineering and technology, Complexity, 01 natural sciences, Trees, Modular decomposition, Combinatorics, Indifference graph, Pathwidth, 010201 computation theory & mathematics, Chordal graph, Chordal graphs, Discrete Mathematics and Combinatorics, Maximal independent set, [INFO]Computer Science [cs], Split graph, Mathematics
Abstract: International audience; An effective way to analyze and apprehend the structural properties of networks is to find their most critical nodes. This makes them easier to control, whether the purpose is to keep or to delete them. Given a graph, Critical Node Detection problem (CNDP) consists in finding a set of nodes, deletion of which satisfies some given connectivity metrics in the induced graph. In this paper, we propose and study a new variant of this problem, called Component-Cardinality-Constrained Critical Node Problem (3C-CNP ). In this variant, we seek to find a minimal set of nodes, removal of which constrains the size of each connected component in the induced graph to a given bound. We prove the NP-hardness of this problem on a graph of maximum degree Δ=4Δ=4, through which we deduce the NP-hardness of CNP (Arulselvan et al., 2009) on the same class of graphs. Also, we study 3C-CNP on trees for different cases depending on node weights and connection costs. For the case where node weights and connection costs have non-negative values, we prove its NP-completeness. While, for the case where node weights (or connection costs) have unit values, we present a polynomial algorithm. Also, we study 3C-CNP on chordal graphs, where we show that it is NP-complete on split graphs, and polynomially solvable on proper interval graphs.
Published: 2015

36. Rook-drawing for plane graphs

Author: Claire Pennarun, David Auber, Paul Dorbec, Nicolas Bonichon, Pennarun, Claire, Laboratoire Bordelais de Recherche en Informatique (LaBRI), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
Subjects: Discrete mathematics, Book embedding, Mathematics::Combinatorics, Planar straight-line graph, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Computer Science::Computational Geometry, 1-planar graph, Planar graph, Combinatorics, symbols.namesake, Indifference graph, Pathwidth, Chordal graph, Outerplanar graph, symbols, Mathematics::Representation Theory, Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; Motivated by visualization of large graphs, we introduce a new type of graph drawing called ``rook-drawing".A \emph{rook-drawing} of a graph $G$ is obtained by placing the $n$ nodes of $G$ on the intersections of a regular grid, such that each row and column of the grid supports exactly one node. This paper focuses on rook-drawings of planar graphs.We first give a linear algorithm to compute a planar straight-line rook-drawing for outerplanar graphs.We then characterize the maximal planar graphs admitting a planar straight-line rook-drawing, which are unique for a given order.Finally, we give a linear time algorithm to compute a polyline planar rook-drawing for plane graphs with at most $n-3$ bent edges.
Published: 2015

37. On the termination of some biclique operators on multipartite graphs

Author: Matthieu Latapy, Christophe Crespelle, Thi Ha Duong Phan, Dynamic Networks : Temporal and Structural Capture Approach (DANTE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-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-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Joseph Fourier - Grenoble 1 (UJF)-Université Jean Moulin - Lyon 3 (UJML), 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)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-Université Joseph Fourier - Grenoble 1 (UJF)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), ComplexNetworks, Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Vietnam Academy of Science and Technology (VAST), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and École normale supérieure - Lyon (ENS Lyon)-Université Lumière - Lyon 2 (UL2)-Université Joseph Fourier - Grenoble 1 (UJF)-Université Jean Moulin - Lyon 3 (UJML)
Subjects: FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Symmetric graph, Comparability graph, Graph Series, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, law.invention, Combinatorics, Pathwidth, law, Line graph, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Discrete Mathematics and Combinatorics, Multipartite graph, Mathematics - Combinatorics, Graph homomorphism, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], 0101 mathematics, Clean-factor Graph, Mathematics, Forbidden graph characterization, Discrete mathematics, Block graph, Complex Network Modelling, Applied Mathematics, 010102 general mathematics, 010201 computation theory & mathematics, Combinatorics (math.CO), Multipartite Graphs, Computer Science - Discrete Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; We define a new graph operator, called the weak-factor graph, which comes from the context of complex network modelling. The weak-factor operator is close to the well-known clique-graph operator but it rather operates in terms of bicliques in a multipartite graph. We address the problem of the termination of the series of graphs obtained by iteratively applying the weak-factor operator starting from a given input graph. As for the clique-graph operator, it turns out that some graphs give rise to series that do not terminate. Therefore, we design a slight variation of the weak-factor operator, called clean-factor, and prove that its associated series terminates for all input graphs. In addition, we show that the multipartite graph on which the series terminates has a very nice combinatorial structure: we exhibit a bijection between its vertices and the chains of the inclusion order on the intersections of the maximal cliques of the input graph.
Published: 2015

38. Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds

Author: Frédéric Maffray, Vassilis Giakoumakis, Andreas Brandstädt, Anne Berry, Modélisation, Information et Systèmes - UR UPJV 4290 (MIS), Université de Picardie Jules Verne (UPJV), Optimisation Combinatoire (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut National Polytechnique de Grenoble (INPG)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut National Polytechnique de Grenoble (INPG)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF), and Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Block graph, Discrete mathematics, Clique-sum, Applied Mathematics, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Treewidth, Combinatorics, Indifference graph, Pathwidth, Computer Science::Discrete Mathematics, 010201 computation theory & mathematics, Chordal graph, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, 020201 artificial intelligence & image processing, Cograph, Split graph, ComputingMilieux_MISCELLANEOUS, Mathematics
Abstract: A graph is hole- and diamond-free (HD-free) if none of its induced subgraphs is isomorphic to a chordless cycle of length at least five or to a diamond. Using the clique separator approach and the simple structure of atoms of HD-free graphs, we show how to recognize HD-free graphs in time O ( n 2 ) . One of the main tools is Lexicographic Breadth-First Search (LexBFS); we give two new properties of LexBFS which are essential for reaching the time bound and which hold for any graph. Moreover, we find minimal triangulations of HD-free graphs in time O ( n 2 ) , introducing efficient algorithms for the minimal triangulation of matched co-bipartite graphs and chordal bipartite graphs.
Published: 2015

39. About some robustness and complexity properties of G-graphs networks

Author: Cerasela Tanasescu, Jean-François Culus, Marc Demange, Ruxandra Marinescu-Ghemeci, Management, économie, modélisation, informatique et aide à la décision (MEMIAD), Université des Antilles (UA), ESSEC Business School, Essec Business School, University of Bucharest (UniBuc), Centre de Recherche en Economie, Gestion, Modélisation et Informatique Appliquée (CEREGMIA), Université des Antilles et de la Guyane (UAG), University of Bucharest (ROMANIA), and University of Bucharest
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC], Network, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Optimal connectivity, [MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR], Graphs and groups, Combinatorics, Indifference graph, Pathwidth, Chordal graph, Orbit graphs, Discrete Mathematics and Combinatorics, Cograph, Split graph, Graph isomorphism, Robustness, Mathematics, Hamming graphs, Discrete mathematics, G-graphs, Clique-sum, Applied Mathematics, Modular decomposition, Vertex and edge-transitivity, Clique graphs
Abstract: International audience; Given a finite group and a set S ⊂ G, we consider the different cosets of each cyclic group with s ∈ S. Then the G-graph Φ (G,S) associated with G and S can be defined as the intersection graph of all these cosets. These graphs were introduced in Bretto and Faisant (2005) as an alternative to Cayley graphs: they still have strong regular properties but a more flexible structure. We investigate here some of their robustness properties (connectivity and vertex/edge-transitivity) recognized as important issues in the domain of network design. In particular, we exhibit some cases where G-graphs are optimally connected, i.e. their edge and vertex-connectivity are both equal to the minimum degree. Our main result concerns the case of a G-graph associated with an abelian group and its canonical base S, which is shown to be optimally connected. We also provide a combinatorial characterization for this class as clique graphs of Cartesian products of complete graphs and we show that it can be recognized in polynomial time. These results motivate future researches in two main directions: revealing new classes of optimally connected G-graphs and investigating the complexity of their recognition.
Published: 2015

40. Observability in Connected Strongly Regular Graphs and Distance Regular Graphs

Author: Christian Commault, Alain Y. Kibangou, Networked Controlled Systems (NECS), Département Automatique (GIPSA-DA), Grenoble Images Parole Signal Automatique (GIPSA-lab), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Grenoble Images Parole Signal Automatique (GIPSA-lab), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), GIPSA - Systèmes linéaires et robustesse (GIPSA-SLR), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Stendhal - Grenoble 3-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Département Automatique (GIPSA-DA), Université Stendhal - Grenoble 3-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Stendhal - Grenoble 3-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Grenoble Images Parole Signal Automatique (GIPSA-lab), and Université Stendhal - Grenoble 3-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Stendhal - Grenoble 3-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)
Subjects: 0209 industrial biotechnology, Control and Optimization, Observability, Computer Networks and Communications, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], 02 engineering and technology, Graph, law.invention, [SPI.AUTO]Engineering Sciences [physics]/Automatic, Combinatorics, 020901 industrial engineering & automation, Pathwidth, law, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, Line graph, 0202 electrical engineering, electronic engineering, information engineering, Nul- lity of graphs, Networked systems, Cograph, Pancyclic graph, Mathematics, Discrete mathematics, Bipartite graph, Strongly regular graph, Distance regular graphs, 020206 networking & telecommunications, Association scheme, 1-planar graph, Consensus networks, Strongly regular graphs, Control and Systems Engineering, [INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA], Signal Processing, Triangle-free graph
Abstract: International audience; This paper concerns the study of observability in consensus networks modeled with strongly regular graphs or distance regular graphs. We first give a Kalman-like simple algebraic criterion for observability in distance regular graphs. This criterion consists in evaluating the rank of a matrix built with the components of the Bose-Mesner algebra associated with the considered graph. Then, we define some bipartite graphs that capture the observability properties of the graph to be studied. In particular, we show that necessary and sufficient observability conditions are given by the nullity of the so-called local bipartite observability graph (resp. local unfolded bipartite observability graph) for strongly regular graphs (resp. distance regular graphs). When the nullity cannot be derived directly from the structure of these bipartite graphs, the rank of the associated bi-adjacency matrix allows evaluating observability. Eventually, as a by-product of the main results we show that non-observability can be stated just by comparing the valency of the graph to be studied with a bound computed from the number of vertices of the graph and its diameter. Similarly nonobservability can also be stated by evaluating the size of the maximum matching in the above mentioned bipartite graphs.
Published: 2014

41. Intersection Graphs of L-Shapes and Segments in the Plane

Author: Torsten Ueckerdt, George B. Mertzios, Kolja Knauer, Stefan Felsner, Discrete Mathematics [Berlin], Institut für Mathematik [Berlin], Technische Universität Berlin (TU)-Technische Universität Berlin (TU), Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Algorithmique, Combinatoire et Recherche Opérationnelle (ACRO), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), School of Engineering and Computing Sciences, Durham University, Karlsruhe Institute of Technology (KIT), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), Csuhaj-Varjú, Erzsébet, Dietzfelbinger, Martin, Ésik, Zoltán, 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), Technical University of Berlin / Technische Universität Berlin (TU)-Technical University of Berlin / Technische Universität Berlin (TU), and Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Vertex (graph theory), Intersection graphs, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Computer Science::Computational Geometry, 01 natural sciences, law.invention, Combinatorics, Indifference graph, symbols.namesake, Pathwidth, Computer Science::Discrete Mathematics, Chordal graph, law, Outerplanar graph, Line graph, planar 3-trees, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, [INFO]Computer Science [cs], segment graphs, ComputingMilieux_MISCELLANEOUS, Mathematics, co-planar graphs, Discrete mathematics, Block graph, Book embedding, Mathematics::Combinatorics, Co-planar graphs, Planar 3-trees, Applied Mathematics, 1-planar graph, k-bend VPG-graphs, intersection graphs, Longest path problem, Planar graph, k- bend VPG-graphs, 010201 computation theory & mathematics, Segment graphs, symbols, 020201 artificial intelligence & image processing, Combinatorics (math.CO)
Abstract: An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: L, \Gamma, LE{} and \eeG. A $k$-bend path is a simple path in the plane, whose direction changes $k$ times from horizontal to vertical. If a graph admits an intersection representation in which every vertex is represented by an L, an L{} or \Gamma, a $k$-bend path, or a segment, then this graph is called an $\{L\}$-graph, $\{L,\Gamma\}$-graph, $B_k$-VPG-graph or SEG-graph, respectively. Motivated by a theorem of Middendorf and Pfeiffer [Discrete Mathematics, 108(1):365--372, 1992], stating that every $\{L,\Gamma\}$-graph is a SEG-graph, we investigate several known subclasses of SEG-graphs and show that they are $\{L\}$-graphs, or $B_k$-VPG-graphs for some small constant $k$. We show that all planar $3$-trees, all line graphs of planar graphs, and all full subdivisions of planar graphs are $\{L\}$-graphs. Furthermore we show that all complements of planar graphs are $B_{17}$-VPG-graphs and all complements of full subdivisions are $B_2$-VPG-graphs. Here a full subdivision is a graph in which each edge is subdivided at least once., Comment: 15 pages, 8 figures, (improved Thm. 4)
Published: 2014

42. Conceptual Graphs are Also Graphs

Author: Marie-Laure Mugnier, Michel Chein, Graphs for Inferences on Knowledge (GRAPHIK), 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)-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), Madalina Croitoru, and Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Inria Sophia Antipolis - Méditerranée (CRISAM)
Subjects: Artyifical Intelligence, Theoretical computer science, Computer science, Comparability graph, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, law.invention, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Morphism, Pathwidth, ACM: H.: Information Systems, law, Algorithmics, Clique-width, Line graph, 0202 electrical engineering, electronic engineering, information engineering, Graph property, Equivalence (measure theory), Constraint satisfaction problem, Complement graph, Universal graph, Forbidden graph characterization, Discrete mathematics, Graph rewriting, Null model, Voltage graph, Graph theory, Graph, Mathematical theory, Vertex-transitive graph, 010201 computation theory & mathematics, Constraint graph, Conceptual graph, Topological graph theory, Graph (abstract data type), Conceptual Graphs, 020201 artificial intelligence & image processing, Null graph, Graphs, Graph product, Moral graph
Abstract: International audience; The main objective of this paper is to add one more brick in building the CG model as a knowledge representation model autonomous from logic. The CG model is not only a graphical representation of logic, it is much more: it is a declarative model encoding knowledge in a mathematical theory, namely labelled graph theory, which has efficient computable forms, with a fundamental graph operation on the encodings to do reasoning, projection, which is a labelled graph morphism. Main topics of this paper are: a generalized formalism for simple CGs; a strong equivalence between CSP (Constraint Satisfaction Problem) and labelled graph morphism. This correspondence allows the transportation of efficient algorithms from one domain to the other, and confirms that projection —or more generally labelled graph morphism— firmly moors CGs to combinatorial algorithmics, which is a cornerstone of computer science. The usual sound and complete first order logic semantics for CGs is still valid for our generalized model. This, plus the ease of doing important reasonings with CGs —for instance plausible reasonings by using some maximal join operations— without, at least for the moment, logical semantics, strengthens our belief that CGs must also be studied and developed independently from logic.
Published: 2014

43. Co-TT graphs and a characterization of split co-TT graphs

Author: Martin Charles Golumbic, Vincent Limouzy, Nirit Lefel Weingarten, Department of Computer Science [Haifa], University of Haifa [Haifa], Caesarea Rothschild Institute and Department of Computer Science, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), and Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])
Subjects: Discrete mathematics, Applied Mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Trapezoid graph, Metric dimension, Combinatorics, Indifference graph, Pathwidth, Chordal graph, Discrete Mathematics and Combinatorics, Cograph, Maximal independent set, Split graph, ComputingMilieux_MISCELLANEOUS, Mathematics
Abstract: In this paper, we present a new characterization of complement Threshold Tolerance graphs (co-TT for short) and find a recognition algorithm for the subclass of split co-TT graphs running in O(n^2) time. Currently, the best recognition algorithms for co-TT graphs and for split co-TT graphs run in O(n^4) time (Hammer and Simeone (1981) [4]; Monma et al. (1988) [7]).
Published: 2014

44. Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth

Author: David Coudert, Dorian Mazauric, Nicolas Nisse, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), INRIA, Inria Associated team AlDyNet, European Project: 258307,EC:FP7:ICT,FP7-ICT-2009-5,EULER(2010), 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), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Inria Chile, Universidad Diego Portales [Santiago] (UDP)-Universidad de la frontera [Chile]-Pontificia Universidad Católica de Chile (UC)-Institut National de Recherche en Informatique et en Automatique (Inria)-Pontificia Universidad Católica de Valparaíso (PUCV)-Universidad Adolfo Ibáñez [Santiago]-Universidad de Valparaiso [Chile]-Universidad Tecnica Federico Santa Maria [Valparaiso] (UTFSM)-Universidad de Concepción - University of Concepcion [Chile], associated Inria team AlDyNet, project ECOS-Sud Chile, Universidad de Valparaiso [Chile]-Universidad Tecnica Federico Santa Maria [Valparaiso] (UTFSM)-Universidad Adolfo Ibáñez [Santiago]-Pontificia Universidad Católica de Valparaíso (PUCV)-Institut National de Recherche en Informatique et en Automatique (Inria)-Pontificia Universidad Católica de Chile (UC)-Universidad de Concepción [Chile]-Universidad de la frontera [Chile]-Universidad Diego Portales [Santiago] (UDP), and Universidad Diego Portales [Santiago] (UDP)-Universidad de la frontera [Chile]-Universidad de Concepción [Chile]-Pontificia Universidad Católica de Chile (UC)-Institut National de Recherche en Informatique et en Automatique (Inria)-Pontificia Universidad Católica de Valparaíso (PUCV)-Universidad Adolfo Ibáñez [Santiago]-Universidad de Valparaiso [Chile]-Universidad Tecnica Federico Santa Maria [Valparaiso] (UTFSM)
Subjects: Discrete mathematics, Branch and bound, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Pathwidth, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Sage, Graph, Combinatorics, Dynamic programming, Indifference graph, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Exact algorithm, Bounded function, branch-and-bound, Undirected graph, vertex-separation, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics
Abstract: It is well known that many NP-hard problems are tractable in the class of bounded pathwidth graphs. In particular, path-decompositions of graphs are an important ingredient of dynamic programming algorithms for solving such problems. Therefore, computing the pathwidth and associated path-decomposition of graphs has both a theoretical and practical interest. In this paper, we design a Branch and Bound algorithm that computes the exact pathwidth of graphs and a corresponding path-decomposition. Our main contribution consists of several non-trivial techniques to reduce the size of the input graph (pre-processing) and to cut the exploration space during the search phase of the algorithm. We evaluate experimentally our algorithm by comparing it to existing algorithms of the literature. It appears from the simulations that our algorithm offers a significative gain with respect to previous work. In particular, it is able to compute the exact pathwidth of any graph with less than 60 nodes in a reasonable running-time (≤ 10 min.). Moreover, our algorithm also achieves good performance when used as a heuristic (i.e., when returning best result found within bounded time-limit). Our algorithm is not restricted to undirected graphs since it actually computes the vertex-separation of digraphs (which coincides with the pathwidth in case of undirected graphs).; Les décompositions en chemin de graphes sont très importants pour la conception d'algorithmes de programmation dynamique pour résoudre de nombreux problèmes NP-difficiles. Calculer la pathwidth et la décomposition en chemin correspondante sont donc d'un grand intérêt tant d'un point de vue théorique que pratique. Dans ce papier, nous proposons un algorithme de Branch and Bound qui calcule la pathwidth et une décomposition. Notre contribution principale réside dans les techniques que nous prouvons pour réduire la taille du graphe donné en entrée (pré- traitement) et réduire la taille de l'espace d'exploration de la phase de recherche de l'algorithme. Nous évaluons expérimentalement notre algorithme en le comparant aux algorithmes proposés dans la littérature. Les simulations montrent que notre algorithme apporte un gain significatif par rapport aux algorithmes existants. Il est capable de calculer la valeur exacte de la pathwidth de tout graphe composé d'au plus 60 sommets en un temps raisonnable (moins de 10 minutes). De plus, notre algorithme montre de bonnes performances lorsqu'il est utilisé en heuristique (c'est-à-dire lorsqu'il retourne le meilleur résultat trouvé en un temps donné). Notre algorithme n'est pas spécifique au graphes non orientés car il permet de calculer la vertex-separation des digraphes (qui coïncide avec la pathwidth dans le cas des graphes non orientés).
Published: 2014

45. Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs

Author: Laurent Massoulié, Charles Bordenave, Marc Lelarge, Institut de Mathématiques de Toulouse UMR5219 (IMT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Laboratory of Information, Network and Communication Sciences (LINCS), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT), Dynamics of Geometric Networks (DYOGENE), 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)-É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)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'informatique de l'école normale supérieure (LIENS), 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), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), INFormation NEtworks (INFINE), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Microsoft Research - Inria Joint Centre (MSR - INRIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Microsoft Research Laboratory Cambridge-Microsoft Corporation [Redmond, Wash.], 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)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Social and Information Networks (cs.SI), FOS: Computer and information sciences, Random graph, Discrete mathematics, Block graph, Probability (math.PR), Computer Science - Social and Information Networks, Ihara zeta function, 05C80, 05C50, 91D30, law.invention, Combinatorics, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Indifference graph, Pathwidth, Chordal graph, law, Line graph, Random regular graph, FOS: Mathematics, Ramanujan graphs, [INFO]Computer Science [cs], Stochastic Block Model, Mathematics - Probability, non-backtracking matrix, Mathematics
Abstract: A non-backtracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The non-backtracking matrix of a graph is indexed by its directed edges and can be used to count non-backtracking walks of a given length. It has been used recently in the context of community detection and has appeared previously in connection with the Ihara zeta function and in some generalizations of Ramanujan graphs. In this work, we study the largest eigenvalues of the non-backtracking matrix of the Erdos-Renyi random graph and of the Stochastic Block Model in the regime where the number of edges is proportional to the number of vertices. Our results confirm the "spectral redemption" conjecture that community detection can be made on the basis of the leading eigenvectors above the feasibility threshold., Comment: 59 pages
Published: 2014

46. Computing H-Joins with Application to 2-Modular Decomposition

Author: Antoine Mamcarz, Fabien de Montgolfier, Michel Habib, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 01 natural sciences, Graph, Combinatorics, Pathwidth, Graph power, Cograph, 0101 mathematics, Complement graph, Graph decompositions, Mathematics, Discrete mathematics, Applied Mathematics, 010102 general mathematics, Neighbourhood (graph theory), H-Join, 16. Peace & justice, Computer Science Applications, Modular decomposition, Homogeneous pairs, 010201 computation theory & mathematics, Bipartite graph, Bound graph, Algorithms
Abstract: International audience; We present here a general framework to design algorithms that compute H-join. For a given bipartite graph H, we say that a graph G admits a H-join decomposition or simply a H-join, if the vertices of G can be partitioned in |H| parts connected as in H. This graph H is a kind of pattern, that we want to discover in G. This framework allows us to present fastest known algorithms for the computation of P 4-join (aka N-join), P 5-join (aka W-join), C 6-join (aka 6-join). We also generalize this method to find a homogeneous pair (also known as 2-module), a pair {M 1,M 2} such that for every vertex x∉(M 1∪M 2) and i∈{1,2}, x is either adjacent to all vertices in M i or to none of them. First used in the context of perfect graphs (Chvátal and Sbihi in Graphs Comb. 3:127-139, 1987), it is a generalization of splits (a.k.a. 1-joins) and of modules. The algorithmics to compute them appears quite involved. In this paper, we describe an O(mn 2)-time algorithm computing all maximal homogeneous pairs of a graph, which not only improves a previous bound of O(mn 3) for finding only one pair (Everett et al. in Discrete Appl. Math. 72:209-218, 1997), but also uses a nice structural property of homogenous pairs, allowing to compute a canonical decomposition tree for sesquiprime graphs (i.e., graphs G having no module and such that for every vertex v∈G, G−v also has no module).
Published: 2014

47. Practical and Efficient Circle Graph Recognition

Author: Derek G. Corneil, Christophe Paul, Marc Tedder, Emeric Gioan, 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), Department of Computer Science [University of Toronto] (DCS), and University of Toronto
Subjects: FOS: Computer and information sciences, Discrete Mathematics (cs.DM), General Computer Science, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, law.invention, Combinatorics, Indifference graph, Pathwidth, Chordal graph, law, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), 0101 mathematics, Mathematics, Discrete mathematics, Applied Mathematics, 010102 general mathematics, Interval graph, Midpoint circle algorithm, Computer Science Applications, Modular decomposition, 010201 computation theory & mathematics, Circle graph, Computer Science - Discrete Mathematics, Circle packing theorem, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; Circle graphs are the intersection graphs of chords in a circle. This paper presents the first sub-quadratic recognition algorithm for the class of circle graphs. Our algorithm is O(n + m) times the inverse Ackermann function, α(n + m), whose value is smaller than 4 for any practical graph. The algorithm is based on a new in- cremental Lexicographic Breadth-First Search characterization of circle graphs, and a new efficient data-structure for circle graphs, both developed in the paper. The al- gorithm is an extension of a Split Decomposition algorithm with the same running time developed by the authors in a companion paper.
Published: 2014

48. Linear Rank-Width of Distance-Hereditary Graphs

Author: O-joung Kwon, Mamadou Moustapha Kanté, Isolde Adler, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), and Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS)
Subjects: Discrete mathematics, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Canonical decomposition, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 1-planar graph, Graph, Combinatorics, Indifference graph, Pathwidth, Chordal graph, Maximal independent set, Time complexity, Mathematics
Abstract: We present a characterization of the linear rank-width of distance-hereditary graphs. Using the characterization, we show that the linear rank-width of every $n$-vertex distance-hereditary graph can be computed in time $\mathcal {O}(n^2\cdot \log (n))$, and a linear layout witnessing the linear rank-width can be computed with the same time complexity. For our characterization, we combine modifications of canonical split decompositions with an idea of [Megiddo, Hakimi, Garey, Johnson, Papadimitriou: The complexity of searching a graph. JACM 1988], used for computing the path-width of trees. We also provide a set of distance-hereditary graphs which contains the set of distance-hereditary vertex-minor obstructions for linear rank-width. The set given in [Jeong, Kwon, Oum: Excluded vertex-minors for graphs of linear rank-width at most k. STACS 2013: 221–232] is a subset of our obstruction set.
Published: 2014

49. The minimum restricted edge-connected graph and the minimum size of graphs with a given edge–degree

Author: Yingzhi Tian, Hengzhe Li, Xiaofeng Guo, Hao Li, Weihua Yang, Department of Mathematics [Taiyuan], Taiyuan University of Technology, College of Mathematics and System Sciences, Xinjiang University, Urumqi, Xinjiang 830046, China, College of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, China, Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), and School of Mathematical Science, Xiamen University, Xiamen, Fujian, 361005, China
Subjects: Discrete mathematics, Applied Mathematics, Symmetric graph, 16. Peace & justice, 1-planar graph, law.invention, Combinatorics, Indifference graph, Pathwidth, law, Chordal graph, Partial k-tree, Line graph, Discrete Mathematics and Combinatorics, [MATH]Mathematics [math], Pancyclic graph, Mathematics
Abstract: International audience; Let $G=(V(G),E(G))$ be a graph. Determining the minimum and/or maximum size $(|E(G)|)$ of graphs with some given parameters is a classic extremal problem in graph theory. For a graph $G$ and $e=uv∈E(G)$, we denote $d(e)=d(u)+d(v)−2$ the edge–degree of $e$. In this paper, we obtain a lower bound for the minimum size of graphs with a given order $n$, a given minimum degree $\delta$ and a given minimum edge–degree $2\delta+k−2$. Moreover, we characterize the extremal graphs for $k=0,1,2$. As an application, we characterize some kinds of minimum restricted edge connected graphs.
Published: 2014

50. Exclusive Graph Searching vs. Pathwidth

Author: Markou, Euripides, Nisse, Nicolas, Pérennes, Stéphane, Department of Computer Science & Biomedical Informatics [Galaneika], University of Thessaly [Volos] (UTH), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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, Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], graph searching, computational complexity, pathwidth, exclusivity property, monotone strategies
Abstract: In Graph Searching, a team of searchers aims at capturing an invisible fugitive moving arbitrarily fast in a graph. Equivalently, the searchers try to clear a contaminated network.The problem is to compute the minimum number of searchers required to accomplish this task. Several variants of Graph Searching have been studied mainly because of their close relationship with the pathwidth of a graph. Blin et al. defined the Exclusive Graph Searching where searchers cannot "jump" and no node can be occupied by more than one searcher. In this paper, we study the complexity of this new variant. We show that the problem is NP-hard in planar graphs with maximum degree 3 and it can be solved in linear-time in the class of cographs. We also show that monotone Exclusive Graph Searching is NP-complete in split graphs where Pathwidth is known to be solvable in polynomial time. Moreover, we prove that monotone Exclusive Graph Searching is in P in a subclass of star-like graphs where Pathwidth is known to be NP-hard. Hence, the computational complexities of monotone Exclusive Graph Searching and Pathwidth cannot be compared. This is the first variant of Graph Searching for which such a difference is proved.; Dans les jeux de capture (Graph Searching), une équipe d'agents doit capturer un fugitif invisible se déplaçant rapidement dans un graphe. De façon équivalente, les agents doivent nettoyer un réseau contaminé. Le problème est de calculer le nombre minimum d'agents nécessaires pour accomplir cette tache. Plusieurs variantes de ces jeux ont été étudiés pour leur lien avec la pathwidth des graphes. Blin et al. ont défini le jeu de capture exclusif dans lequel les agents ne peuvent ni "sauter", ni occuper un sommet à plusieurs. Dans ce rapport, nous étudions la complexité de cette nouvelle variante. Nous montrons que le problème est NP-difficile dans les graphes planaires avec degré au plus 3 et qu'il peut être résolu en temps linéaire dans la classe des cographes. Nous montrons également que la variante monotone du jeu exclusif est NP-complet dans la classe des split-graphes où la pathwidth est NP-complet. De plus, nous prouvons que le jeu exclusif monotone peut être calculé en temps polynomial dans une classe de star-like graphes où calculer la pathwidth est NP-complet. Les complexités de la pathwidth et du jeu de capture exclusif monotone ne peuvent donc être comparées. Il s'agit de la première variante de jeu de capture où une telle différence est avérée
Published: 2014

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

Database

168 results on '"Pathwidth"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources