Treewidth versus clique number. II. Tree-independence number
References
[1]
T. Abrishami, M. Chudnovsky, S. Hajebi, S. Spirkl, Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth, Adv. Comb. (2022) 29 pp.
[2]
T. Abrishami, M. Chudnovsky, M. Pilipczuk, P. Rza̧żewski, P. Seymour, Induced subgraphs of bounded treewidth and the container method, in: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, PA, 2021, pp. 1948–1964.
[3]
B. Ahat, T. Ekim, Z.C. Taşkın, Integer programming formulations and benders decomposition for the maximum induced matching problem, INFORMS J. Comput. 30 (1) (2018) 43–56.
[4]
S. Arnborg, J. Lagergren, D. Seese, Easy problems for tree-decomposable graphs, J. Algorithms 12 (2) (1991) 308–340.
[5]
S. Arnborg, A. Proskurowski, Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Appl. Math. 23 (1) (1989) 11–24.
[6]
R. Belmonte, M. Vatshelle, Graph classes with structured neighborhoods and algorithmic applications, Theor. Comput. Sci. 511 (2013) 54–65.
[7]
W. Ben-Ameur, M.-A. Mohamed-Sidi, J. Neto, The k-separator problem: polyhedra, complexity and approximation results, J. Comb. Optim. 29 (1) (2015) 276–307.
[8]
M. Biró, M. Hujter, Zs. Tuza, Precoloring extension. I. Interval graphs, Discrete Math. 100 (1–3) (1992) 267–279.
[9]
J.R.S. Blair, B. Peyton, An introduction to chordal graphs and clique trees, in: Graph Theory and Sparse Matrix Computation, in: IMA Vol. Math. Appl., vol. 56, Springer, New York, 1993, pp. 1–29.
[10]
H. Bodlaender, J. Gustedt, J.A. Telle, Linear-time register allocation for a fixed number of registers, in: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, 1998, ACM, New York, 1998, pp. 574–583.
[11]
H.L. Bodlaender, A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput. 25 (6) (1996) 1305–1317.
[12]
H.L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theor. Comput. Sci. 209 (1–2) (1998) 1–45.
[13]
H.L. Bodlaender, A.M.C.A. Koster, Treewidth computations II. Lower bounds, Inf. Comput. 209 (7) (2011) 1103–1119.
[14]
H.L. Bodlaender, R.H. Möhring, The pathwidth and treewidth of cographs, SIAM J. Discrete Math. 6 (2) (1993) 181–188.
[15]
M. Bonamy, E. Bonnet, H. Déprés, L. Esperet, C. Geniet, C. Hilaire, S. Thomassé, A. Wesolek, Sparse graphs with bounded induced cycle packing number have logarithmic treewidth, in: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, PA, 2023, pp. 3006–3028.
[16]
E. Bonnet, C. Geniet, E.J. Kim, S. Thomassé, R. Watrigant, Twin-width III: max independent set, min dominating set, and coloring, in: 48th International Colloquium on Automata, Languages, and Programming, in: LIPIcs. Leibniz Int. Proc. Inform., vol. 198, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2021, Art. 35.
[17]
E. Bonnet, C. Geniet, E.J. Kim, S. Thomassé, R. Watrigant, Twin-width II: small classes, Comb. Theory 2 (2) (2022) 42 pp.
[18]
E. Bonnet, E.J. Kim, S. Thomassé, R. Watrigant, Twin-width I: tractable FO model checking, J. ACM 69 (1) (2022) 46 pp.
[19]
A. Brandstädt, V.B. Le, J.P. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, SIAM, Philadelphia, PA, 1999.
[20]
A. Brandstädt, R. Mosca, Maximum weight independent set for ℓclaw-free graphs in polynomial time, Discrete Appl. Math. 237 (2018) 57–64.
[21]
N. Brettell, J. Horsfield, A. Munaro, G. Paesani, D. Paulusma, Bounding the mim-width of hereditary graph classes, J. Graph Theory 99 (1) (2022) 117–151.
[22]
M. Briański, J. Davies, B. Walczak, Separating polynomial χ-boundedness from χ-boundedness, Combinatorica (2023),.
[23]
B.-M. Bui-Xuan, J.A. Telle, M. Vatshelle, Boolean-width of graphs, Theor. Comput. Sci. 412 (39) (2011) 5187–5204.
[24]
B.-M. Bui-Xuan, J.A. Telle, M. Vatshelle, Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems, Theor. Comput. Sci. 511 (2013) 66–76.
[25]
P. Buneman, A characterisation of rigid circuit graphs, Discrete Math. 9 (1974) 205–212.
[26]
K. Cameron, Induced matchings, Discrete Appl. Math. 24 (1–3) (1989) 97–102.
[27]
K. Cameron, P. Hell, Independent packings in structured graphs, Math. Program. 105 (2–3) (2006) 201–213.
[28]
P. Chalermsook, B. Walczak, Coloring and maximum weight independent set of rectangles, in: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, PA, 2021, pp. 860–868.
[29]
G.J. Chang, The weighted independent domination problem is NP-complete for chordal graphs, Discrete Appl. Math. 143 (1–3) (2004) 351–352.
[30]
S. Chaplick, F.V. Fomin, P.A. Golovach, D. Knop, P. Zeman, Kernelization of graph hamiltonicity: proper H-graphs, SIAM J. Discrete Math. 35 (2) (2021) 840–892.
[31]
S. Chaplick, M. Töpfer, J. Voborník, P. Zeman, On H-topological intersection graphs, in: Graph-Theoretic Concepts in Computer Science, in: Lecture Notes in Comput. Sci., vol. 10520, Springer, Cham, 2017, pp. 167–179.
[32]
S. Chaplick, M. Töpfer, J. Voborník, P. Zeman, On H-topological intersection graphs, Algorithmica 83 (11) (2021) 3281–3318.
[33]
S. Chaplick, P. Zeman, Combinatorial problems on H-graphs, Electron. Notes Discrete Math. 61 (2017) 223–229.
[34]
M. Chudnovsky, Induced subgraphs and tree decompositions, Talk at the Stony Brook Mathematics Colloquium, October 22, 2020 (online).
[35]
M. Chudnovsky, Induced subgraphs and tree decompositions, Talk at the Berlin Mathematical School, MATH+ Friday Colloquium, April 16, 2021 (online).
[36]
M. Chudnovsky, Induced subgraphs and tree decompositions, Talk at the Charles University, Faculty of Mathematics and Physics, Department of Applied Mathematics, Noon seminar, May 14, 2021 (online).
[37]
M. Chudnovsky, Induced subgraphs and tree decompositions, Invited talk at IWOCA 2021: 32nd International Workshop on Combinatorial Algorithms, 5-7 July 2021, Ottawa, Canada (online).
[38]
M. Chudnovsky, I. Penev, A. Scott, N. Trotignon, Substitution and χ-boundedness, J. Comb. Theory, Ser. B 103 (5) (2013) 567–586.
[39]
M. Chudnovsky, M. Pilipczuk, M. Pilipczuk, S. Thomassé, On the maximum weight independent set problem in graphs without induced cycles of length at least five, SIAM J. Discrete Math. 34 (2) (2020) 1472–1483.
[40]
M. Chudnovsky, M. Pilipczuk, M. Pilipczuk, S. Thomassé, Quasi-polynomial time approximation schemes for the maximum weight independent set problem in H-free graphs, in: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2020, pp. 2260–2278.
[41]
D.G. Corneil, Y. Perl, Clustering and domination in perfect graphs, Discrete Appl. Math. 9 (1) (1984) 27–39.
[42]
D.G. Corneil, U. Rotics, On the relationship between clique-width and treewidth, SIAM J. Comput. 34 (4) (2005) 825–847.
[43]
B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inf. Comput. 85 (1) (1990) 12–75.
[44]
B. Courcelle, J.A. Makowsky, U. Rotics, Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst. 33 (2) (2000) 125–150.
[45]
B. Courcelle, S. Olariu, Upper bounds to the clique width of graphs, Discrete Appl. Math. 101 (1–3) (2000) 77–114.
[46]
M. Cygan, F.V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, S. Saurabh, Parameterized Algorithms, Springer, Cham, 2015.
[47]
K.K. Dabrowski, M. Johnson, D. Paulusma, Clique-width for hereditary graph classes, in: Surveys in Combinatorics 2019, in: London Math. Soc. Lecture Note Ser., vol. 456, Cambridge Univ. Press, Cambridge, 2019, pp. 1–56.
[48]
Dallard, C.; Fomin, F.V.; Golovach, P.A.; Korhonen, T.; Milanič, M. (2022): Computing tree decompositions with small independence number. arXiv:2207.09993.
[49]
C. Dallard, M. Milanič, K. Štorgel, Treewidth versus clique number in graph classes with a forbidden structure, in: I. Adler, H. Müller (Eds.), Graph-Theoretic Concepts in Computer Science - 46th International Workshop, Revised Selected Papers, in: Lecture Notes in Computer Science, vol. 12301, WG 2020, Leeds, UK, June 24-26, 2020, Springer, 2020, pp. 92–105.
[50]
C. Dallard, M. Milanič, K. Štorgel, Treewidth versus clique number. I. Graph classes with a forbidden structure, SIAM J. Discrete Math. 35 (4) (2021) 2618–2646.
[51]
Dallard, C.; Milanič, M.; Štorgel, K. (2022): Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure. arXiv:2206.15092.
[52]
R. Diestel, M. Müller, Connected tree-width, Combinatorica 38 (2) (2018) 381–398.
[53]
G.A. Dirac, On rigid circuit graphs, Abh. Math. Semin. Univ. Hamb. 25 (1961) 71–76.
[54]
Y. Dourisboure, C. Gavoille, Tree-decompositions with bags of small diameter, Discrete Math. 307 (16) (2007) 2008–2029.
[55]
F.F. Dragan, E. Köhler, An approximation algorithm for the tree t-spanner problem on unweighted graphs via generalized chordal graphs, Algorithmica 69 (4) (2014) 884–905.
[56]
P. Duchet, Classical perfect graphs: an introduction with emphasis on triangulated and interval graphs, in: Topics on Perfect Graphs, in: North-Holland Math. Stud., vol. 88, North-Holland, Amsterdam, 1984, pp. 67–96.
[57]
L. Esperet, Graph colorings, flows and perfect matchings, Habilitation Thesis Université Grenoble Alpes, 2017.
[58]
M. Farber, Independent domination in chordal graphs, Oper. Res. Lett. 1 (4) (1981/82) 134–138.
[59]
U. Feige, M. Hajiaghayi, J.R. Lee, Improved approximation algorithms for minimum weight vertex separators, SIAM J. Comput. 38 (2) (2008) 629–657.
[60]
F.V. Fomin, P.A. Golovach, Subexponential parameterized algorithms and kernelization on almost chordal graphs, Algorithmica 83 (7) (2021) 2170–2214.
[61]
F.V. Fomin, P.A. Golovach, J.-F. Raymond, On the tractability of optimization problems on H-graphs, Algorithmica 82 (9) (2020) 2432–2473.
[62]
F.V. Fomin, T. Korhonen, Fast FPT-approximation of branchwidth, in: STOC '22—Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2022, pp. 886–899.
[63]
F.V. Fomin, I. Todinca, Y. Villanger, Large induced subgraphs via triangulations and CMSO, SIAM J. Comput. 44 (1) (2015) 54–87.
[64]
M.R. Garey, D.S. Johnson, G.L. Miller, C.H. Papadimitriou, The complexity of coloring circular arcs and chords, SIAM J. Algebraic Discrete Methods 1 (2) (1980) 216–227.
[65]
P. Gartland, D. Lokshtanov, Independent set on P k-free graphs in quasi-polynomial time, in: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science—FOCS 2020, IEEE Computer Soc., Los Alamitos, CA, 2020, pp. 613–624.
[66]
P. Gartland, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, P. Rzażewski, Finding large induced sparse subgraphs in C > t-free graphs in quasipolynomial time, in: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, Association for Computing Machinery, New York, NY, USA, 2021, pp. 330–341.
[67]
F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Comb. Theory, Ser. B 16 (1974) 47–56.
[68]
M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, vol. 57, second edition, Elsevier Science B.V., Amsterdam, 2004.
[69]
M. Grötschel, L. Lovász, A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics: Study and Research Texts, vol. 2, Springer-Verlag, Berlin, 1988.
[70]
A. Grzesik, T. Klimošová, M. Pilipczuk, M. Pilipczuk, Polynomial-time algorithm for maximum weight independent set on P 6-free graphs, ACM Trans. Algorithms 18 (1) (Jan 2022).
[71]
A. Gyárfás, Problems from the world surrounding perfect graphs, Zastos. Mat. 19 (3–4) (1987) 413–441.
[72]
A. Jacob, F. Panolan, V. Raman, V. Sahlot, Structural parameterizations with modulator oblivion, Algorithmica 84 (8) (2022) 2335–2357.
[73]
L. Jaffke, O.-j. Kwon, T.J.F. Strømme, J.A. Telle, Mim-width III. Graph powers and generalized distance domination problems, Theor. Comput. Sci. 796 (2019) 216–236.
[74]
P. Jégou, C. Terrioux, Tree-decompositions with connected clusters for solving constraint networks, in: International Conference on Principles and Practice of Constraint Programming, Springer, 2014, pp. 407–423.
[75]
D.Y. Kang, O.-j. Kwon, T.J.F. Strømme, J.A. Telle, A width parameter useful for chordal and co-comparability graphs, Theor. Comput. Sci. 704 (2017) 1–17.
[76]
R.M. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), 1972, pp. 85–103.
[77]
D. Kobler, U. Rotics, Edge dominating set and colorings on graphs with fixed clique-width, Discrete Appl. Math. 126 (2–3) (2003) 197–221.
[78]
P.K. Krause, Optimal register allocation in polynomial time, in: R. Jhala, K.D. Bosschere (Eds.), Compiler Construction - 22nd International Conference, CC 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, Proceedings, in: Lecture Notes in Computer Science, vol. 7791, ETAPS 2013, Rome, Italy, March 16-24, 2013, Springer, 2013, pp. 1–20.
[79]
E. Lee, Partitioning a graph into small pieces with applications to path transversal, Math. Program. 177 (1–2, Ser. A) (2019) 1–19.
[80]
S. Mengel, Lower bounds on the mim-width of some graph classes, Discrete Appl. Math. 248 (2018) 28–32.
[81]
Y. Orlovich, A. Dolgui, G. Finke, V. Gordon, F. Werner, The complexity of dissociation set problems in graphs, Discrete Appl. Math. 159 (13) (2011) 1352–1366.
[82]
S.-i. Oum, P. Seymour, Approximating clique-width and branch-width, J. Comb. Theory, Ser. B 96 (4) (2006) 514–528.
[83]
B.S. Panda, A. Pandey, J. Chaudhary, P. Dane, M. Kashyap, Maximum weight induced matching in some subclasses of bipartite graphs, J. Comb. Optim. 40 (3) (2020) 713–732.
[84]
M. Pilipczuk, M. Pilipczuk, P. Rza̧żewski, Quasi-polynomial-time algorithm for independent set in P t-free graphs via shrinking the space of induced paths, in: H.V. Le, V. King (Eds.), 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, SIAM, Philadelphia, PA, 2021, pp. 204–209.
[85]
V. Raghavan, J. Spinrad, Robust algorithms for restricted domains, J. Algorithms 48 (1) (2003) 160–172.
[86]
F.P. Ramsey, On a problem of formal logic, Proc. Lond. Math. Soc. (2) 30 (4) (1929) 264–286.
[87]
N. Robertson, P.D. Seymour, Graph minors. III. Planar tree-width, J. Comb. Theory, Ser. B 36 (1) (1984) 49–64.
[88]
N. Robertson, P.D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms 7 (3) (1986) 309–322.
[89]
D.J. Rose, R.E. Tarjan, G.S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput. 5 (2) (1976) 266–283.
[90]
P. Scheffler, What graphs have bounded tree-width?, in: Proceedings of the 7th Fischland Colloquium, III, vol. 41, Wustrow, 1988, 1990, pp. 31–38.
[91]
A. Scott, P. Seymour, A survey of χ-boundedness, J. Graph Theory 95 (3) (2020) 473–504.
[92]
P. Seymour, Tree-chromatic number, J. Comb. Theory, Ser. B 116 (2016) 229–237.
[93]
K. Skodinis, Efficient analysis of graphs with small minimal separators, in: Graph-Theoretic Concepts in Computer Science, in: Lecture Notes in Comput. Sci., vol. 1665, Ascona, 1999, Springer, Berlin, 1999, pp. 155–166.
[94]
J.P. Spinrad, Efficient Graph Representations, Fields Institute Monographs, vol. 19, American Mathematical Society, Providence, RI, 2003.
[95]
L. Sunil Chandran, A linear time algorithm for enumerating all the minimum and minimal separators of a chordal graph, in: Computing and Combinatorics, in: Lecture Notes in Comput. Sci., vol. 2108, Guilin, 2001, Springer, Berlin, 2001, pp. 308–317.
[96]
R.E. Tarjan, Decomposition by clique separators, Discrete Math. 55 (2) (1985) 221–232.
[97]
L. Vandenberghe, M.S. Andersen, Chordal graphs and semidefinite optimization, Found. Trends Optim. 1 (4) (2015) 241–433.
[98]
M. Vatshelle, New width parameters of graphs, PhD thesis University of Bergen, 2012.
[99]
J.R. Walter, Representations of chordal graphs as subtrees of a tree, J. Graph Theory 2 (3) (1978) 265–267.
[100]
D.B. West, Introduction to Graph Theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996.
[101]
M. Yannakakis, Node-deletion problems on bipartite graphs, SIAM J. Comput. 10 (2) (1981) 310–327.
[102]
N. Yolov, Minor-matching hypertree width, in: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2018, pp. 219–233.
[103]
J. You, J. Wang, Y. Cao, Approximate association via dissociation, in: Graph-Theoretic Concepts in Computer Science, in: Lecture Notes in Comput. Sci., vol. 9941, Springer, Berlin, 2016, pp. 13–24.
[104]
D. Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number, Theory Comput. 3 (2007) 103–128.
[105]
I.E. Zverovich, Satgraphs and independent domination. I, Theor. Comput. Sci. 352 (1–3) (2006) 47–56.
Index Terms
- Treewidth versus clique number. II. Tree-independence number
Index terms have been assigned to the content through auto-classification.
Recommendations
Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure
AbstractWe continue the study of ( tw , ω )-bounded graph classes, that is, hereditary graph classes in which the treewidth can only be large due to the presence of a large clique, with the goal of understanding the extent to which this property has ...
Independence number and clique minors
The Hadwiger number h(G) of a graph G is the maximum integer t such that Kt is a minor of G. Since X(G)·α(G)≥|G|, Hadwiger's conjecture implies that h(G)·α(G)≥|G|, where α(G) and |G| denote the independence number and the number of vertices of G, respectively. ...
Triangle-free graphs whose independence number equals the degree
In a triangle-free graph, the neighbourhood of every vertex is an independent set. We investigate the class S of triangle-free graphs where the neighbourhoods of vertices are maximum independent sets. Such a graph G must be regular of degree d=@a(G) and ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
The Author(s).
Publisher
Academic Press, Inc.
United States
Publication History
Published: 01 February 2024
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 04 Jan 2025