Recent zbMATH articles in MSC 05C85https://www.zbmath.org/atom/cc/05C852021-04-16T16:22:00+00:00WerkzeugThe scaling of the minimum sum of edge lengths in uniformly random trees.https://www.zbmath.org/1456.681282021-04-16T16:22:00+00:00"Esteban, Juan Luis"https://www.zbmath.org/authors/?q=ai:esteban.juan-luis"Ferrer-i-Cancho, Ramon"https://www.zbmath.org/authors/?q=ai:ferrer-i-cancho.ramon"Gómez-Rodríguez, Carlos"https://www.zbmath.org/authors/?q=ai:gomez-rodriguez.carlosExact exponential algorithms to find a tropical connected set of minimum size.https://www.zbmath.org/1456.682282021-04-16T16:22:00+00:00"Chapelle, Mathieu"https://www.zbmath.org/authors/?q=ai:chapelle.mathieu"Cochefert, Manfred"https://www.zbmath.org/authors/?q=ai:cochefert.manfred"Kratsch, Dieter"https://www.zbmath.org/authors/?q=ai:kratsch.dieter"Letourneur, Romain"https://www.zbmath.org/authors/?q=ai:letourneur.romain"Liedloff, Mathieu"https://www.zbmath.org/authors/?q=ai:liedloff.mathieuSummary: The input of the \textit{Tropical Connected Set} problem is a vertex-colored graph \(G=(V,E)\) and the task is to find a connected subset \(S\subseteq V\) of minimum size such that each color of \(G\) appears in \(S\). This problem is known to be NP-complete, even when restricted to trees of height at most three. We show that \textit{Tropical Connected Set} on trees has no subexponential-time algorithm unless the Exponential Time Hypothesis fails. This motivates the study of exact exponential algorithms to solve \textit{Tropical Connected Set}. We present an \(\mathcal {O}^*(1.5359^n)\) time algorithm for general graphs and an \(\mathcal {O}^*(1.2721^n)\) time algorithm for trees.
For the entire collection see [Zbl 1318.68014].The number of matchings in random graphs.https://www.zbmath.org/1456.051532021-04-16T16:22:00+00:00"Zdeborová, Lenka"https://www.zbmath.org/authors/?q=ai:zdeborova.lenka"Mézard, Marc"https://www.zbmath.org/authors/?q=ai:mezard.marcA \(14k\)-kernel for planar feedback vertex set via region decomposition.https://www.zbmath.org/1456.680642021-04-16T16:22:00+00:00"Bonamy, Marthe"https://www.zbmath.org/authors/?q=ai:bonamy.marthe"Kowalik, Łukasz"https://www.zbmath.org/authors/?q=ai:kowalik.lukaszSummary: We show a kernel of at most \(14k\) vertices for the \textsc{Planar Feedback Vertex Set} problem. This improves over the previous kernel of size bounded by \(97k\). Our algorithm has a few new reduction rules. However, our main contribution is an application of the region decomposition technique in the analysis of the kernel size.
For the entire collection see [Zbl 1318.68014].Caterpillars are antimagic.https://www.zbmath.org/1456.051382021-04-16T16:22:00+00:00"Lozano, Antoni"https://www.zbmath.org/authors/?q=ai:lozano.antoni"Mora, Mercè"https://www.zbmath.org/authors/?q=ai:mora.merce"Seara, Carlos"https://www.zbmath.org/authors/?q=ai:seara.carlos"Tey, Joaquín"https://www.zbmath.org/authors/?q=ai:tey.joaquinSummary: An antimagic labeling of a graph \(G\) is a bijection from the set of edges \(E(G)\) to \(\{1,2,\dots ,|E(G)|\}\), such that all vertex sums are pairwise distinct, where the vertex sum at vertex \(u\) is the sum of the labels assigned to the edges incident to \(u\). A graph is called antimagic when it has an antimagic labeling. \textit{N. Hartsfield} and \textit{G. Ringel} [Pearls in graph theory. A comprehensive introduction. Rev. and augmented ed. Orlando, FL: Academic Press (1994; Zbl 0823.05001), pp. 108--109] conjectured that every simple connected graph other than \(K_2\) is antimagic and the conjecture remains open even for trees. Here, we prove that caterpillars are antimagic by means of an \(O(n \log n)\) algorithm.Generalized \(k\)-core pruning process on directed networks.https://www.zbmath.org/1456.051632021-04-16T16:22:00+00:00"Zhao, Jin-Hua"https://www.zbmath.org/authors/?q=ai:zhao.jinhuaMinimum-weight combinatorial structures under random cost-constraints.https://www.zbmath.org/1456.051452021-04-16T16:22:00+00:00"Frieze, Alan"https://www.zbmath.org/authors/?q=ai:frieze.alan-m"Pegden, Wesley"https://www.zbmath.org/authors/?q=ai:pegden.wesley"Sorkin, Gregory B."https://www.zbmath.org/authors/?q=ai:sorkin.gregory-b"Tkocz, Tomasz"https://www.zbmath.org/authors/?q=ai:tkocz.tomaszSummary: Recall that \textit{S. Janson} [Comb. Probab. Comput. 8, No. 4, 347--361 (1999; Zbl 0934.05115)] showed that if the edges of the complete graph \(K_n\) are assigned exponentially distributed independent random weights, then the expected length of a shortest path between a fixed pair of vertices is asymptotically equal to \((\log n)/n\). We consider analogous problems where edges have not only a random length but also a random cost, and we are interested in the length of the minimum-length structure whose total cost is less than some cost budget. For several classes of structures, we determine the correct minimum length structure as a function of the cost-budget, up to constant factors. Moreover, we achieve this even in the more general setting where the distribution of weights and costs are arbitrary, so long as the density \(f(x)\) as \(x\to 0\) behaves like \(cx^\gamma\) for some \(\gamma\geq 0\); previously, this case was not understood even in the absence of cost constraints. We also handle the case where each edge has several independent costs associated to it, and we must simultaneously satisfy budgets on each cost. In this case, we show that the minimum-length structure obtainable is essentially controlled by the product of the cost thresholds.Parallel tempering for the planted clique problem.https://www.zbmath.org/1456.682332021-04-16T16:22:00+00:00"Angelini, Maria Chiara"https://www.zbmath.org/authors/?q=ai:angelini.maria-chiaraStable roommates problem with random preferences.https://www.zbmath.org/1456.825102021-04-16T16:22:00+00:00"Mertens, Stephan"https://www.zbmath.org/authors/?q=ai:mertens.stephanDiameter of colorings under Kempe changes.https://www.zbmath.org/1456.050552021-04-16T16:22:00+00:00"Bonamy, Marthe"https://www.zbmath.org/authors/?q=ai:bonamy.marthe"Heinrich, Marc"https://www.zbmath.org/authors/?q=ai:heinrich.marc"Ito, Takehiro"https://www.zbmath.org/authors/?q=ai:ito.takehiro"Kobayashi, Yusuke"https://www.zbmath.org/authors/?q=ai:kobayashi.yusuke"Mizuta, Haruka"https://www.zbmath.org/authors/?q=ai:mizuta.haruka"Mühlenthaler, Moritz"https://www.zbmath.org/authors/?q=ai:muhlenthaler.moritz"Suzuki, Akira"https://www.zbmath.org/authors/?q=ai:suzuki.akira"Wasa, Kunihiro"https://www.zbmath.org/authors/?q=ai:wasa.kunihiroSummary: Given a \(k\)-coloring of a graph \(G\), a Kempe-change for two colors \(a\) and \(b\) produces another \(k\)-coloring of \(G\), as follows: first choose a connected component in the subgraph of \(G\) induced by the two color classes of \(a\) and \(b\), and then swap the colors \(a\) and \(b\) in the component. Two \(k\)-colorings are called Kempe-equivalent if one can be transformed into the other by a sequence of Kempe-changes. We consider two problems, defined as follows: first, given two \(k\)-colorings of a graph \(G\), Kempe reachability asks whether they are Kempe-equivalent; and second, given a graph \(G\) and a positive integer \(k\), Kempe Connectivity asks whether any two \(k\)-colorings of \(G\) are Kempe-equivalent. We analyze the complexity of these problems from the viewpoint of graph classes. We prove that Kempe reachability is PSPACE-complete for any fixed \(k\ge 3\), and that it remains PSPACE-complete even when restricted to three colors and planar graphs of maximum degree six. Furthermore, we show that both problems admit polynomial-time algorithms on chordal graphs, bipartite graphs, and cographs. For each of these graph classes, we give a non-trivial upper bound on the number of Kempe-changes needed in order to certify that two \(k\)-colorings are Kempe-equivalent.
For the entire collection see [Zbl 1416.68009].Improved parameterized algorithms for network query problems.https://www.zbmath.org/1456.681332021-04-16T16:22:00+00:00"Pinter, Ron Y."https://www.zbmath.org/authors/?q=ai:pinter.ron-yair"Shachnai, Hadas"https://www.zbmath.org/authors/?q=ai:shachnai.hadas"Zehavi, Meirav"https://www.zbmath.org/authors/?q=ai:zehavi.meiravSummary: In the \textsc{Partial Information Network Query (PINQ)} problem, we are given a host graph \(H\), and a pattern \(\mathcal P\) whose topology is \textit{partially} known. We seek a subgraph of \(H\) that \textit{resembles} \(\mathcal{P}\). \textsc{PINQ} is a generalization of \textsc{Subgraph Isomorphism}, where the topology of \(\mathcal P\) is known, and \textsc{Graph Motif}, where the topology of \(\mathcal P\) is unknown. This generalization has important applications to bioinformatics, since it addresses the major challenge of analyzing biological networks in the absence of certain topological data. In this paper, we use a non-standard part-algebraic/part-combinatorial hybridization strategy to develop an exact parameterized algorithm as well as an FPT-approximation scheme for \textsc{PINQ}, allowing \textit{near resemblance} between \(H\) and \(\mathcal P\). We thus unify and significantly improve previous results related to network queries.
For the entire collection see [Zbl 1318.68014].Improved FPT algorithms for weighted independent set in bull-free graphs.https://www.zbmath.org/1456.680662021-04-16T16:22:00+00:00"Cray, Henri"https://www.zbmath.org/authors/?q=ai:cray.henri"Sau, Ignasi"https://www.zbmath.org/authors/?q=ai:sau.ignasiSummary: Very recently,
\textit{S. Thomassé} et al. [Lect. Notes Comput. Sci. 8747, 408--419 (2014; Zbl 1364.68232)]
have given an FPT algorithm for \textsc{Weighted Independent Set} in bull-free graphs parameterized by the weight of the solution, running in time \(2^{O(k^5)} \cdot n^9\). In this article we improve this running time to \(2^{O(k^2)} \cdot n^7\). As a byproduct, we also improve the previous Turing-kernel for this problem from \(O(k^5)\) to \(O(k^2)\). Furthermore, for the subclass of bull-free graphs without holes of length at most \(2p-1\) for \(p \geq 3\), we speed up the running time to \(2^{O(k \cdot k^{\frac{1}{p-1}})} \cdot n^7\). As \(p\) grows, this running time is asymptotically tight in terms of \(k\), since we prove that for each integer \(p \geq 3\), \textsc{Weighted Independent Set} cannot be solved in time \(2^{o(k)} \cdot n^{O(1)}\) in the class of \(\{\mathrm{bull},C_4,\ldots,C_{2p-1}\}\)-free graphs unless the ETH fails.
For the entire collection see [Zbl 1318.68014].Display sets of normal and tree-child networks.https://www.zbmath.org/1456.051542021-04-16T16:22:00+00:00"Döcker, Janosch"https://www.zbmath.org/authors/?q=ai:docker.janosch"Linz, Simone"https://www.zbmath.org/authors/?q=ai:linz.simone"Semple, Charles"https://www.zbmath.org/authors/?q=ai:semple.charlesSummary: Phylogenetic networks are leaf-labelled directed acyclic graphs that are used in computational biology to analyse and represent the evolutionary relationships of a set of species or viruses. In contrast to phylogenetic trees, phylogenetic networks have vertices of in-degree at least two that represent reticulation events such as hybridisation, lateral gene transfer, or reassortment. By systematically deleting various combinations of arcs in a phylogenetic network \(\mathcal{N}\), one derives a set of phylogenetic trees that are embedded in \(\mathcal{N}\). We recently showed that the problem of deciding if two binary phylogenetic networks embed the same set of phylogenetic trees is computationally hard, in particular, we showed it to be \(\Pi^P_2\)-complete. In this paper, we establish a polynomial-time algorithm for this decision problem if the initial two networks consist of a normal network and a tree-child network; two well-studied topologically restricted subclasses of phylogenetic networks, with normal networks being more structurally constrained than tree-child networks. The running time of the algorithm is quadratic in the size of the leaf sets.Diameter of colorings under Kempe changes.https://www.zbmath.org/1456.050562021-04-16T16:22:00+00:00"Bonamy, Marthe"https://www.zbmath.org/authors/?q=ai:bonamy.marthe"Heinrich, Marc"https://www.zbmath.org/authors/?q=ai:heinrich.marc"Ito, Takehiro"https://www.zbmath.org/authors/?q=ai:ito.takehiro"Kobayashi, Yusuke"https://www.zbmath.org/authors/?q=ai:kobayashi.yusuke"Mizuta, Haruka"https://www.zbmath.org/authors/?q=ai:mizuta.haruka"Mühlenthaler, Moritz"https://www.zbmath.org/authors/?q=ai:muhlenthaler.moritz"Suzuki, Akira"https://www.zbmath.org/authors/?q=ai:suzuki.akira"Wasa, Kunihiro"https://www.zbmath.org/authors/?q=ai:wasa.kunihiroSummary: Given a \(k\)-coloring of a graph \(G\), a Kempe-change for two colors \(a\) and \(b\) produces another \(k\)-coloring of \(G\), as follows: first choose a connected component in the subgraph of \(G\) induced by the two color classes of \(a\) and \(b\), and then swap the colors \(a\) and \(b\) in the component. Two \(k\)-colorings are called Kempe-equivalent if one can be transformed into the other by a sequence of Kempe-changes. We consider two problems, defined as follows: First, given two \(k\)-colorings of a graph \(G\), Kempe Reachability asks whether they are Kempe-equivalent; and second, given a graph \(G\) and a positive integer \(k\), Kempe Connectivity asks whether any two \(k\)-colorings of \(G\) are Kempe-equivalent. We analyze the complexity of these problems from the viewpoint of graph classes. We prove that Kempe Reachability is \(\mathsf{PSPACE} \)-complete for any fixed \(k \geq 3\), and that it remains \(\mathsf{PSPACE} \)-complete even when restricted to three colors and planar graphs of maximum degree six. Furthermore, we show that both problems admit polynomial-time algorithms on chordal graphs, bipartite graphs, and cographs. For each of these graph classes, we give a non-trivial upper bound on the number of Kempe-changes needed in order to certify that two \(k\)-colorings are Kempe-equivalent.