An official website of the United States government
In this paper, we generalize the recently studied stochastic matching problem to more accurately model a significant medical process, kidney exchange, and several other applications. Up until now the stochastic matching problem that has been studied was as follows: given a graph G= (V,E), each edge is included in the realized sub-graph of G independently with probability pe, and the goal is to find a degree-bounded sub-graph Q of G that has an expected maximum matching that approximates the expected maximum matching of G. This model does not account for possibilities of vertex dropouts, which can be found in several applications, e.g. in kidney exchange when donors or patients opt out of the exchange process as well as in online freelancing and online dating when online profiles are found to be faked. Thus, we will study a more generalized model of stochastic matching in which vertices and edges are both realized independently with some probabilities pv, pe, respectively, which more accurately fits important applications than the previously studied model. We will discuss the first algorithms and analysis for this generalization of the stochastic matching model and prove that they achieve good approximation ratios. In particular, we show that the approximation factor of a natural algorithm for this problem is at least 0.6568 in unweighted graphs, and 1/2+ε in weighted graphs for some constant ε >0. We further improve our result for unweighted graphs to 2/3 using edge degree constrained sub-graphs (EDCS).
more »
« less
Rainbow Matchings of size $m$ in Graphs with Total Color Degree at least $2mn$
The existence of a rainbow matching given a minimum color degree, proper coloring, or triangle-free host graph has been studied extensively. This paper generalizes these problems to edge colored graphs with given total color degree. In particular, we find that if a graph $$G$$ has total color degree $2mn$ and satisfies some other properties, then $$G$$ contains a matching of size $$m$$. These other properties include $$G$$ being triangle-free, $$C_4$$-free, properly colored, or large enough.
more »
« less
- Award ID(s):
- 1839918
- PAR ID:
- 10220205
- Date Published:
- Journal Name:
- The Electronic Journal of Combinatorics
- Volume:
- 27
- Issue:
- 3
- ISSN:
- 1077-8926
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We study quantitative relationships between the triangle removal lemma and several of its variants. One such variant, which we call the triangle-free lemma , states that for each $$\epsilon>0$$ there exists M such that every triangle-free graph G has an $$\epsilon$$ -approximate homomorphism to a triangle-free graph F on at most M vertices (here an $$\epsilon$$ -approximate homomorphism is a map $$V(G) \to V(F)$$ where all but at most $$\epsilon \left\lvert{V(G)}\right\rvert^2$$ edges of G are mapped to edges of F ). One consequence of our results is that the least possible M in the triangle-free lemma grows faster than exponential in any polynomial in $$\epsilon^{-1}$$ . We also prove more general results for arbitrary graphs, as well as arithmetic analogues over finite fields, where the bounds are close to optimal.more » « less
-
A hole in a graph $$G$$ is an induced cycle of length at least four, and an even hole is a hole of even length. The diamond is the graph obtained from the complete graph $$K_4$$ by removing an edge. A pyramid is a graph consisting of a vertex $$a$$ called the apex and a triangle $$\{b_1, b_2, b_3\}$$ called the base, and three paths $$P_i$$ from $$a$$ to $$b_i$$ for $$1 \leq i \leq 3$$, all of length at least one, such that for $$i \neq j$$, the only edge between $$P_i \setminus \{a\}$$ and $$P_j \setminus \{a\}$$ is $$b_ib_j$$, and at most one of $$P_1$$, $$P_2$$, and $$P_3$$ has length exactly one. For a family $$\mathcal{H}$$ of graphs, we say a graph $$G$$ is $$\mathcal{H}$$-free if no induced subgraph of $$G$$ is isomorphic to a member of $$\mathcal{H}$$. Cameron, da Silva, Huang, and Vušković proved that (even hole, triangle)-free graphs have treewidth at most five, which motivates studying the treewidth of even-hole-free graphs of larger clique number. Sintiari and Trotignon provided a construction of (even hole, pyramid, $$K_4$$)-free graphs of arbitrarily large treewidth. Here, we show that for every $$t$$, (even hole, pyramid, diamond, $$K_t$$)-free graphs have bounded treewidth. The graphs constructed by Sintiari and Trotignon contain diamonds, so our result is sharp in the sense that it is false if we do not exclude diamonds. Our main result is in fact more general, that treewidth is bounded in graphs excluding certain wheels and three-path-configurations, diamonds, and a fixed complete graph. The proof uses “non-crossing decompositions” methods similar to those in previous papers in this series. In previous papers, however, bounded degree was a necessary condition to prove bounded treewidth. The result of this paper is the first to use the method of “non-crossing decompositions” to prove bounded treewidth in a graph class of unbounded maximum degree.more » « less
-
In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NP-hard and hard to approximate within a factor of n1−ε for any ε > 0. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In H-free graphs, that is, graphs not containing a fixed graph H as an induced subgraph, the problem is known to remain NP-hard and APX-hard whenever H contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of H is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomial-time solvability results for small graphs H such as P5, P6, the claw, or the fork. We prove that for every such “possibly tractable” graph H there exists an algorithm that, given an H-free graph G and an accuracy parameter ε > 0, finds an independent set in G of cardinality within a factor of (1 – ε) of the optimum in time exponential in a polynomial of log | V(G) | and ε−1. That is, we show that for every graph H for which Maximum Independent Set is not known to be APX-hard in H-free graphs, the problem admits a quasi-polynomial time approximation scheme in this graph class. Our algorithm works also in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set.more » « less
-
A _theta_ is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $$\mathcal{H}$$ of graphs, we say a graph $$G$$ is $$\mathcal{H}$$-_free_ if no induced subgraph of $$G$$ is isomorphic to a member of $$\mathcal{H}$$. We prove a conjecture of Sintiari and Trotignon, that there exists an absolute constant $$c$$ for which every (theta, triangle)-free graph $$G$$ has treewidth at most $$c\log (|V(G)|)$$. A construction by Sintiari and Trotignon shows that this bound is asymptotically best possible, and (theta, triangle)-free graphs comprise the first known hereditary class of graphs with arbitrarily large yet logarithmic treewidth.Our main result is in fact a generalization of the above conjecture, that treewidth is at most logarithmic in $|V(G)|$ for every graph $$G$$ excluding the so-called _three-path-configurations_ as well as a fixed complete graph. It follows that several NP-hard problems such as Stable Set, Vertex Cover, Dominating Set and $$k$$-Coloring (for fixed $$k$$) admit polynomial time algorithms in graphs excluding the three-path-configurations and a fixed complete graph.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.37236/8239
