|
|
Acuna, V., Ferreira, C. E., Freire, A. S., & Moreno, E. (2014). Solving the maximum edge biclique packing problem on unbalanced bipartite graphs. Discret Appl. Math., 164, 2–12.
Abstract: A biclique is a complete bipartite graph. Given an (L, R)-bipartite graph G = (V, E) and a positive integer k, the maximum edge biclique packing (num') problem consists in finding a set of at most k bicliques, subgraphs of G, such that the bicliques are vertex disjoint with respect to a subset of vertices S, where S E {V, L, R}, and the number of edges inside the bicliques is maximized. The maximum edge biclique (mEs) problem is a special case of the MEBP problem in which k = 1. Several applications of the MEB problem have been studied and, in this paper, we describe applications of the MEBP problem in metabolic networks and product bundling. In these applications the input graphs are very unbalanced (i.e., IRI is considerably greater than ILI), thus we consider carefully this property in our models. We introduce a new formulation for the MEB problem and a branch-and-price scheme, using the classical branch rule by Ryan and Foster, for the MEBP problem. Finally, we present computational experiments with instances that come from the described applications and also with randomly generated instances. (C) 2011 Elsevier B.V. All rights reserved.
|
|
|
|
Aracena, J., Demongeot, J., Fanchon, E., & Montalva, M. (2013). On the number of update digraphs and its relation with the feedback arc sets and tournaments. Discret Appl. Math., 161(10-11), 1345–1355.
Abstract: An update digraph corresponds to a labeled digraph that indicates a relative order of its nodes introduced to define equivalence classes of deterministic update schedules yielding the same dynamical behavior of a Boolean network. In Aracena et al. [1], the authors exhibited relationships between update digraphs and the feedback arc sets of a given digraph G. In this paper, we delve into the study of these relations. Specifically, we show differences and similarities between both sets through increasing and decreasing monotony properties in terms of their structural characteristics. Besides, we prove that these sets are equivalent if and only if all the digraph circuits are cycles. On the other hand, we characterize the minimal feedback arc sets of a given digraph in terms of their associated update digraphs. In particular, for complete digraphs, this characterization shows a close relation with acyclic tournaments. For the latter, we show that the size of the associated equivalence classes is a power of two. Finally, we determine exactly the number of update digraphs associated to digraphs containing a tournament. (C) 2013 Elsevier B.V. All rights reserved.
|
|
|
|
Espinoza, D., Goycoolea, M., & Moreno, E. (2015). The precedence constrained knapsack problem: Separating maximally violated inequalities. Discret Appl. Math., 194, 65–80.
Abstract: We consider the problem of separating maximally violated inequalities for the precedence constrained knapsack problem. Though we consider maximally violated constraints in a very general way, special emphasis is placed on induced cover inequalities and induced clique inequalities. Our contributions include a new partial characterization of maximally violated inequalities, a new safe shrinking technique, and new insights on strengthening and lifting. This work follows on the work of Boyd (1993), Park and Park (1997), van de Leensel et al. (1999) and Boland et al. (2011). Computational experiments show that our new techniques and insights can be used to significantly improve the performance of cutting plane algorithms for this problem. (C) 2015 Elsevier B.V. All rights reserved.
|
|
|
|
Feuilloley, L., Fraigniaud, P., Montealegre, P., Rapaport, I., Remila, E., & Todinca, I. (2023). Local certification of graphs with bounded genus. Discret Appl. Math., 325, 9–36.
Abstract: Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for automatically translating standard centralized interactive protocols to distributed interactive protocols, as introduced by Kol, Oshman, and Saxena [PODC 2018]. In particular, by using this compiler, every linear-time algorithm for deciding the membership to some fixed graph class can be translated into a dMAM(O(log n)) protocol for this class, that is, a distributed interactive protocol with O(log n)-bit proof size in n-node graphs, and three interactions between the (centralized) computationally-unbounded but non-trustable prover Merlin, and the (decentralized) randomized computationally-limited verifier Arthur. As a corol-lary, there is a dMAM(O(log n)) protocol for recognizing the class of planar graphs, as well as for recognizing the class of graphs with bounded genus.We show that there exists a distributed interactive protocol for recognizing the class of graphs with bounded genus performing just a single interaction, from the prover to the verifier, yet preserving proof size of O(log n) bits. This result also holds for the class of graphs with bounded non-orientable genus, that is, graphs that can be embedded on a non-orientable surface of bounded genus. The interactive protocols described in this paper are actually proof-labeling schemes, i.e., a subclass of interactive protocols, previously introduced by Korman, Kutten, and Peleg [PODC 2005]. In particular, these schn be computed a priori, at low cost, by the nodes themselves. Our results thus extend the recent proof-labeling scheme for planar graphs by Feuilloley et al. [PODC 2020], to graphs of bounded genus, and to graphs of bounded non-orientable genus.
|
|
|
|
Gaspers, S., Liedloff, M., Stein, M., & Suchan, K. (2015). Complexity of splits reconstruction for low-degree trees. Discret Appl. Math., 180, 89–100.
Abstract: Given a vertex-weighted tree T, the split of an edge em T is the minimum over the weights of the two trees obtained by removing e from T, where the weight of a tree is the sum of weights of its vertices. Given a set of weighted vertices V and a multiset of integers s, we consider the problem of constructing a tree on V whose splits correspond to s. The problem is known to be NP-complete, even when all vertices have unit weight and the maximum vertex degree of T is required to be at most 4. We show that the problem is strongly NP-complete when T is required to be a path, the problem is NP-complete when all vertices have unit weight and the maximum degree of T is required to be at most 3, and it remains NP-complete when all vertices have unit weight and T is required to be a caterpillar with unbounded hair length and maximum degree at most 3. We also design polynomial time algorithms for the variant where T is required to be a path and the number of distinct vertex weights is constant, and the variant where all vertices have unit weight and T has a constant number of leaves. The latter algorithm is not only polynomial when the number of leaves, k, is a constant, but also is a fixed-parameter algorithm for parameter k. Finally, we shortly discuss the problem when the vertex weights are not given but can be freely chosen by an algorithm. The considered problem is related to building libraries of chemical compounds used for drug design and discovery. In these inverse problems, the goal is to generate chemical compounds having desired structural properties, as there is a strong relation between structural invariants of the particles, such as the Wiener index and, less directly, the problem under consideration here, and physico-chemical properties of the substance. (C) 2014 Elsevier B.V. All rights reserved.
|
|
|
|
Kowalik, L., Pilipczuk, M., & Suchan, K. (2013). Towards optimal kernel for connected vertex cover in planar graphs. Discret Appl. Math., 161(7-8), 1154–1161.
Abstract: We study the parameterized complexity of the connected version of the vertex cover problem, where the solution set has to induce a connected subgraph. Although this problem does not admit a polynomial kernel for general graphs (unless NP subset of coNP/poly), for planar graphs Guo and Niedermeier [ICALP'08] showed a kernel with at most 14k vertices, subsequently improved by Wang et al. [MFCS'11] to 4k. The constant 4 here is so small that a natural question arises: could it be already an optimal value for this problem? In this paper we answer this question in the negative: we show a 11/3 k-vertex kernel for CONNECTED VERTEX COVER in planar graphs. We believe that this result will motivate further study in the search for an optimal kernel. In our analysis, we show an extension of a theorem of Nishizeki and Baybars [Takao Nishizeki, Ilker Baybars, Lower bounds on the cardinality of the maximum matchings of planar graphs, Discrete Mathematics 28 (3) (1979) 255-267] which might be of independent interest: every planar graph with n(>= 3) vertices of degree at least 3 contains a matching of cardinality at least n(>= 3)/3. (C) 2012 Elsevier B.V. All rights reserved.
|
|
|
|
Li, B., Moataz, F. Z., Nisse, N., & Suchan, K. (2018). Minimum size tree-decompositions. Discret Appl. Math., 245, 109–127.
Abstract: We study in this paper the problem of computing a tree-decomposition of a graph with width at most k and minimum number of bags. More precisely, we focus on the following problem: given a fixed k >= 1, what is the complexity of computing a tree-decomposition of width at most k with minimum number of bags in the class of graphs with treewidth at most k? We prove that the problem is NP-complete for any fixed k >= 4 and polynomial for k <= 2; for k = 3, we show that it is polynomial in the class of trees and 2-connected outerplanar graphs. (C) 2017 Elsevier B.V. All rights reserved.
|
|
|
|
Ortiz, C., & Villanueva, M. (2012). Maximal independent sets in caterpillar graphs. Discret Appl. Math., 160(3), 259–266.
Abstract: A caterpillar graph is a tree in which the removal of all pendant vertices results in a chordless path. In this work, we determine the number of maximal independent sets (mis) in caterpillar graphs. For a general graph, this problem is #P-complete. We provide a polynomial time algorithm to generate the whole family of mis in a caterpillar graph. We also characterize the independent graph (intersection graph of mis) and the clique graph (intersection graph of cliques) of complete caterpillar graphs. (C) 2011 Elsevier B.V. All rights reserved.
|
|
