Yuli Ye
Skip Abstract Section
Abstract
In this article we study graphs with inductive neighborhood properties. Let P be a graph property, a graph G = (V, E) with n vertices is said to have an inductive neighborhood property with respect to P if there is an ordering of vertices v1, …, vn such that the property P holds on the induced subgraph G[N(vi)∩ Vi], where N(vi) is the neighborhood of vi and Vi = {vi, …, vn}. It turns out that if we take P as a graph with maximum independent set size no greater than k, then this definition gives a natural generalization of both chordal graphs and (k + 1)-claw-free graphs. We refer to such graphs as inductive k-independent graphs. We study properties of such families of graphs, and we show that several natural classes of graphs are inductive k-independent for small k. In particular, any intersection graph of translates of a convex object in a two dimensional plane is an inductive 3-independent graph; furthermore, any planar graph is an inductive 3-independent graph. For any fixed constant k, we develop simple, polynomial time approximation algorithms for inductive k-independent graphs with respect to several well-studied NP-complete problems. Our generalized formulation unifies and extends several previously known results.
- Addario-Berry, L., Kennedy, W., King, A. D., Li, Z., and Reed, B. 2010. Finding a maximum-weight induced k-partite subgraph of an i-triangulated graph. Discrete Appl. Math. 158, 7, 765--770. Google Scholar
Digital Library
- Akcoglu, K., Aspnes, J., DasGupta, B., and Kao, M.-Y. 2002. Opportunity-cost algorithms for combinatorial auctions. In Applied Optimization 74: Computational Methods in Decision-Making, Economics and Finance, E. J. Kontoghiorghes, B. Rustem, and S. Siokos, Eds., Kluwer Academic Publishers, 455--479.Google Scholar
- Alon, N., Feige, U., Wigderson, A., and Zuckerman, D. 1995. Derandomized graph products. Comput. Complexity 5, 60--75. Google ScholarDigital Library
- Baker, B. S. 1994. Approximation algorithms for np-complete problems on planar graphs. J. ACM 41, 153--180. Google ScholarDigital Library
- Bar-Noy, A., Bar-Yehuda, R., Freund, A., (Seffi) Naor, J., and Schieber, B. 2001. A unified approach to approximating resource allocation and scheduling. J. ACM 48, 1069--1090. Google ScholarDigital Library
- Bar-Noy, A. and Guha, S. 2002a. Approximating the throughput of multiple machines in real-time scheduling. SIAM J. Comput. 31, 331--352. Google ScholarDigital Library
- Bar-Noy, A. and Guha, S. 2002b. Approximating the throughput of multiple machines in real-time scheduling. SIAM J. Comput. 31, 331--352. Google ScholarDigital Library
- Bar-Yehuda, R. and Even, S. 1982. On approximating a vertex cover for planar graphs. In Proceedings of the 14th Annual ACM Symposium on Theory of Computing (STOC). 303--309. Google ScholarDigital Library
- Bar-Yehuda, R. and Even, S. 1985. A local-ratio theorem for approximating the weighted vertex cover problem. In Analysis and Design of Algorithms for Combinatorial Problems, G. Ausiello and M. Lucertini, Eds., North-Holland Mathematics Studies Series, vol. 109, North-Holland, 27--45.Google Scholar
- Berman, P. 2000. A d/2 approximation for maximum weight independent set in d-claw free graphs. Nordic J. Comput. 7, 178--184. Google ScholarDigital Library
- Berman, P. and DasGupta, B. 2000. Improvements in throughout maximization for real-time scheduling. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC). 680--687. Google ScholarDigital Library
- Berman, P. and DasGupta, B. 2002. A simple approximation algorithm for nonoverlapping local alignments (weighted independent sets of axis parallel rectangles). Biocomput. 1, 129--138.Google ScholarCross Ref
- Berman, P., DasGupta, B., and Muthukrishnan, S. 2002. Simple approximation algorithm for nonoverlapping local alignments. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 677--678. Google ScholarDigital Library
- Borodin, A., Cashman, D., and Magen, A. 2005. How well can primal-dual and local-ratio algorithms perform? In Automata, Languages and Programming, L. Caires, G. Italiano, L. Monteiro, C. Palamidessi, and M. Yung, Eds., Lecture Notes in Computer Science, vol. 3580, Springer Berlin, 943--955. Google ScholarDigital Library
- Borodin, A., Nielsen, M. N., and Rackoff, C. 2002. (incremental) priority algorithms. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 752--761. Google ScholarDigital Library
- Chakaravarthy, V. T. and Roy, S. 2009. Approximating maximum weight k-colorable subgraphs in chordal graphs. Inform. Proc. Lett. 109, 7, 365--368. Google ScholarDigital Library
- Chuzhoy, J., Ostrovsky, R., and Rabani, Y. 2006. Approximation algorithms for the job interval selection problem and related scheduling problems. Math. Oper. Res. 31, 730--738. Google ScholarDigital Library
- Corneil, D. G., Olariu, S., and Stewart, L. 1997. Asteroidal triple-free graphs. SIAM J. Discret. Math. 10, 399--430. Google ScholarDigital Library
- De Figueiredo, C. M. H. and Maffray, F. 2004. Optimizing bull-free perfect graphs. SIAM J. Discrete Math. 18, 2, 226--240. Google ScholarDigital Library
- Downey, R. G. and Fellows, M. R. 1995. Fixed-parameter tractability and completeness II: On completeness for w{1}. Theoret. Comput. Sci. 141, 1-2, 109--131. Google ScholarDigital Library
- Edmonds, J. 1965. Paths, trees, and flowers. Canad. J. Math. 17, 449--467.Google ScholarCross Ref
- Edmonds, J. 1971. Matroids and the greedy algorithm. Math. Program. 1, 127--136.Google ScholarDigital Library
- Eisenbrand, F. and Grandoni, F. 2004. On the complexity of fixed parameter clique and dominating set. Theor. Comput. Sci. 326, 57--67. Google ScholarDigital Library
- Erlebach, T., Jansen, K., and Seidel, E. 2005. Polynomial-time approximation schemes for geometric intersection graphs. SIAM J. Comput. 34, 1302--1323. Google ScholarDigital Library
- Feige, U. and Kilian, J. 1996. Zero knowledge and the chromatic number. In Proceedings of the 11th Annual IEEE Conference on Computational Complexity. 278--287. Google ScholarDigital Library
- Gavril, F. 1972. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 180--187.Google Scholar
- Grötschel, M., Lovász, L., and Schrijver, A. 1981. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169--197.Google ScholarCross Ref
- Halldórsson, M. 1999. Approximations of weighted independent set and hereditary subset problems. In Computing and Combinatorics, T. Asano, H. Imai, D. Lee, S.-i. Nakano, and T. Tokuyama, Eds., Lecture Notes in Computer Science, vol. 1627, Springer Berlin, 261--270. Google ScholarDigital Library
- Hochbaum, D. S. 1983. Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Appl. Math. 6, 3, 243--254.Google ScholarCross Ref
- Itai, A. and Rodeh, M. 1977. Finding a minimum circuit in a graph. In Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC). 1--10. Google ScholarDigital Library
- Jamison, R. E. and Mulder, H. M. 2000. Tolerance intersection graphs on binary trees with constant tolerance 3. Discrete Math. 215, 1-3, 115--131. Google ScholarDigital Library
- Jensen, T. R. and Toft, B. 1995. Graph Coloring Problems. Wiley-Interscience, New York.Google Scholar
- Kako, A., Ono, T., Hirata, T., and Halldórsson, M. M. 2009. Approximation algorithms for the weighted independent set problem in sparse graphs. Discrete Appl. Math. 157, 617--626. Google ScholarDigital Library
- Kammer, F., Tholey, T., and Voepel, H. 2009. Approximation algorithms for intersection graphs. Tech. rep., Institut für Informatik, Universitat Augsburg.Google Scholar
- Khot, S. and Regev, O. 2003. Vertex cover might be hard to approximate to within 2-epsilon. In Proceedings of the 18th Annual IEEE Conference on Computational Complexity. 379--386.Google Scholar
- Kim, S. J., Kostochka, A., and Nakprasit, K. 2004. On the chromatic number of intersection graphs of convex sets in the plane. Electron. J. Combinat. 11, 52.Google ScholarCross Ref
- Korte, B. and Lovász, L. 1981. Mathematical structures underlying greedy algorithms. In Proceedings of the International FCT-Conference on Fundamentals of Computation Theory (FCT). 205--209. Google ScholarDigital Library
- Lekkerkerker, C. G. and Boland, J. C. 1962. Representation of a finite graph by a set of intervals on the real line. Fund. Math. 51, 45--64.Google ScholarCross Ref
- Marathe, M., Breu, H., I, I I, H. B. H., Ravi, S. S., and Rosenkrantz, D. J. 1995. Simple heuristics for unit disk graphs. Netw. 25, 59--68.Google ScholarCross Ref
- Minty, G. J. 1980. On maximal independent sets of vertices in claw-free graphs. J. Combinat. Theory, Series B 28, 3, 284--304.Google ScholarCross Ref
- Nagashima, H. and Yamazaki, K. 2004. Hardness of approximation for non-overlapping local alignments. Discrete Appl. Math. 137, 293--309. Google ScholarDigital Library
- Nakamura, D. and Tamura, A. 2001. A revision of Minty's algorithm for finding a maximum weight stable set of a claw-free graph. J. Oper. Res. Soc. Japan 44, 2, 194--204.Google ScholarCross Ref
- Nemhauser, G. L. and Trotter, L. E. 1975. Vertex packings: Structural properties and algorithms. Math. Prog. 8, 232--248.Google ScholarDigital Library
- Nieberg, T., Hurink, J., and Kern, W. 2004. A robust PTAS for maximum weight independent sets in unit disk graphs. In Proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science. 214--221. Google ScholarDigital Library
- Spieksma, F. C. R. 1999. On the approximability of an interval scheduling problem. J. Sched. 2, 215--227.Google ScholarCross Ref
- Yannakakis, M. and Gavril, F. 1987. The maximum k-colorable subgraph problem for chordal graphs. Inform. Proc. Lett. 24, 2, 133--137. Google ScholarDigital Library
Index Terms
- Elimination graphs
Recommendations
Well-partitioned chordal graphs
AbstractWe introduce a new subclass of chordal graphs that generalizes the class of split graphs, which we call well-partitioned chordal graphs. A connected graph G is a well-partitioned chordal graph if there exist a partition P of the vertex ...
Polynomial-time algorithms for Subgraph Isomorphism in small graph classes of perfect graphs
Given two graphs, Subgraph Isomorphism is the problem of deciding whether the first graph (the base graph) contains a subgraph isomorphic to the second one (the pattern graph). This problem is NP-complete even for very restricted graph classes such as ...
Map graphs having witnesses of large girth
AbstractA half-square of a bipartite graph B = ( X , Y , E B ) has one color class of B as vertex set, say X; two vertices are adjacent whenever they have a common neighbor in Y. If G = ( V , E G ) is the half-square of a planar bipartite ...
Comments