Search

Topological features of polymer chains have been used as the key controlling mechanism for the physicochemical properties of hyperbranched polymers (HPs) and, therefore, provide a significant impet...

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

In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing W[1]-hardness proofs for these problems, since XNLP-hardness implies W[t]-hardness for all t. It also indicates, via a conjecture by Pilipczuk and Wrochna [ToCT 2018], that any XP algorithm for such problems is likely to require XP space. In particular, we show XNLP-completeness for natural problems parameterized by pathwidth, linear clique-width, and linear mim-width. The problems we consider are Independent Set, Dominating Set, Odd Cycle Transversal, (q-)Coloring, Max Cut, Maximum Regular Induced Subgraph, Feedback Vertex Set, Capacitated (Red-Blue) Dominating Set, and Bipartite Bandwidth.

Courcelle’s celebrated theorem states that all MSO-expressible properties can be decided in linear time on graphs of bounded treewidth. Unfortunately, the hidden constant implied by this theorem is a tower of exponentials whose height increases with each quantifier alternation in the formula. More devastatingly, this cannot be improved, under standard assumptions, even if we consider the much more restricted problem of deciding FO-expressible properties on trees. In this paper we revisit this well-studied topic and identify a natural special case where the dependence of Courcelle’s theorem can, in fact, be improved. Specifically, we show that all FO-expressible properties can be decided with an elementary dependence on the input formula, if the input graph has bounded pathwidth (rather than treewidth). This is a rare example of treewidth and pathwidth having different complexity behaviors. Our result is also in sharp contrast with MSO logic on graphs of bounded pathwidth, where it is known that the dependence has to be non-elementary, under standard assumptions. Our work builds upon, and generalizes, a corresponding meta-theorem by Gajarský and Hliněný for the more restricted class of graphs of bounded tree-depth., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 132:1-132:17

Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex set is fixed but the edge set changes over time, gained more and more attention. A path is time-respecting, or temporal, if it uses edges with non-decreasing time stamps. We investigate a basic constraint for temporal paths, where the time spent at each vertex must not exceed a given duration Δ, referred to as Δ-restless temporal paths. This constraint arises naturally in the modeling of real-world processes like packet routing in communication networks and infection transmission routes of diseases where recovery confers lasting resistance. While finding temporal paths without waiting time restrictions is known to be doable in polynomial time, we show that the "restless variant" of this problem becomes computationally hard even in very restrictive settings. For example, it is W[1]-hard when parameterized by the feedback vertex number or the pathwidth of the underlying graph. The main question thus is whether the problem becomes tractable in some natural settings. We explore several natural parameterizations, presenting FPT algorithms for three kinds of parameters: (1) output-related parameters (here, the maximum length of the path), (2) classical parameters applied to the underlying graph (e.g., feedback edge number), and (3) a new parameter called timed feedback vertex number, which captures finer-grained temporal features of the input temporal graph, and which may be of interest beyond this work., LIPIcs, Vol. 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020), pages 30:1-30:18

Given a graph G = ( V , E ) with a vertex ordering ≺, the fixed-order book thickness problem asks whether there is a page assignment σ such that 〈 ≺ , σ 〉 is a k-page book embedding of G. This problem is NP-complete even for any fixed k greater than 3. Recently, Bhore et al. (2019, 2020) [1] , [2] presented a parameterized algorithm with respect to the pathwidth κ of the vertex ordering. In this paper, we first re-analyze the running time for Bhore et al.'s algorithm, and prove a bound of 2 O ( κ 2 ) ⋅ | V | improving Bhore et al.'s bound of κ O ( κ 2 ) ⋅ | V | . Then, we show that fixed-order book thickness parameterized by the pathwidth of the vertex ordering does not admit a polynomial kernel unless NP ⊆ coNP/poly. Finally, we show that a generalized fixed-order book thickness problem, in which a budget of at most c crossings over all pages was given, admits a parameterized algorithm running in time ( c + 2 ) O ( κ 2 ) ⋅ | V | .

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

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.

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

Robertson and Seymour proved that the family of all graphs containing a fixed graph H as a minor has the Erdős-Posa property if and only if H is planar. We show that this is no longer true for the edge version of the Erdős-Posa property, and indeed even fails when H is an arbitrary subcubic tree of large pathwidth or a long ladder. This answers a question of Raymond, Sau and Thilikos.

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

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

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

In this paper we consider the parameterized complexity of two versions of a parallel machine scheduling problem with precedence delays, unit processing times and time windows. In the first version - with exact delays - we assume that the delay between two jobs must be exactly respected, whereas in the second version - with minimum delays - the delay between two jobs is a lower bound on the time between them. Two parameters are considered for this analysis: the pathwidth of the interval graph induced by the time windows and the maximum precedence delay value. We prove that our problems are para-NP-complete with respect to any of the two parameters and fixed-parameter tractable parameterized by the pair of parameters., LIPIcs, Vol. 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022), pages 21:1-21:21

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.

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.

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.

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

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.