1,721,072 research outputs found
Erdos-Posa property of chordless cycles and its applications
No full textA chordless cycle, or equivalently a hole, in a graph G is an induced subgraph of G which is a cycle of length at least 4. We prove that the Erdos-Posa property holds for chordless cycles, which resolves the major open question concerning the Erdos-Posa property. Our proof for chordless cycles is constructive: in polynomial time, one can find either k + 1 vertex-disjoint chordless cycles, or c(1)k(2) log k + c(2) vertices hitting every chordless cycle for some constants c(1) and c(2). It immediately implies an approximation algorithm of factor 0(opt log opt) for CHORDAL VERTEX DELETION. We complement our main result by showing that chordless cycles of length at least P for any fixed l >= 5 do not have the Erdos-Posa property. (C) 2020 The Authors. Published by Elsevier Inc.
A tight meta-theorem for LOCAL certification of MSO2 properties within bounded treewidth graphs
No full textTwin-width I: Tractable FO Model Checking
No full textInspired by a width invariant defined on permutations by Guillemot and Marx [SODA'14], we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width graphs, map graphs, K-t-free unit d-dimensional ball graphs, posets with antichains of bounded size, and proper subclasses of dimension-2 posets all have bounded twin-width. On all these classes (except map graphs without geometric embedding) we show how to compute in polynomial time a sequence of d-contractions, witness that the twin-width is at most d. We show that FO model checking, that is deciding if a given first-order formula phi evaluates to true for a given binary structure G on a domain D, is FPT in vertical bar phi vertical bar on classes of bounded twin-width, provided the witness is given. More precisely, being given a d-contraction sequence for G, our algorithm runs in time f (d,vertical bar phi vertical bar)center dot vertical bar D vertical bar where f is a computable but non-elementary function. We also prove that bounded twin-width is preserved under FO interpretations and transductions (allowing operations such as squaring or complementing a graph). This unifies and significaiitly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes, such as the FPT algorithm on bounded-width posets by Gajarsky et al. [FOCS'15].
Shallow vertex minors, stability, and dependence
No full textStability and dependence are model-theoretic notions that have recently proved highly effective in the study of structural and algorithmic properties of hereditary graph classes, and are considered key notions for generalizing to hereditary graph classes the theory of sparsity developed for monotone graph classes (where an essential notion is that of nowhere dense class). The theory of sparsity was initially built on the notion of shallow minors and on the idea of excluding different sets of minors, depending on the depth at which these minors can appear.
In this paper, we follow a similar path, where shallow vertex minors replace shallow minors. In this setting, we provide a neat characterization of stable / dependent hereditary classes of graphs: A hereditary class of graphs
is dependent if and only if it does not contain all permutation graphs and, for each integer
, it excludes some split interval graph as a depth-
vertex minor; it is stable if and only if, for each integer
, it excludes some half-graph as a depth-
vertex minor.
A key ingredient in proving these results is the preservation of stability and dependence of a class when taking bounded depth shallow vertex minors. We extend this preservation result to binary structures and get, as a direct consequence, that bounded depth shallow vertex minors of graphs with bounded twin-width have bounded twin-width.
Flow-augmentation I: Directed graphs
No full textWe show a flow-augmentation algorithm in directed graphs: There exists a randomized polynomial-time algorithm that, given a directed graph G, two vertices s, t E V(G), and an integer k, adds (randomly) to G a number of arcs such that for every minimal st-cut Z in G of size at most k, with probability 2-poly(k) the set Z becomes a minimum st-cut in the resulting graph. We also provide a deterministic counterpart of this procedure. The directed flow-augmentation tool allows us to prove fixed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set whose parameterized complexity status was repeatedly posed as open problems: (1) CHAIN SAT, defined by Chitnis, Egri, and Marx [ESA'13, Algorithmica'17], (2) a number of weighted variants of classic directed cut problems, such as WEIGHTED st-CUT or WEIGHTED DIRECTED FEEDBACK VERTEX SET. By proving that CHAIN SAT is FPT, we confirm a conjecture of Chitnis, Egri, and Marx that, for any graph H, if the LIST H-COLORING problem is polynomial-time solvable, then the corresponding vertex-deletion problem is fixed-parameter tractable.
Nano-patterned SU-8 surface using nanosphere-lithography for enhanced neuronal cell growth
No full textMimicking the nanoscale surface texture of the extracellular matrix can affect the regulation of cellular behavior, including adhesion, differentiation, and neurite outgrowth. In this study, SU-8-based polymer surfaces with well-ordered nanowell arrays were fabricated using nanosphere lithography with polystyrene nanoparticles. We show that the SU-8 surface with nanowells resulted in similar neuronal development of rat pheochromocytoma (PC12) cells compared with an unpatterned poly-L-lysine (PLL)-coated SU-8 surface. Additionally, even after soaking the substrate in cell culture medium for two weeks, cells on the nanowell SU-8 surface showed long-term neurite outgrowth compared to cells on the PLL-coated SU-8 surface. The topographical surface modification of the nanowell array demonstrates potential as a replacement for cell adhesive material coatings such as PLL, for applications requiring long-term use of polymer-based implantable devices. © 2016 IOP Publishing Ltd.1
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
