304,893 research outputs found
On the Erdős-Pósa property for long holes in C_4-free graphs
No full textWe prove that there exists a function f(k)=O(k^2logk) such that for every C4-free graph G and every k∈N, G either contains k vertex-disjoint holes of length at least 6, or a set X of at most f(k) vertices such that G−X has no hole of length at least 6. This answers a question of Kim and Kwon [Erdős-Pósa property of chordless cycles and its applications. JCTB 2020
O pułapce „skojarzeniowej” w humanistyce. (Na marginesie uroszczenia S. Gałkowskiego w jego próbie „logicznej” wykładni Znanieckiego)
No full textAutor polemiki we wstępie wskazuje na zjawisko "reductio ad absurdum" koncepcji Znanieckiego w wykładni adresata jego krytyki. Dalej jest zarysowana ogólna perspektywa sprzeciwu wobec podejścia Stanisława Gałkowskiego. Przedstawiono także krytycyzm i pochwały wobec Znanieckiego ze strony autora polemiki. W tekście wskazuje się na pułapkę czytania epistemicznego jako etyczne nadużycie logiki. Wreszcie, zamiast zakończenia, mówi się o traktowaniu tradycji myśli humanistycznej i uczula na błędy interpretacyjne popełnione przez krytykowanego autora. Główny błąd polega na skojarzeniach czytelnika blokujących mu głębszy dostęp do znaczenia czytanej koncepcji.In his introduction the author of this polemic indicates the phenomenon of "reductio ad absurdum" of Znaniecki's conception in the exegesis of the addressee of this criticism. Next there is an outline sketched concerning the general perspective of disagreement against the approach by S. Gałkowski. There is also outlined criticism and appraisal towards Znaniecki by the author of this polemics. The text illustrates the trap of an epistemic reading as an ethical abuse of logics. Finally instead of a conclusion one is discussing the ways of treatement of the tradition of humanistic reflection and it warns against interpretative errors committed by the criticised author. The basic error is perceived as the result of domination of application of harmful associations of the leader blocking the way to deeper sense of the conception
Obstructions for bounded shrub-depth and rank-depth
No full textShrub-depth and rank-depth are dense analogues of the tree-depth of a graph.
It is well known that a graph has large tree-depth if and only if it has a long
path as a subgraph. We prove an analogous statement for shrub-depth and
rank-depth, which was conjectured by Hlin\v{e}n\'y, Kwon, Obdr\v{z}\'alek, and
Ordyniak [Tree-depth and vertex-minors, European J.~Combin. 2016]. Namely, we
prove that a graph has large rank-depth if and only if it has a vertex-minor
isomorphic to a long path. This implies that for every integer , the class
of graphs with no vertex-minor isomorphic to the path on vertices has
bounded shrub-depth.Comment: 19 pages, 5 figures; accepted to Journal of Combinatorial Theory Ser.
A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width
No full textWe give a first polynomial-time algorithm for (Weighted) Feedback Vertex Set on graphs of bounded maximum induced matching width (mim-width). Explicitly, given a branch decomposition of mim-width w, we give an n^{O(w)}-time algorithm that solves Feedback Vertex Set. This provides a unified algorithm for many well-known classes, such as Interval graphs and Permutation graphs, and furthermore, it gives the first polynomial-time algorithms for other classes of bounded mim-width, such as Circular Permutation and Circular k-Trapezoid graphs for fixed k. In all these classes the decomposition is computable in polynomial time, as shown by Belmonte and Vatshelle [Theor. Comput. Sci. 2013].
We show that powers of graphs of tree-width w-1 or path-width w and powers of graphs of clique-width w have mim-width at most w. These results extensively provide new classes of bounded mim-width. We prove a slight strengthening of the first statement which implies that, surprisingly, Leaf Power graphs which are of importance in the field of phylogenetic studies have mim-width at most 1. Given a tree decomposition of width w-1, a path decomposition of width w, or a clique-width w-expression of a graph G, one can for any value of k find a mim-width decomposition of its k-power in polynomial time, and apply our algorithm to solve Feedback Vertex Set on the k-power in time n^{O(w)}.
In contrast to Feedback Vertex Set, we show that Hamiltonian Cycle is NP-complete even on graphs of linear mim-width 1, which further hints at the expressive power of the mim-width parameter
„O strojach dawnych i o teraźniejszej tego wieku modzie” w ujęciu Jakuba Kazimierza Haura (1632–1709)
No full textThe article describes the work of Jakub Kazimierz Haur, entitled The Store or Treasury of Excellent Secrets of Land Economy, first published in 1693. It is a voluminous book of more than five hundred pages, in which the author presented a lot of information from various disciplines – agriculture, meteorology, astrology, medicine, hygiene, veterinary medicine, plastic arts, geography and law, as well as some practical instructions on educating children, reading, hunting or protection against witchcraft. The book also touches on issues relating to costumes, and the parts of the text devoted to these issues were divided by the author into three categories. The first part is devoted to the history of costumes, both in Poland and in other countries, the second part provides information on 17th century fashion in the territory of Poland, and the third part gives practical tips on the cleaning and care of clothes. The book explicitly shows the author’s passion for didacticism, reflected especially in the fragments in which he criticizes women for being excessively influenced by fashion and for blindly copying foreign culture. Nevertheless, the 17th-century author considers clothing to be an important part of everyday life and recommends proper care of it. It should be noted that some of the in the book on how to take care of clothes is still valid today.Artykuł przybliża dzieło Jakuba Kazimierza Haura zatytułowane Skład albo skarbiec znakomitych sekretów ekonomiej ziemiańskiej wydane po raz pierwszy w roku 1693. Jest to bardzo obszerna, licząca ponad pięćset stron, księga, w której autor zawarł szereg informacji z najróżniejszych dziedzin – rolnictwa, meteorologii, astrologii, medycyny, higieny, weterynarii, sztuk plastycznych, geografii i prawa, a także garść porad dotyczących kulinariów, wychowywania dzieci, czytelnictwa, łowiectwa czy zabezpieczania się przed czarami. Na kartach tego dzieła znalazła swoje miejsce także tematyka związana ze strojami. Te fragmenty tekstu podzielił autor na trzy kategorie. Pierwszą stanowią rozważania o historii ubioru zarówno w Polsce, jak i w innych krajach, drugą – informacje o XVII-wiecznej modzie na terenie Rzeczypospolitej, trzeci obszar rozważań Haura obejmuje natomiast praktyczne porady dotyczące czyszczenia odzieży i dbania o nią. W utworze wyraźnie daje o sobie znać skłonność autora do dydaktyzmu, szczególnie w tych fragmentach, w których krytykuje on Polki za nadmierne uleganie dyktatowi mody i ślepe naśladownictwo obcej kultury. Niezależnie jednak od tego XVII-wieczny autor postrzega strój jako ważny element codzienności i zaleca o niego dbać, przy czym niektóre zamieszczone w dziele porady dotyczące konserwacji odzieży nie straciły do dziś aktualności
Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms
No full textIt has long been known that Feedback Vertex Set can be solved in time 2^O(w log w)n^O(1) on graphs of treewidth w, but it was only recently that this running time was improved to 2^O(w)n^O(1), that is, to single-exponential parameterized by treewidth. We investigate which generalizations of Feedback Vertex Set can be solved in a similar running time. Formally, for a class of graphs P, Bounded P-Block Vertex Deletion asks, given a graph G on n vertices and positive integers k and d, whether G contains a set S of at most k vertices
such that each block of G-S has at most d vertices and is in P. Assuming that P is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of d:
- if P consists only of chordal graphs, then the problem can be solved in time 2^O(wd^2) n^{O}(1),
- if P contains a graph with an induced cycle of length ell>= 4, then the problem is not solvable in time 2^{o(w log w)} n^O(1)} even for fixed d=ell, unless the ETH fails.
We also study a similar problem, called Bounded P-Component Vertex Deletion, where the target graphs have connected components of small size instead of having blocks of small size, and present analogous results
- …
