39 results on '"Pathwidth"'
Search Results
2. Recent Advances in Positive-Instance Driven Graph Searching
- Author
-
Max Bannach and Sebastian Berndt
- Subjects
treewidth ,pathwidth ,treedepth ,graph searching ,positive-instance driven ,color coding ,Industrial engineering. Management engineering ,T55.4-60.8 ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
Research on the similarity of a graph to being a tree—called the treewidth of the graph—has seen an enormous rise within the last decade, but a practically fast algorithm for this task has been discovered only recently by Tamaki (ESA 2017). It is based on dynamic programming and makes use of the fact that the number of positive subinstances is typically substantially smaller than the number of all subinstances. Algorithms producing only such subinstances are called positive-instance driven (PID). The parameter treedepth has a similar story. It was popularized through the graph sparsity project and is theoretically well understood—but the first practical algorithm was discovered only recently by Trimble (IPEC 2020) and is based on the same paradigm. We give an alternative and unifying view on such algorithms from the perspective of the corresponding configuration graphs in certain two-player games. This results in a single algorithm that can compute a wide range of important graph parameters such as treewidth, pathwidth, and treedepth. We complement this algorithm with a novel randomized data structure that accelerates the enumeration of subproblems in positive-instance driven algorithms.
- Published
- 2022
- Full Text
- View/download PDF
3. Finding small-width connected path decompositions in polynomial time.
- Author
-
Dereniowski, Dariusz, Osula, Dorota, and Rzążewski, Paweł
- Subjects
- *
POLYNOMIAL time algorithms , *GRAPH connectivity , *OPEN-ended questions - Abstract
A connected path decomposition of a simple graph G is a path decomposition (X 1 , ... , X l) such that the subgraph of G induced by X 1 ∪ ⋯ ∪ X i is connected for each i ∈ { 1 , ... , l }. The connected pathwidth of G is then the minimum width over all connected path decompositions of G. We prove that for each fixed k , the connected pathwidth of any input graph can be computed in polynomial-time. This answers an open question raised by Fedor V. Fomin during the GRASTA 2017 workshop, since connected pathwidth is equivalent to the connected (monotone) node search game. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
4. On Tradeoffs Between Width- and Fill-like Graph Parameters.
- Author
-
Dereniowski, Dariusz and Stański, Adam
- Subjects
- *
INTEGERS , *CONVEX bodies , *EDGES (Geometry) - Abstract
In this work we consider two two-criteria optimization problems: given an input graph, the goal is to find its interval (or chordal) supergraph that minimizes the number of edges and its clique number simultaneously. For the interval supergraph, the problem can be restated as simultaneous minimization of the path width pw(G) and the profile p(G) of the input graph G. We prove that for an arbitrary graph G and an integer t ∈ {1, ... , pw(G) + 1}, there exists an interval supergraph G′ of G such that for its clique number it holds ω (G ′) ≤ (1 + 2 t) (pw (G) + 1) and the number of its edges is bounded by |E(G′)| ≤ (t + 2)p(G). In other words, the pathwidth and the profile of a graph can be simultaneously minimized within the factors of 1 + 2 t (plus a small constant) and t + 2, respectively. Note that for a fixed t, both upper bounds provide constant factor approximations. On the negative side, we show an example that proves that, for some graphs, there is no solution in which both parameters are optimal. In case of finding a chordal supergraph, the two corresponding graph parameters that reflect its clique size and number of edges are the treewidth and fill-in. We obtain that the treewidth and the fill-in problems are also 'orthogonal' in the sense that for some graphs, a solution that minimizes one of those parameters cannot minimize the other. As a motivating example, we recall graph searching games which illustrates a need of simultaneous minimization of these pairs of graph parameters. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
5. Bounding the Search Number of Graph Products.
- Author
-
CLARKE, NANCY ELLEN, MESSINGER, MARGARET-ELLEN, and POWER, GRACE
- Subjects
- *
MANUFACTURED products - Abstract
In this paper, we provide results for the search number of the Cartesian product of graphs. We consider graphs on opposing ends of the spectrum: paths and cliques. Our main result determines the pathwidth of the product of cliques and provides a lower bound for the search number of the product of cliques. A consequence of this result is a bound for the search number of the product of arbitrary graphs G and H based on their respective clique numbers. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
6. Pathwidth and Searching in Parameterized Threshold Graphs
- Author
-
Krishna, D. Sai, Reddy, T. V. Thirumala, Shashank, B. Sai, Rangan, C. Pandu, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Rahman, Md. Saidur, editor, and Fujita, Satoshi, editor
- Published
- 2010
- Full Text
- View/download PDF
7. Monotony Properties of Connected Visible Graph Searching
- Author
-
Fraigniaud, Pierre, Nisse, Nicolas, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Fomin, Fedor V., editor
- Published
- 2006
- Full Text
- View/download PDF
8. Nondeterministic Graph Searching: From Pathwidth to Treewidth
- Author
-
Fomin, Fedor V., Fraigniaud, Pierre, Nisse, Nicolas, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Jȩdrzejowicz, Joanna, editor, and Szepietowski, Andrzej, editor
- Published
- 2005
- Full Text
- View/download PDF
9. Computing Small Search Numbers in Linear Time
- Author
-
Bodlaender, Hans L., Thilikos, Dimitrios M., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Downey, Rod, editor, Fellows, Michael, editor, and Dehne, Frank, editor
- Published
- 2004
- Full Text
- View/download PDF
10. Exclusive Graph Searching.
- Author
-
Blin, Lélia, Burman, Janna, and Nisse, Nicolas
- Subjects
- *
GRAPH theory , *SEARCH algorithms , *MONOTONIC functions , *POLYNOMIAL time algorithms , *INTEGERS - Abstract
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. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
11. Exclusive graph searching vs. pathwidth.
- Author
-
Markou, Euripides, Nisse, Nicolas, and Pérennes, Stéphane
- Subjects
- *
GRAPH theory , *MONOTONE operators , *COMPUTATIONAL complexity , *POLYNOMIAL time algorithms , *COMPLETENESS theorem - 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. In this paper, we study the complexity of the Exclusive Graph Searching variant. We show that the problem is NP-hard in planar graphs 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. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
12. Connected Search for a Lazy Robber
- Author
-
Isolde Adler, Christophe Paul, Dimitrios M. Thilikos, School of Computing [Leeds], University of Leeds, 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), Arkadev Chattopadhyay, Paul Gastin, ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016), and ANR-17-CE23-0010,ESIGMA,Efficacité et structure pour les applications de la fouille de graphes(2017)
- Subjects
Class (set theory) ,Computer Science::Computer Science and Game Theory ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Obstructions ,0102 computer and information sciences ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,01 natural sciences ,Combinatorics ,Set (abstract data type) ,Computer Science::Robotics ,Pathwidth ,Computer Science::Discrete Mathematics ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,Discrete Mathematics and Combinatorics ,Tree-decomposition ,0101 mathematics ,ComputingMilieux_MISCELLANEOUS ,Mathematics ,Graph searching ,000 Computer science, knowledge, general works ,010102 general mathematics ,Tree (graph theory) ,Treewidth ,Search game ,Monotone polygon ,010201 computation theory & mathematics ,Bounded function ,Computer Science ,Geometry and Topology - Abstract
International audience; The node search game against a lazy (or, respectively, agile) invisible robber has been introduced as a search-game analogue of the treewidth parameter (and, respectively, pathwidth). In the \emph{connected} variants of the above two games, we additionally demand that, at each moment of the search, the \emph{clean} territories are {\sl connected}. The connected search game against an agile and invisible robberhas been extensively examined. The monotone variant (where we also demand that the clean territories are progressively increasing) of this game, corresponds to the graph parameter of {\sl connected pathwidth}. It is known that \emph{the price of connectivtiy} to search for an agile robber is bounded by $2$, that is the connected pathwidth of a graph is at most twice (plus some constant) its pathwidth.In this paper, we investigate the study of the connected search game against a {\sl lazy} robber. A lazy robber moves only when the searchers' strategy threatens the location that he currently occupies. We introduce two alternative graph-theoretical formulations of this game, one in terms of connected tree decompositions, and one in terms of (connected) layouts, leading to the graph parameter of {\sl connected treewidth}. We observe that connected treewidth parameter is closed under contractions and prove that for every $k\geq 2$, the set of contraction obstructions of the class of graphs with connected treewidth at most $k$ is infinite.Our main result is a complete characterisation of the obstruction set for $k=2$. One may observe that, so far, only a few complete obstruction sets are explicity known for contraction closed graph classes.We finally show that, in contrast to the agile robber game, the price of connectivity is unbounded.
- Published
- 2021
13. The complexity of minimum-length path decompositions.
- Author
-
Dereniowski, Dariusz, Kubiak, Wieslaw, and Zwols, Yori
- Subjects
- *
COMPUTATIONAL complexity , *PATHS & cycles in graph theory , *MATHEMATICAL decomposition , *GENERALIZATION , *GRAPH theory - Abstract
We consider a bicriterion generalization of the pathwidth problem: given integers k , l and a graph G , does there exist a path decomposition of G of width at most k and length (i.e., number of bags) at most l ? We provide a complete complexity classification of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter tractable with respect to k , the generalized problem is NP-complete for any fixed k ≥ 4 , and also for any fixed l ≥ 2 . On the other hand, we give a polynomial-time algorithm that constructs a minimum-length path decomposition of width at most k ≤ 3 for any disconnected input graph. As a by-product, we obtain an almost complete classification for connected graphs: the problem is NP-complete for any fixed k ≥ 5 , and polynomial for any k ≤ 3 . [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
14. Non-deterministic graph searching in trees.
- Author
-
Amini, Omid, Coudert, David, and Nisse, Nicolas
- Subjects
- *
TREE graphs , *SEARCH algorithms , *PARAMETER estimation , *LINEAR systems , *POLYNOMIALS - Abstract
Non-deterministic graph searching was introduced by Fomin et al. to provide a unified approach for pathwidth, treewidth, and their interpretations in terms of graph searching games. Given q ≥ 0 , the q -limited search number, s q ( G ) , of a graph G is the smallest number of searchers required to capture an invisible fugitive in G , when the searchers are allowed to know the position of the fugitive at most q times. The search parameter s 0 ( G ) corresponds to the pathwidth of a graph G , and s ∞ ( G ) to its treewidth. Determining s q ( G ) is NP-complete for any fixed q ≥ 0 in general graphs and s 0 ( T ) can be computed in linear time in trees, however the complexity of the problem on trees has been unknown for any q > 0 . We introduce a new variant of graph searching called restricted non-deterministic. The corresponding parameter is denoted by rs q and is shown to be equal to the non-deterministic graph searching parameter s q for q = 0 , 1 , and at most twice s q for any q ≥ 2 (for any graph G ). Our main result is a polynomial time algorithm that computes rs q ( T ) for any tree T and any q ≥ 0 . This provides a 2-approximation of s q ( T ) for any tree T , and shows that the decision problem associated to s 1 is polynomial in the class of trees. Our proofs are based on a new decomposition technique for trees which might be of independent interest. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
15. Zero-visibility cops and robber and the pathwidth of a graph.
- Author
-
Dereniowski, Dariusz, Dyer, Danny, Tifenbach, Ryan, and Yang, Boting
- Abstract
We examine the zero-visibility cops and robber graph searching model, which differs from the classical cops and robber game in one way: the robber is invisible. We show that this model is not monotonic. We show that the zero-visibility copnumber of a graph is bounded above by its pathwidth and cannot be bounded below by any nontrivial function of the pathwidth. As well, we define a monotonic version of this game and show that the monotonic zero-visibility copnumber can be bounded both above and below by positive multiples of the pathwidth. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
16. Recent Advances in Positive-Instance Driven Graph Searching
- Author
-
Sebastian Berndt and Max Bannach
- Subjects
Computational Mathematics ,Numerical Analysis ,Computational Theory and Mathematics ,treewidth ,pathwidth ,treedepth ,graph searching ,positive-instance driven ,color coding ,Theoretical Computer Science - Abstract
Research on the similarity of a graph to being a tree—called the treewidth of the graph—has seen an enormous rise within the last decade, but a practically fast algorithm for this task has been discovered only recently by Tamaki (ESA 2017). It is based on dynamic programming and makes use of the fact that the number of positive subinstances is typically substantially smaller than the number of all subinstances. Algorithms producing only such subinstances are called positive-instance driven (PID). The parameter treedepth has a similar story. It was popularized through the graph sparsity project and is theoretically well understood—but the first practical algorithm was discovered only recently by Trimble (IPEC 2020) and is based on the same paradigm. We give an alternative and unifying view on such algorithms from the perspective of the corresponding configuration graphs in certain two-player games. This results in a single algorithm that can compute a wide range of important graph parameters such as treewidth, pathwidth, and treedepth. We complement this algorithm with a novel randomized data structure that accelerates the enumeration of subproblems in positive-instance driven algorithms.
- Published
- 2022
17. A linear fixed parameter tractable algorithm for connected pathwidth
- Author
-
Kanté, Mamadou Moustapha, Paul, Christophe, Thilikos, Dimitrios M., Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), 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), Fabrizio Grandoni, Grzegorz Herman, Peter Sanders, ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016), ANR-17-CE23-0010,ESIGMA,Efficacité et structure pour les applications de la fouille de graphes(2017), ANR-18-CE40-0025,ASSK,Algorithmes avec décomposition moins connu: graphes et matroids(2018), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), ANR-20-CE92-0027,UTMA,Théories Unifiantes dans les Algorithmes Multivarieés(2020), 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 Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
FOS: Computer and information sciences ,Mathematics of computing → Graph theory ,General Mathematics ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Pathwidth ,G.2.2 ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Typical sequences ,Graph theory ,Theory of computation → Fixed parameter tractability ,Parameterized algorithms ,Theory of computation → Graph algorithms analysis ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,Computer Science - Data Structures and Algorithms ,Cops and Robber games ,Data Structures and Algorithms (cs.DS) ,05C85 ,Width parameter ,Graph decompositions ,Graph searching - Abstract
International audience; The graph parameter of {\sl pathwidth} can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of {\sl node search} where we are given a system of tunnels (represented by a graph) that is contaminated by some infectious substance and we are looking for a search strategy that, at each step, either places a searcher on a vertex or removes a searcher from a vertex and where an edge is cleaned when both endpoints are simultaneously occupied by searchers. It was proved that the minimum number of searchers required for a successful cleaning strategy is equal to the pathwidth of the graph plus one.Two desired characteristics for a cleaning strategy is to be {\sl monotone} (no recontamination occurs) and {\sl connected} (clean territories always remain connected). Under these two demands, the number of searchers is equivalent to a variant of pathwidth called {\em connected pathwidth}. We prove that connected pathwidth is fixed parameter tractable, in particular we design a $2^{O(k^2)}\cdot n$ time algorithm that checks whether the connected pathwidth of $G$ is at most $k.$ This resolves an open question by [{\sl Dereniowski, Osula, and Rz{\k{a}}{\.{z}}ewski, Finding small-width connected path-decompositions in polynomial time. Theor. Comput. Sci., 794:85–100, 2019}\,]. For our algorithm, we enrich the {\sl typical sequence technique} that is able to deal with the connectivity demand. Typical sequences have been introduced in [{\sl Bodlaender and Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21(2):358–402, 1996}\,] for the design of linear parameterized algorithms for treewidth and pathwidth. While this technique has been later applied to other parameters, none of its advancements was able to deal with the connectivity demand, as it is a ``global’’ demand that concerns an unbounded number of parts of the graph of unbounded size. The proposed extension is based on an encoding of the connectivity property that is quite versatile and may be adapted so to deliver linear parameterized algorithms for the connected variants of other width parameters as well. An immediate consequence of our result is a $2^{O(k^2)}\cdot n$ time algorithm for the monotone and connected version of the edge search number.
- Published
- 2020
18. Recent Advances in Positive-Instance Driven Graph Searching †.
- Author
-
Bannach, Max and Berndt, Sebastian
- Subjects
- *
DATA structures , *GRAPH algorithms , *DYNAMIC programming , *TREE graphs , *CHARTS, diagrams, etc. , *COLOR codes - Abstract
Research on the similarity of a graph to being a tree—called the treewidth of the graph—has seen an enormous rise within the last decade, but a practically fast algorithm for this task has been discovered only recently by Tamaki (ESA 2017). It is based on dynamic programming and makes use of the fact that the number of positive subinstances is typically substantially smaller than the number of all subinstances. Algorithms producing only such subinstances are called positive-instance driven (PID). The parameter treedepth has a similar story. It was popularized through the graph sparsity project and is theoretically well understood—but the first practical algorithm was discovered only recently by Trimble (IPEC 2020) and is based on the same paradigm. We give an alternative and unifying view on such algorithms from the perspective of the corresponding configuration graphs in certain two-player games. This results in a single algorithm that can compute a wide range of important graph parameters such as treewidth, pathwidth, and treedepth. We complement this algorithm with a novel randomized data structure that accelerates the enumeration of subproblems in positive-instance driven algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
19. Approximate search strategies for weighted trees
- Author
-
Dereniowski, Dariusz
- Subjects
- *
TREE graphs , *GRAPH connectivity , *APPROXIMATION theory , *POLYNOMIALS , *ALGORITHMS , *PATHS & cycles in graph theory - Abstract
Abstract: The problems of (classical) searching and connected searching of weighted trees are known to be computationally hard. In this work we give a polynomial-time 3-approximation algorithm that finds a connected search strategy of a given weighted tree. This in particular yields constant factor approximation algorithms for the (non-connected) classical searching problems and for the weighted pathwidth problem for this class of graphs. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF
20. FROM PATHWIDTH TO CONNECTED PATHWIDTH.
- Author
-
DERENIOWSKI, DARIUSZ
- Subjects
- *
GRAPH theory , *MATHEMATICAL decomposition , *MATHEMATICAL inequalities , *ALGORITHMS , *MONOTONIC functions - Abstract
It is proven that the connected pathwidth of any graph G is at most 2 · pw(G)+1, where pw(G) is the pathwidth of G. The method is constructive, i.e., it yields an efficient algorithm that for a given path decomposition of width k computes a connected path decomposition of width at most 2k+1. The running time of the algorithm is O(dk²), where d is the number of "bags" in the input path decomposition. The motivation for studying connected path decompositions comes from the connection between the pathwidth and the search number of a graph. One of the advantages of the above bound for connected pathwidth is an inequality cs(G) ≤ 2s(G) + 3, where cs(G) and s(G) are the connected search number and the search number of G, respectively. Moreover, the algorithm presented in this work can be used to convert a given search strategy using k searchers into a (monotone) connected one using 2k + 3 searchers and starting at an arbitrary homebase. [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
21. A Distributed Algorithm for Computing the Node Search Number in Trees.
- Author
-
Coudert, David, Huc, Florian, and Mazauric, Dorian
- Subjects
- *
TREE graphs , *MATHEMATICAL decomposition , *DISTRIBUTED algorithms , *MATHEMATICAL analysis , *COMPUTATIONAL complexity - Abstract
We present a distributed algorithm to compute the node search number in trees. This algorithm extends the centralized algorithm proposed by Ellis et al. (Inf. Comput. 113(1):50-79, ). It can be executed in an asynchronous environment, requires an overall computation time of O( nlog n), and n messages of log n+4 bits each. The main contribution of this work lies in the data structure proposed to design our algorithm, called hierarchical decomposition. This simple and flexible data structure is used for four operations: updating the node search number after addition or deletion of any tree-edges in a distributed fashion; computing it in a tree whose edges are added sequentially and in any order; computing other graph invariants such as the process number and the edge search number, by changing only initialization rules; extending our algorithms for trees and forests of unknown size (using messages of up to 2log n+5 bits). [ABSTRACT FROM AUTHOR]
- Published
- 2012
- Full Text
- View/download PDF
22. GRAPH SEARCHING IN A CRIME WAVE.
- Author
-
Richerby, David and Thilikos, Dimitrios M.
- Subjects
- *
TREE graphs , *GRAPHIC methods , *SIMULATION methods & models , *SIMULATION games , *EQUIVALENCE relations (Set theory) , *MONOTONIC functions - Abstract
We define helicopter cops and robber games with multiple robbers, extending previous research, which considered only the pursuit of a single robber. Our model is defined for robbers that are visible (their position in the graph is known to the cops) and active (they can move at any point in the game) but is easily adapted to other variants of the single-robber game that have been considered in the literature. We show that the game with many robbers is nonmonotone: that is, fewer cops are needed if the robbers are allowed to reoccupy positions that were previously unavailable to them. As the moves of the cops depend on the position of the visible robbers, strategies for such games should be interactive, but the game becomes, in a sense, less interactive as the initial number of robbers increases. We prove that the main parameter emerging from the game, which we denote mvams(G, r), captures a hierarchy of parameters between proper pathwidth and proper treewidth, and we completely characterize it for trees, extending analogous existing characterizations of the pathwidth of trees. Moreover, we prove an upper bound for mvams(G, r) on general graphs and show that this bound is reached by an infinite class of graphs. On the other hand, if we consider the robbers to be invisible and lazy, the resulting parameters collapse in all cases to either proper pathwidth or proper treewidth, giving a further case where the classical equivalence between visible, active robbers and invisible, lazy robbers does not hold. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF
23. Monotony properties of connected visible graph searching
- Author
-
Fraigniaud, Pierre and Nisse, Nicolas
- Subjects
- *
INFORMATION science , *ELECTRONIC data processing , *GRAPHIC methods , *INFORMATION processing - Abstract
Abstract: Search games are attractive for their correspondence with classical width parameters. For instance, the invisible search number (a.k.a. node search number) of a graph is equal to its pathwidth plus 1, and the visible search number of a graph is equal to its treewidth plus 1. The connected variants of these games ask for search strategies that are connected, i.e., at every step of the strategy, the searched part of the graph induces a connected subgraph. We focus on monotone search strategies, i.e., strategies for which every node is searched exactly once. The monotone connected visible search number of an n-node graph is at most times its visible search number. First, we prove that this logarithmic bound is tight. Precisely, we prove that there is an infinite family of graphs for which the ratio monotone connected visible search number over visible search number is . Second, we prove that, as opposed to the non-connected variant of visible graph searching, “recontamination helps” for connected visible search. Precisely, we prove that, for any , there exists a graph with connected visible search number at most k, and monotone connected visible search number >k [Copyright &y& Elsevier]
- Published
- 2008
- Full Text
- View/download PDF
24. Exclusive graph searching vs. pathwidth
- Author
-
Nicolas Nisse, Euripides Markou, Stéphane Pérennes, Department of Computer Science & Biomedical Informatics [Galaneika], University of Thessaly [Volos] (UTH), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), ANR-13-BS02-0007,Stint,Structures Interdites(2013), Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
- Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,0211 other engineering and technologies ,Comparability graph ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Theoretical Computer Science ,law.invention ,Combinatorics ,graph searching ,Pathwidth ,law ,Outerplanar graph ,Line graph ,Graph minor ,Split graph ,Graph property ,Mathematics ,Discrete mathematics ,021103 operations research ,pathwidth ,Computer Science Applications ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Null graph ,MathematicsofComputing_DISCRETEMATHEMATICS ,Information Systems - Abstract
International audience; In Graph Searching, a team of searchers aims at capturing an invisible fugitive moving arbitrarily fast in a graph. Equivalently, the searchers try to clear a contaminated network. The problem is to compute the minimum number of searchers required to accomplish this task. Several variants of Graph Searching have been studied mainly because of their close relationship with the pathwidth of a graph. Blin et al. defined the Exclusive Graph Searching where searchers cannot " jump " and no node can be occupied by more than one searcher. In this paper, we study the complexity of this new variant. We show that the problem is NP-hard in planar graphs with maximum degree 3 and it can be solved in linear-time in the class of cographs. We also show that monotone Exclusive Graph Searching is NP-complete in split graphs where Pathwidth is known to be solvable in polynomial time. Moreover, we prove that monotone Exclusive Graph Searching is in P in a subclass of star-like graphs where Pathwidth is known to be NP-hard. Hence, the computational complexities of monotone Exclusive Graph Searching and Pathwidth cannot be compared. This is the first variant of Graph Searching for which such a difference is proved.
- Published
- 2017
25. Non-deterministic graph searching in trees
- Author
-
Nicolas Nisse, Omid Amini, David Coudert, Département de Mathématiques et Applications - ENS Paris (DMA), É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), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-13-BS02-0007,Stint,Structures Interdites(2013), ANR-11-LABX-0031,UCN@SOPHIA,Réseau orienté utilisateur(2011), 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), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), École normale supérieure - Paris (ENS-PSL), 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 ,General Computer Science ,Treewidth ,010102 general mathematics ,Pathwidth ,0102 computer and information sciences ,Tree-depth ,Graph Searching ,01 natural sciences ,Tree decomposition ,Trees ,Theoretical Computer Science ,Combinatorics ,[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,010201 computation theory & mathematics ,Graph power ,Clique-width ,Graph minor ,0101 mathematics ,Complement graph ,Mathematics ,Distance-hereditary graph - Abstract
International audience; Non-deterministic graph searching was introduced by Fomin et al. to provide a unified approach for pathwidth, treewidth, and their interpretations in terms of graph searching games. Given q ≥ 0, the q-limited search number, s q (G), of a graph G is the smallest number of searchers required to capture an invisible fugitive in G, when the searchers are allowed to know the position of the fugitive at most q times. The search parameter s 0 (G) corresponds to the pathwidth of a graph G, and s ∞ (G) to its treewidth. Determining s q (G) is NP-complete for any fixed q ≥ 0 in general graphs and s 0 (T) can be computed in linear time in trees, however the complexity of the problem on trees has been unknown for any q > 0. We introduce a new variant of graph searching called restricted non-deterministic. The corresponding parameter is denoted by rs q and is shown to be equal to the non-deterministic graph searching parameter s q for q = 0, 1, and at most twice s q for any q ≥ 2 (for any graph G). Our main result is a polynomial time algorithm that computes rs q (T) for any tree T and any q ≥ 0. This provides a 2-approximation of s q (T) for any tree T , and shows that the decision problem associated to s 1 is polynomial in the class of trees. Our proofs are based on a new decomposition technique for trees which might be of independent interest.
- Published
- 2015
26. Three-fast-searchable graphs
- Author
-
Danny Dyer, Öznur Yaşar Diner, Dariusz Dereniowski, and Diner, Öznur Yaşar
- Subjects
InformationSystems_INFORMATIONSTORAGEANDRETRIEVAL ,Computer Science::Human-Computer Interaction ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Edge cover ,law.invention ,Combinatorics ,Pathwidth ,Graph power ,law ,Line graph ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,Edge contraction ,Graph searching ,Mathematics ,Discrete mathematics ,Computer Science::Information Retrieval ,Applied Mathematics ,Neighbourhood (graph theory) ,Fast searching ,16. Peace & justice ,Computational complexity ,010201 computation theory & mathematics ,020201 artificial intelligence & image processing ,Feedback vertex set ,Graph factorization ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
In the edge searching problem searchers move from vertex to vertex in a graph to capture an invisible fast intruder that may occupy either vertices or edges. Fast searching is a monotonic internal model in which at every move a new edge of the graph G must be guaranteed to be free of the intruder. That is once all searchers are placed the graph G is cleared in exactly vertical bar E(G)vertical bar moves. Such a restriction obviously necessitates a larger number of searchers. We examine this model and characterize graphs for which 2 or 3 searchers are sufficient. We prove that the corresponding decision problem is NP-complete. (C) 2013 Elsevier B.V. All rights reserved.
- Published
- 2013
27. Approximate search strategies for weighted trees
- Author
-
Dariusz Dereniowski
- Subjects
Discrete mathematics ,Class (set theory) ,General Computer Science ,Node searching ,Edge searching ,Approximation algorithm ,Pathwidth ,Tree (graph theory) ,Theoretical Computer Science ,Combinatorics ,Constant factor ,Connected searching ,Graph searching ,Computer Science(all) ,Mathematics - Abstract
The problems of (classical) searching and connected searching of weighted trees are known to be computationally hard. In this work we give a polynomial-time 3-approximation algorithm that finds a connected search strategy of a given weighted tree. This in particular yields constant factor approximation algorithms for the (non-connected) classical searching problems and for the weighted pathwidth problem for this class of graphs.
- Published
- 2012
28. LIFO-search: A min–max theorem and a searching game for cycle-rank and tree-depth
- Author
-
Archontia C. Giannopoulou, Paul Hunter, Dimitrios M. Thilikos, 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 Mathematics [Athens], National and Kapodistrian University of Athens (NKUA), Department of Informatics [Bergen] (UiB), University of Bergen (UiB), Department of Computer Science [Oxford], and University of Oxford [Oxford]
- Subjects
InformationSystems_INFORMATIONSTORAGEANDRETRIEVAL ,Tree-depth ,Obstructions ,010103 numerical & computational mathematics ,0102 computer and information sciences ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,01 natural sciences ,Graph parameters ,Combinatorics ,symbols.namesake ,Pathwidth ,Cycle-rank ,Discrete Mathematics and Combinatorics ,0101 mathematics ,Min–max theorem ,Game tree ,Graph searching ,Mathematics ,Forbidden graph characterization ,Bondareva–Shapley theorem ,Discrete mathematics ,Applied Mathematics ,Pursuit–evasion games ,Planar graph ,Cycle rank ,Search game ,010201 computation theory & mathematics ,symbols - Abstract
International audience; We introduce a variant of the classic node search game called LIFO-search where searchers are assigned different numbers. The additional rule is that a searcher can be removed only if no searchers of lower rank are in the graph at that moment. We show that all common variations of the game require the same number of searchers. We then introduce the notion of (directed) shelters in (di)graphs and prove a min-max theorem implying their equivalence to the cycle-rank/tree-depth parameter in (di)graphs. As (directed) shelters provide escape strategies for the fugitive, this implies that the LIFO-search game is monotone and that the LIFO-search parameter is equivalent to the one of cycle-rank/tree-depth in (di)graphs.
- Published
- 2012
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. Edge search number of cographs
- Author
-
Rodica Mihai, Petr A. Golovach, and Pinar Heggernes
- Subjects
Discrete mathematics ,Graph classes ,Applied Mathematics ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Polynomial-time algorithm ,Edge cover ,Cographs ,Combinatorics ,Modular decomposition ,Pathwidth ,010201 computation theory & mathematics ,Clique-width ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,Permutation graph ,Edge contraction ,020201 artificial intelligence & image processing ,NP-hard problem ,Split graph ,Graph searching ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics ,Distance-hereditary graph - Abstract
We give a linear-time algorithm for computing the edge search number of cographs, thereby resolving the computational complexity of edge searching on this graph class. To achieve this we give a characterization of the edge search number of the join of two graphs. With our result, the knowledge on graph searching of cographs is now complete: node, mixed, and edge search numbers of cographs can all be computed efficiently. Furthermore, we are one step closer to computing the edge search number of permutation graphs.
- Published
- 2012
31. Nondeterministic Graph Searching: From Pathwidth to Treewidth
- Author
-
Fomin, Fedor V., Fraigniaud, Pierre, and Nisse, Nicolas
- Published
- 2009
- Full Text
- View/download PDF
32. 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
33. Algorithms and obstructions for linear-width and related search parameters
- Author
-
Dimitrios M. Thilikos
- Subjects
Graph minor ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Combinatorics ,symbols.namesake ,Pathwidth ,Partial k-tree ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,Obstruction set ,Graph searching ,Forbidden graph characterization ,Mathematics ,Discrete mathematics ,Pseudoforest ,Applied Mathematics ,Graph algorithm ,Linear width ,020206 networking & telecommunications ,1-planar graph ,Planar graph ,010201 computation theory & mathematics ,Independent set ,symbols ,Path graph ,Algorithm - Abstract
The linear-width of a graph G is defined to be the smallest integer k such that the edges of G can be arranged in a linear ordering (e1,…,er) in such a way that for every i=1,…,r−1, there are at most k vertices incident to edges that belong both to {e1,…,ei} and to {ei+1,…,er}. In this paper, we give a set of 57 graphs and prove that it is the set of the minimal forbidden minors for the class of graphs with linear-width at most two. Our proof also gives a linear time algorithm that either reports that a given graph has linear-width more than two or outputs an edge ordering of minimum linear-width. We further prove a structural connection between linear-width and the mixed search number which enables us to determine, for any k⩾1, the set of acyclic forbidden minors for the class of graphs with linear-width⩽k. Moreover, due to this connection, our algorithm can be transfered to two linear time algorithms that check whether a graph has mixed search or edge search number at most two and, if so, construct the corresponding sequences of search moves.
- Published
- 2000
- Full Text
- View/download PDF
34. Some Results on Non-deterministic Graph Searching in Trees
- Author
-
Amini, Omid, Coudert, David, Nisse, Nicolas, Département de Mathématiques et Applications - ENS Paris (DMA), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-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), GDR ASR ResCom, 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), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), École normale supérieure - Paris (ENS Paris), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
- Subjects
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Graph searching ,pathwidth ,treewidth ,Trees - Abstract
Non-deterministic graph searching was introduced by Fomin et al. to provide a unified approach for pathwidth, treewidth, and their interpretations in terms of graph searching games. Given q>=0, the q-limited search number, s_q(G), of a graph G is the smallest number of searchers required to capture an invisible fugitive in G, when the searchers are allowed to know the position of the fugitive at most q times. The search parameter s_0(G) corresponds to the pathwidth of a graph G, and s_{\infty}(G) to its treewidth. Determining s_q(G) is NP-complete for any fixed q>=0 in general graphs and s_0(T) can be computed in linear time in trees, however the complexity of the problem on trees has been unknown for any q>0. We introduce a new variant of graph searching that we call restricted non-deterministic. The corresponding parameter is denoted by rs_q and is shown to be equal to s_q for q=0,1, and at most twice s_q for any q>=2 (for any graph G). Our main result is the design of a polynomial time algorithm that computes rs_q(T) for any tree T and any q>= 0. This provides a 2-approximation of s_q(T) for any tree T, and shows that the decision problem associated to s_1 is polynomial in the class of trees. Our proofs are based on a new decomposition technique for trees which might be of independent interest. We also prove that the number of queries required to search a tree with two searchers can be computed in linear time. Tight upper bounds on the minimum number of queries for an arbitrary fixed number of searchers are also provided.
- Published
- 2013
35. A Distributed Algorithm for Computing the Node Search Number in Trees
- Author
-
Florian Huc, Dorian Mazauric, David Coudert, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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), Ecole Polytechnique Fédérale de Lausanne (EPFL), This work has been partially supported by région PACA and ANR AGAPE., ANR-18-CE23-0013,AGAPE,Un langage d'enchères pour des joueurs génériques d'enchères(2018), 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
Theoretical computer science ,General Computer Science ,Edge search number ,Best-first search ,Pathwidth ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Graph ,[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,Search algorithm ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,Mathematics ,Graph searching ,Fringe search ,Distributed algorithm ,Applied Mathematics ,Node (networking) ,Vertex Separation ,Data structure ,Tree (graph theory) ,Computer Science Applications ,Process number ,010201 computation theory & mathematics ,Node search number ,Beam search ,Algorithm - Abstract
International audience; We present a distributed algorithm to compute the node search number in trees. This algorithm extends the centralized algorithm proposed by Ellis \emph{et al.}~[EST94]. It can be executed in an asynchronous environment, requires an overall computation time of $O(n\log{n})$, and $n$ messages of $\log_3{n}+4$ bits each. The main contribution of this work lies in the data structure proposed to design our algorithm, called \emph{hierarchical decomposition}. This simple and flexible data structure is used for four operations: updating the node search number after addition or deletion of any tree-edges in a distributed fashion; computing it in a tree whose edges are added sequentially and in any order; computing other graph invariants such as the process number and the edge search number, by changing only initialization rules; extending our algorithms for trees and forests of unknown size (using messages of up to $2\log_3{n}+5$ bits).
- Published
- 2012
36. From Pathwidth to Connected Pathwidth
- Author
-
Dariusz Dereniowski, Dürr, Christoph, Department of Algorithms and Systems Modelling [ETI GUT] (Gdansk University of Technology), Faculty of Electronics, Telecommunications and Informatics [GUT Gdańsk] (ETI), and Gdańsk University of Technology (GUT)-Gdańsk University of Technology (GUT)
- Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,FOS: Computer and information sciences ,connected searching ,Discrete Mathematics (cs.DM) ,General Mathematics ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,0102 computer and information sciences ,02 engineering and technology ,connected pathwidth ,01 natural sciences ,Combinatorics ,Pathwidth ,graph searching ,0202 electrical engineering, electronic engineering, information engineering ,Mathematics ,Discrete mathematics ,060201 languages & linguistics ,000 Computer science, knowledge, general works ,fugitive search games ,Efficient algorithm ,pathwidth ,020206 networking & telecommunications ,06 humanities and the arts ,68R10 (Primary) 05C83, 05C85 (Secondary) ,Graph ,Running time ,Monotone polygon ,010201 computation theory & mathematics ,0602 languages and literature ,Computer Science ,020201 artificial intelligence & image processing ,[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC] ,Computer Science - Discrete Mathematics - Abstract
It is proven that the connected pathwidth of any graph $G$ is at most $2\cdot\textup{pw}(G)+1$, where $\textup{pw}(G)$ is the pathwidth of $G$. The method is constructive, i.e., it yields an efficient algorithm that for a given path decomposition of width $k$ computes a connected path decomposition of width at most $2k+1$. The running time of the algorithm is $O(dk^2)$, where $d$ is the number of “bags” in the input path decomposition. The motivation for studying connected path decompositions comes from the connection between the pathwidth and the search number of a graph. One of the advantages of the above bound for connected pathwidth is an inequality $\textup{\texttt{cs}}(G)\leq 2\textup{\texttt{s}}(G)+3$, where $\textup{\texttt{cs}}(G)$ and $\textup{\texttt{s}}(G)$ are the connected search number and the search number of $G$, respectively. Moreover, the algorithm presented in this work can be used to convert a given search strategy using $k$ searchers into a (monotone) connected one using $2k+3$ searc...
- Published
- 2011
37. Non-Deterministic Graph Searching: From Pathwidth to Treewidth
- Author
-
Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse, Department of Informatics [Bergen] (UiB), University of Bergen (UiB), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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), Research Council of Norway, INRIA Project 'Grand Large', and from the Project PairAPair of the ACI 'Masse de Données', Project Fragile of the ACI 'Sécurité & Informatique', 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
General Computer Science ,Treewidth ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Pathwidth ,02 engineering and technology ,0102 computer and information sciences ,Computer Science::Computational Complexity ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Tree-depth ,01 natural sciences ,Combinatorics ,Partial k-tree ,0202 electrical engineering, electronic engineering, information engineering ,0101 mathematics ,Mathematics ,Graph searching ,Discrete mathematics ,Applied Mathematics ,010102 general mathematics ,Tree decomposition ,Computer Science Applications ,Nondeterministic algorithm ,Graph bandwidth ,010201 computation theory & mathematics ,Graph (abstract data type) ,020201 artificial intelligence & image processing - Abstract
International audience; We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game-theoretic approach and graph decompositions called q -branched tree decompositions, which can be interpreted as a parameterized version of tree decompositions. Path decomposition and (standard) tree decomposition are two extreme cases of q-branched tree decompositions. The equivalence between nondeterministic graph searching and q-branched tree decomposition enables us to design an exact (exponential time) algorithm computing q-branched treewidth for all q≥0, which is thus valid for both treewidth and pathwidth. This algorithm performs as fast as the best known exact algorithm for pathwidth. Conversely, this equivalence also enables us to design a lower bound on the amount of nondeterminism required to search a graph with the minimum number of searchers.
- Published
- 2009
38. Monotony Properties of Connected Visible Graph Searching
- Author
-
Pierre Fraigniaud, Nicolas Nisse, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (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), project 'PairAPair' of the ACI Masses de Données, from the project 'Fragile' of the ACI Sécurité Informatique, and from the project 'Grand Large' of 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
Strongly connected component ,Treewidth ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Pathwidth ,0102 computer and information sciences ,02 engineering and technology ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Degeneracy (graph theory) ,01 natural sciences ,Theoretical Computer Science ,law.invention ,Combinatorics ,law ,Line graph ,0202 electrical engineering, electronic engineering, information engineering ,k-vertex-connected graph ,Graph toughness ,Complement graph ,Graph searching ,Mathematics ,Universal graph ,Distance-hereditary graph ,Connected component ,Discrete mathematics ,Computer Science Applications ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,020201 artificial intelligence & image processing ,Null graph ,Information Systems ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
International audience; Search games are attractive for their correspondence with classical width parameters. For instance, the \emph{invisible} search number (a.k.a. \emph{node} search number) of a graph is equal to its pathwidth plus~1, and the \emph{visible} search number of a graph is equal to its treewidth plus~1. The \emph{connected} variants of these games ask for search strategies that are connected, i.e., at every step of the strategy, the searched part of the graph induces a connected subgraph. We focus on \emph{monotone} search strategies, i.e., strategies for which every node is searched exactly once. The monotone connected visible search number of an $n$-node graph is at most $O(\log n)$ times its visible search number. First, we prove that this logarithmic bound is tight. Precisely, we prove that there is an infinite family of graphs for which the ratio monotone connected visible search number over visible search number is $\Omega(\log n)$. Second, we prove that, as opposed to the non-connected variant of visible graph searching, ``recontamination helps" for connected visible search. Precisely, we prove that, for any $k \geq 4$, there exists a graph with connected visible search number at most $k$, and monotone connected visible search number $>k$.
- Published
- 2006
39. The price of connectedness in expansions
- Author
-
Fomin, Fedor V., Fraigniaud, Pierre, Thilikos Touloupas, Dimitrios, and Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
- Subjects
Expansion ,Informàtica::Informàtica teòrica [Àrees temàtiques de la UPC] ,Branchwidth ,Pathwidth ,Graph searching - Abstract
Expansion is the way of generalizing different graph layout and searching problems. We initiate the study of connected expansion which naturally arises in a number of applications. Our main tool for this investigation is the branchwidth of a graph. In particular, we prove that any 2-edge-connected graph of branchwidth k has a {em connected} branch decom-po-si-tion of width k, i.e., a branch decomposition in which any cut separates two edge-sets that induce two connected subgraphs. Our proof is constructive, and is inspired from the existential proof of Seymour and Thomas (1994) for carvings. We also prove that the {em connected} search number (i.e., connected pathwidth) of any n-node graph of branchwidth k is at most O(klog n) and this bound is the best possible for parameters k and n. A first consequence of these results is that, for any graph, the connected search number is at most O(log n) times larger than the (standard) search number. The only bound known so far held for trees only. Another consequence is that the connected search number can be approximated in polynomial time up to a factor O(log{n}cdotlog{OPT}). That is, for any connected graph G, one can compute in polynomial time a connected search strategy for G that uses at most O (log{n}cdotlog{OPT}) times the optimal number OPT of searchers. The ratio O(log{n}cdotlog{OPT}) is the same as the best known approximation ratio for (standard) pathwidth, and any improvement for the approximation of connected search (i.e., connected pathwidth) would indeed produce an improvement for the approximation of pathwidth.
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.