834 results on '"Pathwidth"'
Search Results
2. PATHWIDTH VS COCIRCUMFERENCE.
- Author
-
BRIAŃSKI, MARCIN, JORET, GWENAËL JORET, and SEWERYN, MICHAŁT.
- Subjects
- *
MATROIDS , *GRAPH theory - Abstract
The circumference of a graph G with at least one cycle is the length of a longest cycle in G. A classic result of Birmel\'e [J. Graph Theory, 43 (2003), pp. 24--25] states that the treewidth of G is at most its circumference minus 1. In case G is 2-connected, this upper bound also holds for the pathwidth of G; in fact, even the treedepth of G is upper bounded by its circumference (Bria\'nski et al. [Treedepth vs circumference, Combinatorica, 43 (2023), pp. 659--664]). In this paper, we study whether similar bounds hold when replacing the circumference of G by its cocircumference, defined as the largest size of a bond in G, an inclusionwise minimal set of edges F such that G F has more components than G. In matroidal terms, the cocircumference of G is the circumference of the bond matroid of G. Our first result is the following "dual" version of Birmel'e's theorem: The treewidth of a graph G is at most its cocircumference. Our second and main result is an upper bound of 3k 2 on the pathwidth of a 2-connected graph G with cocircumference k. Contrary to circumference, no such bound holds for the treedepth of G. Our two upper bounds are best possible up to a constant factor. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
3. THE TREEWIDTH AND PATHWIDTH OF GRAPH UNIONS.
- Author
-
ALECU, BOGDAN, LOZIN, VADIM V., QUIROZ, DANIEL A., RABINOVICH, ROMAN, RAZGON, IGOR, and ZAMARAEV, VIKTOR
- Subjects
- *
GLUE , *SENSES - Abstract
Given two n-vertex graphs G1 and G2 of bounded treewidth, is there an n-vertex graph G of bounded treewidth having subgraphs isomorphic to G1 and G2? Our main result is a negative answer to this question, in a strong sense: we show that the answer is no even if G1 is a binary tree and G2 is a ternary tree. We also provide an extensive study of cases where such "gluing"" is possible. In particular, we prove that if G1 has treewidth k and G2 has pathwidth \l, then there is an n-vertex graph of treewidth at most k + 3\l + 1 containing both G1 and G2 as subgraphs. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
4. Monotone Arithmetic Complexity of Graph Homomorphism Polynomials.
- Author
-
Komarath, Balagopal, Pandey, Anurag, and Rahul, C. S.
- Subjects
- *
POLYNOMIALS , *ARITHMETIC , *CIRCUIT complexity , *HOMOMORPHISMS , *GRAPH algorithms - Abstract
We study homomorphism polynomials, which are polynomials that enumerate all homomorphisms from a pattern graph H to n-vertex graphs. These polynomials have received a lot of attention recently for their crucial role in several new algorithms for counting and detecting graph patterns, and also for obtaining natural polynomial families which are complete for algebraic complexity classes VBP , V P , and VNP . We discover that, in the monotone setting, the formula complexity, the ABP complexity, and the circuit complexity of such polynomial families are exactly characterized by the treedepth, the pathwidth, and the treewidth of the pattern graph respectively. Furthermore, we establish a single, unified framework, using our characterization, to collect several known results that were obtained independently via different methods. For instance, we attain superpolynomial separations between circuits, ABPs, and formulas in the monotone setting, where the polynomial families separating the classes all correspond to well-studied combinatorial problems. Moreover, our proofs rediscover fine-grained separations between these models for constant-degree polynomials. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
5. Approximating Pathwidth for Graphs of Small Treewidth.
- Author
-
GROENLAND, CARLA, JORET, GWENAËL, NADARA, WOJCIECH, and WALCZAK, BARTOSZ
- Subjects
APPROXIMATION algorithms ,TREE height ,POLYNOMIAL time algorithms ,GRAPH algorithms ,ALGORITHMS ,SUBDIVISION surfaces (Geometry) - Abstract
We describe a polynomial-time algorithm which, given a graph G with treewidth t, approximates the path-width of G to within a ratio of O(t√log t). This is the first algorithm to achieve an f(t)-approximation for some function f. Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a subdivision of a large complete binary tree. Specifically, we show that every graph with pathwidth at least th + 2 has treewidth at least t or contains a subdivision of a complete binary tree of height h + 1. The bound th + 2 is best possible up to a multiplicative constant. This result was motivated by, and implies (with c = 2), the following conjecture of Kawarabayashi and Rossman (SODA'18): there exists a universal constant c such that every graph with pathwidth Ω(k
c ) has treewidth at least k or contains a subdivision of a complete binary tree of height k. Our main technical algorithm takes a graph G and some (not necessarily optimal) tree decomposition of G of width t' in the input, and it computes in polynomial time an integer h, a certificate that G has pathwidth at least h, and a path decomposition of G of width at most (t' + 1)h + 1. The certificate is closely related to (and implies) the existence of a subdivision of a complete binary tree of height h. The approximation algorithm for pathwidth is then obtained by combining this algorithm with the approximation algorithm of Feige, Hajiaghayi, and Lee (STOC'05) for treewidth. [ABSTRACT FROM AUTHOR]- Published
- 2023
- Full Text
- View/download PDF
6. Possible and Impossible Attempts to Solve the Treewidth Problem via ILPs
- Author
-
Grigoriev, Alexander, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Fomin, Fedor V., editor, Kratsch, Stefan, editor, and van Leeuwen, Erik Jan, editor
- Published
- 2020
- Full Text
- View/download PDF
7. The localization capture time of a graph.
- Author
-
Behague, Natalie C., Bonato, Anthony, Huggan, Melissa A., Marbach, Trent G., and Pittman, Brittany
- Subjects
- *
PROJECTIVE planes , *TREE graphs , *LINEAR orderings , *CHARTS, diagrams, etc. , *GENEALOGY , *SUBGRAPHS - Abstract
The localization game is a pursuit-evasion game analogous to Cops and Robbers, where the robber is invisible and the cops send distance probes in an attempt to identify the location of the robber. We present a novel graph parameter called the localization capture time, which measures how long the localization game lasts assuming optimal play. We conjecture that the localization capture time is linear in the order of the graph, and show that the conjecture holds for graph families such as trees and interval graphs. We study bounds on the localization capture time for trees and its monotone property on induced subgraphs of trees and more general graphs. We give upper bounds for the localization capture time on the incidence graphs of projective planes. We finish with new bounds on the localization number and localization capture time using treewidth. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
8. On the Parameterized Complexity of the Expected Coverage Problem.
- Author
-
Fomin, Fedor V. and Ramamoorthi, Vijayaragunathan
- Subjects
- *
LINEAR orderings , *OPERATIONS research , *INTEGERS , *PROBLEM solving - Abstract
The Maximum Covering Location Problem (MCLP) is a well-studied problem in the field of operations research. Given a network with positive or negative demands on the nodes, a positive integer k, the MCLP seeks to find k potential facility centers in the network such that the neighborhood coverage is maximized. We study the variant of MCLP where edges of the network are subject to random failures due to some disruptive events. One of the popular models capturing the unreliable nature of the facility location is the linear reliability ordering (LRO) model. In this model, with every edge e of the network, we associate its survival probability 0 ≤ pe ≤ 1, or equivalently, its failure probability 1 − pe. The failure correlation in LRO is the following: If an edge e fails then every edge e ′ with p e ′ ≤ p e surely fails. The task is to identify the positions of k facilities that maximize the expected coverage. We refer to this problem as Expected Coverage problem. We study the Expected Coverage problem from the parameterized complexity perspective and obtain the following results. 1. For the parameter pathwidth, we show that the Expected Coverage problem is W[1]-hard. We find this result a bit surprising, because the variant of the problem with non-negative demands is fixed-parameter tractable (FPT) parameterized by the treewidth of the input graph. 2. We complement the lower bound by the proof that Expected Coverage is FPT being parameterized by the treewidth and the maximum vertex degree. We give an algorithm that solves the problem in time 2 O (tw log Δ) n O (1) , where tw is the treewidth, Δ is the maximum vertex degree, and n the number of vertices of the input graph. In particular, since Δ ≤ n, it means the problem is solvable in time n O (tw) , that is, is in XP parameterized by treewidth. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
9. Positive-Instance Driven Dynamic Programming for Graph Searching
- Author
-
Bannach, Max, Berndt, Sebastian, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Friggstad, Zachary, editor, Sack, Jörg-Rüdiger, editor, and Salavatipour, Mohammad R, editor
- Published
- 2019
- Full Text
- View/download PDF
10. Bounds on the Diameter of Graph Associahedra.
- Author
-
Cardinal, Jean, Pournin, Lionel, and Valencia-Pabon, Mario
- Subjects
COMBINATORICS ,SKELETON ,POLYTOPES ,ROTATIONAL motion ,TREES ,DIAMETER - Abstract
Graph associahedra are generalized permutohedra arising as special cases of nestohedra and hypergraphic polytopes. The graph associahedron of a graph G encodes the combinatorics of search trees on G, defined recursively by a root r together with search trees on each of the connected components of G − r. In particular, the skeleton of the graph associahedron is the rotation graph of those search trees. We investigate the diameter of graph associahedra as a function of some graph parameters. It is known that the diameter of the associahedra of paths of length n, the classical associahedra, is 2n - 6 for a large enough n. We give a tight bound of Θ(m) on the diameter of trivially perfect graph associahedra on m edges. We consider the maximum diameter of associahedra of graphs on n vertices and of given tree-depth, treewidth, or pathwidth, and give lower and upper bounds as a function of these parameters. Finally, we prove that the maximum diameter of associahedra of graphs of pathwidth two is Θ(n log n). [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
11. The Effect of Planarization on Width
- Author
-
Eppstein, David, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Frati, Fabrizio, editor, and Ma, Kwan-Liu, editor
- Published
- 2018
- Full Text
- View/download PDF
12. On the Number of Labeled Graphs of Bounded Treewidth
- Author
-
Baste, Julien, Noy, Marc, Sau, Ignasi, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Bodlaender, Hans L., editor, and Woeginger, Gerhard J., editor
- Published
- 2017
- Full Text
- View/download PDF
13. SAT-Encodings for Special Treewidth and Pathwidth
- Author
-
Lodha, Neha, Ordyniak, Sebastian, Szeider, Stefan, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Gaspers, Serge, editor, and Walsh, Toby, editor
- Published
- 2017
- Full Text
- View/download PDF
14. 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
15. Connecting Knowledge Compilation Classes Width Parameters.
- Author
-
Amarilli, Antoine, Capelli, Florent, Monet, Mikaël, and Senellart, Pierre
- Subjects
- *
LOGIC circuits , *CIRCUIT complexity , *TIMING circuits , *BOOLEAN functions - 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). [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
16. MINOR-CLOSED GRAPH CLASSES WITH BOUNDED LAYERED PATHWIDTH.
- Author
-
DUJMOVIĆ, VIDA, EPPSTEIN, DAVID, JORET, GWENAËL, MORIN, PAT, and WOOD, DAVID R.
- Abstract
We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if some apex-forest is not in the class. This generalizes a theorem of Robertson and Seymour, which says that a minor-closed class of graphs has bounded pathwidth if and only if some forest is not in the class. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
17. Using decomposition-parameters for QBF: Mind the prefix!
- Author
-
Eiben, Eduard, Ganian, Robert, and Ordyniak, Sebastian
- Subjects
- *
AWARENESS , *ALGORITHMS - Abstract
Similar to the satisfiability (SAT) problem, which can be seen to be the archetypical problem for NP, the quantified Boolean formula problem (QBF) is the archetypical problem for PSPACE. Recently, Atserias and Oliva (2014) showed that, unlike for SAT, many of the well-known decompositional parameters (such as treewidth and pathwidth) do not allow efficient algorithms for QBF. The main reason for this seems to be the lack of awareness of these parameters towards the dependencies between variables of a QBF formula. In this paper we extend the ordinary pathwidth to the QBF-setting by introducing prefix pathwidth, which takes into account the dependencies between variables in a QBF, and show that it leads to an efficient algorithm for QBF. We hope that our approach will help to initiate the study of novel tailor-made decompositional parameters for QBF and thereby help to lift the success of these decompositional parameters from SAT to QBF. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
18. Near-Optimal Low-Congestion Shortcuts on Bounded Parameter Graphs
- Author
-
Haeupler, Bernhard, Izumi, Taisuke, Zuzic, Goran, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Gavoille, Cyril, editor, and Ilcinkas, David, editor
- Published
- 2016
- Full Text
- View/download PDF
19. 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
20. Structural Parameterizations for Boxicity
- Author
-
Bruhn, Henning, Chopin, Morgan, Joos, Felix, Schaudt, Oliver, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Kratsch, Dieter, editor, and Todinca, Ioan, editor
- Published
- 2014
- Full Text
- View/download PDF
21. 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
22. Constrained Connectivity in Bounded X-Width Multi-Interface Networks
- Author
-
Alessandro Aloisio and Alfredo Navarra
- Subjects
multi-interface networks ,constrained connectivity ,energy optimization ,treewidth ,pathwidth ,carvingwidth ,Industrial engineering. Management engineering ,T55.4-60.8 ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
As technology advances and the spreading of wireless devices grows, the establishment of interconnection networks is becoming crucial. Main activities that involve most of the people concern retrieving and sharing information from everywhere. In heterogeneous networks, devices can communicate by means of multiple interfaces. The choice of the most suitable interfaces to activate (switch-on) at each device results in the establishment of different connections. A connection is established when at its endpoints the devices activate at least one common interface. Each interface is assumed to consume a specific percentage of energy for its activation. This is referred to as the cost of an interface. Due to energy consumption issues, and the fact that most of the devices are battery powered, special effort must be devoted to suitable solutions that prolong the network lifetime. In this paper, we consider the so-called p-Coverage problem where each device can activate at most p of its available interfaces in order to establish all the desired connections of a given network of devices. As the problem has been shown to be NP -hard even for p = 2 and unitary costs of the interfaces, algorithmic design activities have focused in particular topologies where the problem is optimally solvable. Following this trend, we first show that the problem is polynomially solvable for graphs (modeling the underlying network) of bounded treewidth by means of the Courcelle’s theorem. Then, we provide two optimal polynomial time algorithms to solve the problem in two subclasses of graphs with bounded treewidth that are graphs of bounded pathwidth and graphs of bounded carvingwidth. The two solutions are obtained by means of dynamic programming techniques.
- Published
- 2020
- Full Text
- View/download PDF
23. A polynomial excluded-minor approximation of treedepth
- Author
-
Ken-ichi Kawarabayashi and Benjamin Rossman
- Subjects
Combinatorics ,Treewidth ,Polynomial ,Pathwidth ,Applied Mathematics ,General Mathematics ,Path (graph theory) ,Minor (linear algebra) ,Graph property ,Time complexity ,Tree (graph theory) ,Mathematics - Abstract
Treedepth is a well-studied graph invariant in the family of "width measures" that includes treewidth and pathwidth. Understanding these invariants in terms of excluded minors has been an active area of research. The recent Grid Minor Theorem of Chekuri and Chuzhoy [12] establishes that treewidth is polynomially approximated by the largest k x k grid minor. In this paper, we give a similar polynomial excluded-minor approximation for treedepth in terms of three basic obstructions: grids, tree, and paths. Specifically, we show that there is a constant c such that every graph of treedepth ≥ kc contains one of the following minors (each of treedepth ≥ k): • the k x k grid, • the complete binary tree of height k, • the path of order 2k. Let us point out that we cannot drop any of the above graphs for our purpose. Moreover, given a graph G we can, in randomized polynomial time, find either an embedding of one of these minors or conclude that treedepth of G is at most kc. This result has potential applications in a variety of settings where bounded treedepth plays a role. In addition to some graph structural applications, we describe a surprising application in circuit complexity and finite model theory from recent work of the second author [28].
- Published
- 2021
24. 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
25. The treewidth of line graphs.
- Author
-
Harvey, Daniel J. and Wood, David R.
- Subjects
- *
LINEAR statistical models , *INVARIANTS (Mathematics) , *ALGOL (Computer program language) , *GRAPH theory , *GEOMETRIC vertices - Abstract
The treewidth of a graph is an important invariant in structural and algorithmic graph theory. This paper studies the treewidth of line graphs . We show that determining the treewidth of the line graph of a graph G is equivalent to determining the minimum vertex congestion of an embedding of G into a tree. Using this result, we prove sharp lower bounds in terms of both the minimum degree and average degree of G . These results are precise enough to exactly determine the treewidth of the line graph of a complete graph and other interesting examples. We also improve the best known upper bound on the treewidth of a line graph. Analogous results are proved for pathwidth. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
26. 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
27. 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
28. Typical Sequences Revisited — Computing Width Parameters of Graphs
- Author
-
Bodlaender, Hans L., Jaffke, Lars, Telle, Jan Arne, Paul, Christophe, Bläser, Markus, Sub Algorithms and Complexity, and Algorithms and Complexity
- Subjects
FOS: Computer and information sciences ,typical sequences ,0102 computer and information sciences ,02 engineering and technology ,Computer Science::Computational Complexity ,Series and parallel circuits ,01 natural sciences ,Constructive ,Bottleneck ,Theoretical Computer Science ,Pathwidth ,Computer Science::Discrete Mathematics ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,treewidth ,0202 electrical engineering, electronic engineering, information engineering ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,series parallel digraphs ,Computer Science::Data Structures and Algorithms ,Time complexity ,Mathematics ,Discrete mathematics ,Lemma (mathematics) ,cutwidth ,modified cutwidth ,020206 networking & telecommunications ,Treewidth ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Theory of computation ,Combinatorics (math.CO) - Abstract
In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized algorithms for treewidth and pathwidth. The lemma addresses a runtime bottleneck in those algorithms but so far it does not lead to asymptotically faster algorithms. However, we apply the lemma to show that the cutwidth and the modified cutwidth of series parallel digraphs can be computed in $\mathcal{O}(n^2)$ time., Comment: 30 pages, 10 figures; accepted at STACS 2020
- Published
- 2021
29. Clique Dominating Sets of Direct Product Graph of Cayley Graphs with Arithmetic Graphs
- Author
-
M. Manjuri and B. Maheswari
- Subjects
Lévy family of graphs ,Clique-sum ,Dense graph ,Cayley graph ,Computer science ,Trapezoid graph ,Graph theory ,1-planar graph ,Graph ,Modular decomposition ,Treewidth ,Indifference graph ,Pathwidth ,Chordal graph ,Dominating set ,Graph drawing ,Partial k-tree ,Odd graph ,Topological graph theory ,Maximal independent set ,Split graph ,Arithmetic ,Graph product ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
Graph Theory is one of the most flourishing branches of modern Mathematics finding widest applications in all most all branches of Science & Technology. It is applied in diverse areas such as social sciences, linguistics, physical sciences, communication engineering etc. Number Theory is one of the oldest branches of Mathematics, which inherited rich contributions from almost all greatest mathematicians, ancient and modern. Every branch of mathematics employs some notion of a product that enables the combination or decomposition of its elemental structures. Product of graphs are introduced in Graph Theory very recently and developing rapidly. In this paper, we consider direct product graphs of Cayley graphs with Arithmetic graphs and present Matching dominating set of these graphs.
- Published
- 2021
30. 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
31. Improved Bounds for the Excluded-Minor Approximation of Treedepth
- Author
-
Wojciech Czerwiński, Wojciech Nadara, Marcin Pilipczuk, and Wagner, Michael
- Subjects
FOS: Computer and information sciences ,Dense graph ,Discrete Mathematics (cs.DM) ,General Mathematics ,Existential quantification ,Minor (linear algebra) ,0102 computer and information sciences ,Computer Science::Computational Complexity ,01 natural sciences ,Combinatorics ,Pathwidth ,Computer Science::Discrete Mathematics ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,Computer Science::Data Structures and Algorithms ,Mathematics ,Discrete mathematics ,000 Computer science, knowledge, general works ,Treewidth ,010201 computation theory & mathematics ,Computer Science ,Graph (abstract data type) ,Combinatorics (math.CO) ,Constant (mathematics) ,Computer Science - Discrete Mathematics - Abstract
Treedepth, a more restrictive graph width parameter than treewidth and pathwidth, plays a major role in the theory of sparse graph classes. We show that there exists a constant $C$ such that for every positive integers $a,b$ and a graph $G$, if the treedepth of $G$ is at least $Cab$, then the treewidth of $G$ is at least $a$ or $G$ contains a subcubic (i.e., of maximum degree at most $3$) tree of treedepth at least $b$ as a subgraph. As a direct corollary, we obtain that every graph of treedepth $\Omega(k^3)$ is either of treewidth at least $k$, contains a subdivision of full binary tree of depth $k$, or contains a path of length $2^k$. This improves the bound of $\Omega(k^5 \log^2 k)$ of Kawarabayashi and Rossman [SODA 2018]. We also show an application of our techniques for approximation algorithms of treedepth: given a graph $G$ of treedepth $k$ and treewidth $t$, one can in polynomial time compute a treedepth decomposition of $G$ of width $\mathcal{O}(kt \log^{3/2} t)$. This improves upon a bound of $\mathcal{O}(kt^2 \log t)$ stemming from a tradeoff between known results. The main technical ingredient in our result is a proof that every tree of treedepth $d$ contains a subcubic subtree of treedepth at least $d \cdot \log_3 ((1+\sqrt{5})/2)$.
- Published
- 2021
32. The treewidth of proofs.
- Author
-
Müller, Moritz and Szeider, Stefan
- Subjects
- *
DIRECTED graphs , *PROOF theory , *PATHS & cycles in graph theory , *AXIOMS , *TOPOLOGICAL spaces , *MATHEMATICAL bounds - Abstract
So-called ordered variants of the classical notions of pathwidth and treewidth are introduced and proposed as proof theoretically meaningful complexity measures for the directed acyclic graphs underlying proofs. Ordered pathwidth is roughly the same as proof space and the ordered treewidth of a proof is meant to serve as a measure of how far it is from being treelike. Length-space lower bounds for k -DNF refutations are generalized to arbitrary infinity axioms and strengthened in that the space measure is relaxed to ordered treewidth. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
33. ON TREEWIDTH AND RELATED PARAMETERS OF RANDOM GEOMETRIC GRAPHS.
- Author
-
MITSCHE, DIETER and PERARNAU, GUILLEM
- Subjects
- *
MATHEMATICAL proofs , *TREE graphs , *GRAPH theory , *TREE codes (Coding theory) , *GEOMETRY - Abstract
We give asymptotically exact values for the treewidth tw(G) of a random geometric graph G ∈ G(n, r) in [0, √n]². More precisely, let rc denote the threshold radius for the appearance of the giant component in G(n, r). We then show that for any constant 0 < r < rc, tw(G) = Θ(log n/log log n), and for c being sufficiently large, and r = r(n) ≥ c, tw(G) = Θ(r√n). Our proofs show that for the corresponding values of r the same asymptotic bounds also hold for the pathwidth and the treedepth of a random geometric graph. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
34. STRUCTURE OF GRAPHS WITH LOCALLY RESTRICTED CROSSINGS.
- Author
-
DUJMOVIĆ, VIDA, EPPSTEIN, DAVID, and WOOD, DAVID R.
- Subjects
- *
PLANAR graphs , *CROSSING numbers (Graph theory) , *GRAPH theory , *EMBEDDINGS (Mathematics) , *LOGARITHMIC functions - Abstract
We consider relations between the size, treewidth, and local crossing number (maximum number of crossings per edge) of graphs embedded on topological surfaces. We show that an n-vertex graph embedded on a surface of genus g with at most k crossings per edge has treewidth O(√(g + 1)(k + 1)n) and layered treewidth O((g + 1)k) and t hat these bounds are tight up to a constant factor. In the special case of g = 0, so-called k-planar graphs, the treewidth bound is O(√((k + 1)n), which is tight and improves upon a known O( (k + 1)3/4n1/2) bound. Analogous results are proved for map graphs defined with respect to any surface. Finally, we show that for g < m, every m-edge graph can be embedded on a surface of genus g with O((m/(g + 1)) log² g) crossings per edge, which is tight to a polylogarithmic factor. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
35. Treewidth and Pathwidth parameterized by the vertex cover number.
- Author
-
Chapelle, Mathieu, Liedloff, Mathieu, Todinca, Ioan, and Villanger, Yngve
- Subjects
- *
PARAMETERIZATION , *KERNEL (Mathematics) , *TREE graphs , *POLYNOMIALS , *GEOMETRIC vertices - Abstract
After the number of vertices, Vertex Cover Number is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized problems, including problems that are not directly related to the Vertex Cover Number . Here we consider the treewidth and pathwidth problems parameterized by k , the size of a minimum vertex cover of the input graph. We show that the pathwidth and treewidth can be computed in O ∗ ( 3 k ) time. This complements recent polynomial kernel results for treewidth and pathwidth parameterized by the Vertex Cover Number . [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
36. Parametrised Complexity of Satisfiability in Temporal Logic.
- Author
-
LÜCK, MARTIN, MEIER, ARNE, and SCHINDLER, IRENA
- Subjects
LOGIC ,LATTICE theory ,BOOLEAN functions ,PROPOSITION (Logic) ,MATHEMATICAL formulas - Abstract
We apply the concept of formula treewidth and pathwidth to computation tree logic, linear temporal logic, and the full branching time logic. Several representations of formulas as graphlike structures are discussed, and corresponding notions of treewidth and pathwidth are introduced. As an application for such structures, we present a classification in terms of parametrised complexity of the satisfiability problem, where we make use of Courcelle's famous theorem for recognition of certain classes of structures. Our classification shows a dichotomy between W[1]-hard and fixed-parameter tractable operator fragments almost independently of the chosen graph representation. The only fragments that are proven to be fixed-parameter tractable (FPT) are those that are restricted to the X operator. By investigating Boolean operator fragments in the sense of Post's lattice, we achieve the same complexity as in the unrestricted case if the set of available Boolean functions can express the function "negation of the implication." Conversely, we show containment in FPT for almost all other clones. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
37. Incremental optimization of independent sets under the reconfiguration framework
- Author
-
Akira Suzuki, Haruka Mizuta, Takehiro Ito, and Naomi Nishimura
- Subjects
Vertex (graph theory) ,021103 operations research ,Control and Optimization ,Applied Mathematics ,0211 other engineering and technologies ,Parameterized complexity ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Degeneracy (graph theory) ,Computer Science Applications ,Planar graph ,Treewidth ,Combinatorics ,symbols.namesake ,Pathwidth ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Chordal graph ,Independent set ,symbols ,Discrete Mathematics and Combinatorics ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
Suppose that we are given an independent set \(I_0\) of a graph G, and an integer \(l\ge 0\). Then, we are asked to find an independent set of G having the maximum size among independent sets that are reachable from \(I_0\) by either adding or removing a single vertex at a time such that all intermediate independent sets are of size at least \(l\). We show that this problem is PSPACE-hard even for bounded pathwidth graphs, and remains NP-hard for planar graphs. On the other hand, we give a linear-time algorithm to solve the problem for chordal graphs. We also study the parameterized complexity of the problem with respect to the following three parameters: the degeneracy \(d\) of an input graph, a lower bound \(l\) on the size of independent sets, and a lower bound \(s\) on the size of a solution reachable from \(I_0\). We show that the problem is fixed-parameter intractable when only one of \(d\), \(l\), and \(s\) is taken as a parameter. On the other hand, we give a fixed-parameter algorithm when parameterized by \(s+d\); this result implies that the problem parameterized only by \(s\) is fixed-parameter tractable for planar graphs, and for bounded treewidth graphs.
- Published
- 2020
38. Using decomposition-parameters for QBF: Mind the prefix!
- Author
-
Sebastian Ordyniak, Eduard Eiben, and Robert Ganian
- Subjects
Discrete mathematics ,Computer Networks and Communications ,Computer science ,True quantified Boolean formula ,Efficient algorithm ,Applied Mathematics ,General Medicine ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Satisfiability ,Theoretical Computer Science ,Treewidth ,Lift (mathematics) ,Prefix ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Pathwidth ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,020204 information systems ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,0202 electrical engineering, electronic engineering, information engineering ,PSPACE - Abstract
Similar to the satisfiability (SAT) problem, which can be seen to be the archetypical problem for NP, the quantified Boolean formula problem (QBF) is the archetypical problem for PSPACE. Recently, Atserias and Oliva (2014) showed that, unlike for SAT, many of the well-known decompositional parameters (such as treewidth and pathwidth) do not allow efficient algorithms for QBF. The main reason for this seems to be the lack of awareness of these parameters towards the dependencies between variables of a QBF formula. In this paper we extend the ordinary pathwidth to the QBF-setting by introducing prefix pathwidth, which takes into account the dependencies between variables in a QBF, and show that it leads to an efficient algorithm for QBF. We hope that our approach will help to initiate the study of novel tailor-made decompositional parameters for QBF and thereby help to lift the success of these decompositional parameters from SAT to QBF.
- Published
- 2020
39. Minor-Closed Graph Classes with Bounded Layered Pathwidth
- Author
-
David R. Wood, Pat Morin, Gwenaël Joret, Vida Dujmović, and David Eppstein
- Subjects
FOS: Computer and information sciences ,Class (set theory) ,Discrete Mathematics (cs.DM) ,General Mathematics ,Minor (linear algebra) ,0102 computer and information sciences ,Computer Science::Computational Complexity ,01 natural sciences ,Combinatorics ,Pathwidth ,Computer Science::Discrete Mathematics ,FOS: Mathematics ,Graph minor ,Théorie des graphes ,Mathematics - Combinatorics ,0101 mathematics ,Computer Science::Data Structures and Algorithms ,Mathematics ,Discrete mathematics ,010102 general mathematics ,Graph ,Treewidth ,010201 computation theory & mathematics ,Bounded function ,Combinatorics (math.CO) ,Computer Science - Discrete Mathematics - Abstract
We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if some apex-forest is not in the class. This generalises a theorem of Robertson and Seymour, which says that a minor-closed class of graphs has bounded pathwidth if and only if some forest is not in the class.
- Published
- 2020
40. Monotone Arithmetic Complexity of Graph Homomorphism Polynomials
- Author
-
Balagopal Komarath, Anurag Pandey, and C. S. Rahul
- Subjects
Algebraic complexity ,General Computer Science ,Applied Mathematics ,Fixed-parameter algorithms and complexity ,Treewidth ,Graph homomorphisms ,Mathematics of computing → Graph algorithms ,Fine-grained complexity ,Algebraic circuits ,Homomorphism polynomials ,Pathwidth ,Computer Science::Computational Complexity ,Monotone complexity ,Computer Science Applications ,Treedepth ,Algebraic branching programs ,Algebraic formulas ,Theory of computation → Parameterized complexity and exact algorithms ,Graph algorithms ,Theory of computation → Algebraic complexity theory ,Theory of computation → Computational complexity and cryptography ,Theory of computation → Circuit complexity - Abstract
We study homomorphism polynomials, which are polynomials that enumerate all homomorphisms from a pattern graph H to n-vertex graphs. These polynomials have received a lot of attention recently for their crucial role in several new algorithms for counting and detecting graph patterns, and also for obtaining natural polynomial families which are complete for algebraic complexity classes VBP, VP, and VNP. We discover that, in the monotone setting, the formula complexity, the ABP complexity, and the circuit complexity of such polynomial families are exactly characterized by the treedepth, the pathwidth, and the treewidth of the pattern graph respectively. Furthermore, we establish a single, unified framework, using our characterization, to collect several known results that were obtained independently via different methods. For instance, we attain superpolynomial separations between circuits, ABPs, and formulas in the monotone setting, where the polynomial families separating the classes all correspond to well-studied combinatorial problems. Moreover, our proofs rediscover fine-grained separations between these models for constant-degree polynomials., LIPIcs, Vol. 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), pages 83:1-83:20
- Published
- 2022
- Full Text
- View/download PDF
41. Homomorphism Tensors and Linear Equations
- Author
-
Grohe, Martin, Rattan, Gaurav, and Seppelt, Tim
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,pathwidth ,treedepth ,Mathematics of computing → Discrete mathematics ,G.2.1 ,G.2.2 ,homomorphisms ,labelled graphs ,Sherali-Adams relaxation ,FOS: Mathematics ,treewidth ,Weisfeiler-Leman ,Mathematics - Combinatorics ,Wiegmann-Specht Theorem ,Combinatorics (math.CO) ,linear equations ,Computer Science - Discrete Mathematics ,05C60, 05C76, 05C05, 05C38, 05C50, 05E10, 20M32 - Abstract
Lovász (1967) showed that two graphs G and H are isomorphic if and only if they are homomorphism indistinguishable over the class of all graphs, i.e. for every graph F, the number of homomorphisms from F to G equals the number of homomorphisms from F to H. Recently, homomorphism indistinguishability over restricted classes of graphs such as bounded treewidth, bounded treedepth and planar graphs, has emerged as a surprisingly powerful framework for capturing diverse equivalence relations on graphs arising from logical equivalence and algebraic equation systems. In this paper, we provide a unified algebraic framework for such results by examining the linear-algebraic and representation-theoretic structure of tensors counting homomorphisms from labelled graphs. The existence of certain linear transformations between such homomorphism tensor subspaces can be interpreted both as homomorphism indistinguishability over a graph class and as feasibility of an equational system. Following this framework, we obtain characterisations of homomorphism indistinguishability over several natural graph classes, namely trees of bounded degree, graphs of bounded pathwidth (answering a question of Dell et al. (2018)), and graphs of bounded treedepth., LIPIcs, Vol. 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), pages 70:1-70:20
- Published
- 2022
- Full Text
- View/download PDF
42. The Parameterised Complexity of Computing the Maximum Modularity of a Graph
- Author
-
Fiona Skerman and Kitty Meeks
- Subjects
FOS: Computer and information sciences ,General Computer Science ,Vertex cover ,Pathwidth ,0102 computer and information sciences ,Computational Complexity (cs.CC) ,01 natural sciences ,Computer Science::Discrete Mathematics ,Computer Science - Data Structures and Algorithms ,0103 physical sciences ,FOS: Mathematics ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,Integer quadratic programming · ,010306 general physics ,Time complexity ,modularity ,Mathematics ,Discrete mathematics ,Modularity (networks) ,000 Computer science, knowledge, general works ,Community detection ,Applied Mathematics ,Computer Science Applications ,Treewidth ,Computer Science - Computational Complexity ,010201 computation theory & mathematics ,Bounded function ,Computer Science ,Graph (abstract data type) ,Feedback vertex set ,Combinatorics (math.CO) ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
The maximum modularity of a graph is a parameter widely used to describe the level of clustering or community structure in a network. Determining the maximum modularity of a graph is known to be NP-complete in general, and in practice a range of heuristics are used to construct partitions of the vertex-set which give lower bounds on the maximum modularity but without any guarantee on how close these bounds are to the true maximum. In this paper we investigate the parameterised complexity of determining the maximum modularity with respect to various standard structural parameterisations of the input graph G. We show that the problem belongs to FPT when parameterised by the size of a minimum vertex cover for G, and is solvable in polynomial time whenever the treewidth or max leaf number of G is bounded by some fixed constant; we also obtain an FPT algorithm, parameterised by treewidth, to compute any constant-factor approximation to the maximum modularity. On the other hand we show that the problem is W[1]-hard (and hence unlikely to admit an FPT algorithm) when parameterised simultaneously by pathwidth and the size of a minimum feedback vertex set., Comment: Author final version, accepted to Algorithmica
- Published
- 2019
43. 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
44. Specifying graph languages with type graphs
- Author
-
Andrea Corradini, Barbara König, and Dennis Nolte
- Subjects
FOS: Computer and information sciences ,Computer Science - Logic in Computer Science ,Dense graph ,Formal Languages and Automata Theory (cs.FL) ,Logic ,Computer science ,Symmetric graph ,Comparability graph ,Computer Science - Formal Languages and Automata Theory ,Theoretical Computer Science ,Computer Science (all) ,02 engineering and technology ,0102 computer and information sciences ,Type graph ,01 natural sciences ,law.invention ,Combinatorics ,Indifference graph ,Pathwidth ,Chordal graph ,law ,Partial k-tree ,Line graph ,0202 electrical engineering, electronic engineering, information engineering ,Cograph ,Split graph ,Pancyclic graph ,Forbidden graph characterization ,Universal graph ,Block graph ,Discrete mathematics ,Graph rewriting ,Lévy family of graphs ,020207 software engineering ,1-planar graph ,Rotation formalisms in three dimensions ,Graph ,Logic in Computer Science (cs.LO) ,Decidability ,Modular decomposition ,Treewidth ,Informatik ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Topological graph theory ,Graph product ,Software ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
We investigate three formalisms to specify graph languages, i.e. sets of graphs, based on type graphs. First, we are interested in (pure) type graphs, where the corresponding language consists of all graphs that can be mapped homomorphically to a given type graph. In this context, we also study languages specified by restriction graphs and their relation to type graphs. Second, we extend this basic approach to a type graph logic and, third, to type graphs with annotations. We present decidability results and closure properties for each of the formalisms., (v2): -Fixed some typos -Added more references
- Published
- 2019
45. A General Reduction Theorem with Applications to Pathwidth and the Complexity of MAX 2-CSP.
- Author
-
Edwards, Keith and McDermid, Eric
- Subjects
- *
MATHEMATICAL simplification , *MATHEMATICS theorems , *COMPUTATIONAL complexity , *GRAPH theory , *PARAMETER estimation , *GEOMETRIC vertices , *ALGORITHMS - Abstract
We prove a general reduction theorem which allows us to extend bounds for certain graph parameters on cubic graphs to bounds for general graphs taking into account the individual vertex degrees. As applications, we give an algorithm for Max $$2$$ -CSP whose complexity matches the algorithm of Scott and Sorkin in the case of $$d$$ -regular graphs, $$d \le 5$$ , but is otherwise faster. It also improves on the previously fastest known algorithm in terms of the average degree, given by Golovnev and Kutzkov. Also from the general theorem, we derive a bound for the pathwidth of a general graph which equals that of Fomin et al. and Gaspers for graphs of degree at most $$6$$ , but is smaller otherwise, and use this to give an improved exponential-space algorithm for Max $$2$$ -CSP. Finally we use the general result to give a faster algorithm for Max $$2$$ -CSP on claw-free graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
46. 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
47. Sur la largeur arborescente linéaire des 3-variétés hyperboliques
- Author
-
Huszár, Kristóf, Understanding the Shape of Data (DATASHAPE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria), 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), and This work has been supported by the French government, through the 3IA Côte d'Azur Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-19-P3IA-0002.
- Subjects
complexité paramétrée ,Computational Geometry (cs.CG) ,FOS: Computer and information sciences ,topologie algorithmique des 3-variétés ,largeur arborescente linéaire ,largeur arborescente ,G.2.2 ,[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] ,computational 3-manifold topology ,MSC 57Q15, 57N10, 05C75, 57M15 ,Mathematics - Geometric Topology ,divisions de Heegaard généralisées ,[MATH.MATH-GT]Mathematics [math]/Geometric Topology [math.GT] ,solubilité à paramètre fixé ,thick-thin decomposition ,treewidth ,FOS: Mathematics ,F.2.2 ,volume ,generalized Heegaard splittings ,hyperbolic 3-manifolds ,3-variétés hyperboliques ,57Q15, 57N10, 05C75, 57M15 ,pathwidth ,Geometric Topology (math.GT) ,décomposition épaisse-fine ,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 ,Computer Science - Computational Geometry - Abstract
According to Mostow's celebrated rigidity theorem, the geometry of closed hyperbolic 3-manifolds is already determined by their topology. In particular, the volume of such manifolds is a topological invariant and, as such, has been subject of investigations for half a century. Motivated by the algorithmic study of 3-manifolds, Maria and Purcell have recently shown that every closed hyperbolic 3-manifold M with volume vol(M) admits a triangulation with dual graph of treewidth at most C vol(M), for some universal constant C. Here we improve on this result by showing that the volume provides a linear upper bound even on the pathwidth of the dual graph of some triangulation, which can potentially be much larger than the treewidth. Our proof relies on a synthesis of tools from 3-manifold theory: generalized Heegaard splittings, amalgamations, and the thick-thin decomposition of hyperbolic 3-manifolds. We provide an illustrated exposition of this toolbox and also discuss the algorithmic consequences of the result., Computing in Geometry and Topology, Vol. 1 No. 1 (2022)
- Published
- 2021
- Full Text
- View/download PDF
48. Bounds on Half Graph Orders in Powers of Sparse Graphs
- Author
-
Marek Sokołowski
- Subjects
FOS: Computer and information sciences ,Polynomial ,Minor (linear algebra) ,Parameterized complexity ,0102 computer and information sciences ,Clique (graph theory) ,01 natural sciences ,Theoretical Computer Science ,Combinatorics ,symbols.namesake ,Pathwidth ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Data Structures and Algorithms (cs.DS) ,0101 mathematics ,Mathematics ,Applied Mathematics ,010102 general mathematics ,16. Peace & justice ,Planar graph ,Treewidth ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Bounded function ,symbols ,Combinatorics (math.CO) ,Geometry and Topology ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
Half graphs and their variants, such as ladders, semi-ladders and co-matchings, are combinatorial objects that encode total orders in graphs. Works by Adler and Adler (Eur. J. Comb.; 2014) and Fabia\'nski et al. (STACS; 2019) prove that in the powers of sparse graphs, one cannot find arbitrarily large objects of this kind. However, these proofs either are non-constructive, or provide only loose upper bounds on the orders of half graphs and semi-ladders. In this work we provide nearly tight asymptotic lower and upper bounds on the maximum order of half graphs, parameterized on the distance, in the following classes of sparse graphs: planar graphs, graphs with bounded maximum degree, graphs with bounded pathwidth or treewidth, and graphs excluding a fixed clique as a minor. The most significant part of our work is the upper bound for planar graphs. Here, we employ techniques of structural graph theory to analyze semi-ladders in planar graphs through the notion of cages, which expose a topological structure in semi-ladders. As an essential building block of this proof, we also state and prove a new structural result, yielding a fully polynomial bound on the neighborhood complexity in the class of planar graphs., Comment: 83 pages, 32 figures
- Published
- 2021
- Full Text
- View/download PDF
49. Approximating Pathwidth for Graphs of Small Treewidth
- Author
-
Bartosz Walczak, Carla Groenland, Gwenaël Joret, and Wojciech Nadara
- Subjects
FOS: Computer and information sciences ,Mathematics (miscellaneous) ,Discrete Mathematics (cs.DM) ,Computer Science - Data Structures and Algorithms ,FOS: Mathematics ,treewidth ,pathwidth ,Mathematics - Combinatorics ,Théorie des graphes ,Data Structures and Algorithms (cs.DS) ,Combinatorics (math.CO) ,Computer Science - Discrete Mathematics - Abstract
We describe a polynomial-time algorithm which, given a graph $G$ with treewidth $t$, approximates the pathwidth of $G$ to within a ratio of $O(t\sqrt{\log t})$. This is the first algorithm to achieve an $f(t)$-approximation for some function $f$. Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a subdivision of a large complete binary tree. Specifically, we show that every graph with pathwidth at least $th+2$ has treewidth at least $t$ or contains a subdivision of a complete binary tree of height $h+1$. The bound $th+2$ is best possible up to a multiplicative constant. This result was motivated by, and implies (with $c=2$), the following conjecture of Kawarabayashi and Rossman (SODA'18): there exists a universal constant $c$ such that every graph with pathwidth $\Omega(k^c)$ has treewidth at least $k$ or contains a subdivision of a complete binary tree of height $k$. Our main technical algorithm takes a graph $G$ and some (not necessarily optimal) tree decomposition of $G$ of width $t'$ in the input, and it computes in polynomial time an integer $h$, a certificate that $G$ has pathwidth at least $h$, and a path decomposition of $G$ of width at most $(t'+1)h+1$. The certificate is closely related to (and implies) the existence of a subdivision of a complete binary tree of height $h$. The approximation algorithm for pathwidth is then obtained by combining this algorithm with the approximation algorithm of Feige, Hajiaghayi, and Lee (STOC'05) for treewidth., Comment: v4: small changes following further comments from a referee. v3: revised following referees' comments, corrects a serious error in the previous version
- Published
- 2021
50. 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
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.