{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:11:00Z","timestamp":1784110260229,"version":"3.55.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2020,3,11]],"date-time":"2020-03-11T00:00:00Z","timestamp":1583884800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,3,11]],"date-time":"2020-03-11T00:00:00Z","timestamp":1583884800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["CLASSIS"],"award-info":[{"award-number":["CLASSIS"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["MULTIVAL"],"award-info":[{"award-number":["MULTIVAL"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["DEC-2013\/11\/N\/ST6\/02706"],"award-info":[{"award-number":["DEC-2013\/11\/N\/ST6\/02706"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["DISTRUCT-648527"],"award-info":[{"award-number":["DISTRUCT-648527"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>For a graph <jats:italic>H<\/jats:italic>, a graph <jats:italic>G<\/jats:italic> is an <jats:italic>H<\/jats:italic>-graph if it is an intersection graph of connected subgraphs of some subdivision of <jats:italic>H<\/jats:italic>. <jats:italic>H<\/jats:italic>-graphs naturally generalize several important graph classes like interval graphs or circular-arc graph. This class was introduced in the early 1990s by B\u00edr\u00f3, Hujter, and Tuza. Recently, Chaplick et al. initiated the algorithmic study of <jats:italic>H<\/jats:italic>-graphs by showing that a number of fundamental optimization problems like M<jats:sc>aximum<\/jats:sc> C<jats:sc>lique<\/jats:sc>, M<jats:sc>aximum<\/jats:sc> I<jats:sc>ndependent<\/jats:sc> S<jats:sc>et<\/jats:sc>, or M<jats:sc>inimum<\/jats:sc> D<jats:sc>ominating<\/jats:sc> S<jats:sc>et<\/jats:sc> are solvable in polynomial time on <jats:italic>H<\/jats:italic>-graphs. We extend and complement these algorithmic findings in several directions. First we show that for every fixed <jats:italic>H<\/jats:italic>, the class of <jats:italic>H<\/jats:italic>-graphs is of logarithmically-bounded boolean-width (via mim-width). Pipelined with the plethora of known algorithms on graphs of bounded boolean-width, this describes a large class of problems solvable in polynomial time on <jats:italic>H<\/jats:italic>-graphs. We also observe that <jats:italic>H<\/jats:italic>-graphs are graphs with polynomially many minimal separators. Combined with the work of Fomin, Todinca and Villanger on algorithmic properties of such classes of graphs, this identify another wide class of problems solvable in polynomial time on <jats:italic>H<\/jats:italic>-graphs. The most fundamental optimization problems among the problems solvable in polynomial time on <jats:italic>H<\/jats:italic>-graphs are M<jats:sc>aximum<\/jats:sc> C<jats:sc>lique<\/jats:sc>, M<jats:sc>aximum<\/jats:sc> I<jats:sc>ndependent<\/jats:sc> S<jats:sc>et<\/jats:sc>, and M<jats:sc>inimum<\/jats:sc> D<jats:sc>ominating<\/jats:sc> S<jats:sc>et<\/jats:sc>. We provide a more refined complexity analysis of these problems from the perspective of parameterized complexity. We show that M<jats:sc>aximum<\/jats:sc> I<jats:sc>ndependent<\/jats:sc> S<jats:sc>et<\/jats:sc> and M<jats:sc>inimum<\/jats:sc> D<jats:sc>ominating<\/jats:sc> S<jats:sc>et<\/jats:sc> are W[1]-hard being parameterized by the size of <jats:italic>H<\/jats:italic> plus the size of the solution. On the other hand, we prove that when <jats:italic>H<\/jats:italic> is a tree, then M<jats:sc>inimum<\/jats:sc> D<jats:sc>ominating<\/jats:sc> S<jats:sc>et<\/jats:sc> is fixed-parameter tractable parameterized by the size of\u00a0<jats:italic>H<\/jats:italic>. For M<jats:sc>aximum<\/jats:sc> C<jats:sc>lique<\/jats:sc> we show that it admits a polynomial kernel parameterized by <jats:italic>H<\/jats:italic> and the solution size.<\/jats:p>","DOI":"10.1007\/s00453-020-00692-9","type":"journal-article","created":{"date-parts":[[2020,3,11]],"date-time":"2020-03-11T07:02:40Z","timestamp":1583910160000},"page":"2432-2473","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["On the Tractability of Optimization Problems on H-Graphs"],"prefix":"10.1007","volume":"82","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4646-7602","authenticated-orcid":false,"given":"Jean-Florent","family":"Raymond","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,3,11]]},"reference":[{"key":"692_CR1","unstructured":"Belmonte, R., Vatshelle, M.: On graph classes with logarithmic boolean-width. arXiv preprint, (2010) arXiv:1009.0216"},{"key":"692_CR2","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.tcs.2013.01.011","volume":"511","author":"R Belmonte","year":"2013","unstructured":"Belmonte, R., Vatshelle, M.: Graph classes with structured neighborhoods and algorithmic applications. Theor. Comput. Sci. 511, 54\u201365 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"692_CR3","doi-asserted-by":"crossref","unstructured":"Berry, Anne, Bordat, Jean-Paul, Cogis, Olivier: Generating all the minimal separators of a graph. In: Graph-Theoretic Concepts in Computer Science: 25th International Workshop, WG\u201999 Ascona, Switzerland, June 17\u201319, pp. 167\u2013172. Springer, Berlin (1999)","DOI":"10.1007\/3-540-46784-X_17"},{"issue":"1","key":"692_CR4","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0012-365X(92)90646-W","volume":"100","author":"M Bir\u00f3","year":"1992","unstructured":"Bir\u00f3, M., Hujter, M., Tuza, Z.: Precoloring extension. I. Interval graphs. Discret. Math. 100(1), 267\u2013279 (1992)","journal-title":"Discret. Math."},{"issue":"1","key":"692_CR5","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1137\/0211015","volume":"11","author":"KS Booth","year":"1982","unstructured":"Booth, K.S., Johnson, J.H.: Dominating sets in chordal graphs. SIAM J. Comput. 11(1), 191\u2013199 (1982)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"692_CR6","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1137\/S0097539799359683","volume":"31","author":"V Bouchitt\u00e9","year":"2001","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Treewidth and minimum fill-in: grouping the minimal separators. SIAM J. Comput. 31(1), 212\u2013232 (2001)","journal-title":"SIAM J. Comput."},{"issue":"39","key":"692_CR7","doi-asserted-by":"publisher","first-page":"5187","DOI":"10.1016\/j.tcs.2011.05.022","volume":"412","author":"B-M Bui-Xuan","year":"2011","unstructured":"Bui-Xuan, B.-M., Telle, J.A., Vatshelle, M.: Boolean-width of graphs. Theor. Comput. Sci. 412(39), 5187\u20135204 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"692_CR8","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.tcs.2013.01.009","volume":"511","author":"B-M Bui-Xuan","year":"2013","unstructured":"Bui-Xuan, B.-M., Telle, J.A., Vatshelle, M.: Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theor. Comput. Sci. 511, 66\u201376 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"692_CR9","unstructured":"Chaplick, S., T\u00f6pfer, M., Voborn\u00edk, J., Zeman, P.: On $$H$$-topological intersection graphs. In: International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 167\u2013179. Springer, Berlin (2017) arXiv:1608.02389"},{"key":"692_CR10","unstructured":"Chaplick, S., Zeman, P.: Combinatorial problems on $$H$$-graphs. In: The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB\u201917), Electronic Notes in Discrete Mathematics, vol. 61, pp. 223\u2013229 (2017). arXiv:1706.00575"},{"key":"692_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"692_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity. Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)"},{"issue":"1","key":"692_CR13","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F.A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"692_CR14","unstructured":"Fomin, F.V., Golovach, P.A., Raymond, J.-F.: On the tractability of optimization problems on $$H$$-graphs. In: Azar Y., Bast H., Herman G. (eds.) 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 30:1\u201330:14, Dagstuhl, Germany, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2018)"},{"key":"692_CR15","volume-title":"Kernelization: Theory of Parameterized Preprocessing","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, Cambridge (2019)"},{"issue":"1","key":"692_CR16","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/140964801","volume":"44","author":"FV Fomin","year":"2015","unstructured":"Fomin, F.V., Todinca, I., Villanger, Y.: Large induced subgraphs via triangulations and CMSO. SIAM J. Comput. 44(1), 54\u201387 (2015). arXiv:1309.1559","journal-title":"SIAM J. Comput."},{"issue":"2","key":"692_CR17","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F Gavril","year":"1972","unstructured":"Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1(2), 180\u2013187 (1972)","journal-title":"SIAM J. Comput."},{"key":"692_CR18","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Combin. Theory Ser. B 16, 47\u201356 (1974)","journal-title":"J. Combin. Theory Ser. B"},{"key":"692_CR19","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic graph theory and perfect graphs. In: Annals of Discrete Mathematics, vol. 57. Elsevier Science B.V., Amsterdam, second edition, With a foreword by Claude Berge (2004)","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"692_CR20","doi-asserted-by":"crossref","unstructured":"Habib, M., Stacho, J.: Polynomial-time algorithm for the leafage of chordal graphs. In: Algorithms\u2014ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7\u20139, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science, pp. 290\u2013300. Springer (2009)","DOI":"10.1007\/978-3-642-04128-0_27"},{"issue":"4","key":"692_CR21","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An n$${}^{\\text{5\/2 }}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"key":"692_CR22","unstructured":"Jaffke, L., Kwon, O., Str\u00f8mme, T.J.F., Telle, J.A.: Generalized distance domination problems and their complexity on graphs of bounded mim-width. In: Paul C., Pilipczuk M., (eds.) 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), volume 115 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 6:1\u20136:14, Dagstuhl, Germany, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2019)"},{"key":"692_CR23","unstructured":"Jaffke, L., Kwon, O., Telle, J.A.: Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width. In: Lokshtanov D., Nishimura N., (eds.) 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), volume\u00a089 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 21:1\u201321:13, Dagstuhl, Germany, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2018)"},{"key":"692_CR24","unstructured":"Jaffke, L., Kwon, O., Telle, J.A.: A note on the complexity of feedback vertex set parameterized by mim-width. arXiv preprint, (November 2017). arXiv:1711.05157"},{"key":"692_CR25","doi-asserted-by":"crossref","unstructured":"Kloks, T., Bodlaender, H., M\u00fcller, H., Kratsch, D.: Computing treewidth and minimum fill-in: all you need are the minimal separators. Algorithms\u2014ESA\u201993, pp. 260\u2013271 (1993)","DOI":"10.1007\/3-540-57273-2_61"},{"issue":"1","key":"692_CR26","doi-asserted-by":"publisher","first-page":"23","DOI":"10.7151\/dmgt.1061","volume":"18","author":"I-J Lin","year":"1998","unstructured":"Lin, I.-J., McKee, T., West, D.: The leafage of a chordal graph. Discuss. Math. Graph Theory 18(1), 23\u201348 (1998)","journal-title":"Discuss. Math. Graph Theory"},{"issue":"4","key":"692_CR27","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K Pietrzak","year":"2003","unstructured":"Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci. 67(4), 757\u2013771 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"692_CR28","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s00453-007-9148-9","volume":"52","author":"V Raman","year":"2008","unstructured":"Raman, V., Saurabh, S.: Short cycles make W[1]-hard problems hard: FPT algorithms for W[1]-hard problems in graphs with no short cycles. Algorithmica 52(2), 203\u2013225 (2008)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00692-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00692-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00692-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,11]],"date-time":"2021-03-11T00:12:07Z","timestamp":1615421527000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00692-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,11]]},"references-count":28,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["692"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00692-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,11]]},"assertion":[{"value":"10 September 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}