{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T04:09:47Z","timestamp":1778299787117,"version":"3.51.4"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T00:00:00Z","timestamp":1778284800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T00:00:00Z","timestamp":1778284800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"University of Bergen"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We study the following\n                    <jats:sc>Independent Stable Set<\/jats:sc>\n                    problem. Let\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{G}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>G<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    be an undirected graph and\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{\\mathcal {M}} \\varvec{=} \\varvec{(V(G),} \\varvec{\\mathcal {I})}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>M<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mo>=<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:mi>V<\/mml:mi>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:mi>G<\/mml:mi>\n                              <mml:mo>)<\/mml:mo>\n                              <mml:mo>,<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>I<\/mml:mi>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    be a matroid whose elements are the vertices of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{G}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>G<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . For an integer\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{k}\\varvec{\\ge } \\varvec{1}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>k<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mo>\u2265<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mn>1<\/mml:mn>\n                            <\/mml:mrow>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , the task is to decide whether\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{G}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>G<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    contains a set\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{S}\\varvec{\\subseteq } \\varvec{V(G)}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>S<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mo>\u2286<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>V<\/mml:mi>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:mi>G<\/mml:mi>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    of size at least\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{k}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>k<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    which is independent (stable) in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{G}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>G<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    and independent in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{\\mathcal {M}}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>M<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . This problem generalizes several well-studied algorithmic problems, including\n                    <jats:sc>Rainbow Independent Set<\/jats:sc>\n                    ,\n                    <jats:sc>Rainbow Matching<\/jats:sc>\n                    , and\n                    <jats:sc>Bipartite Matching with Separation<\/jats:sc>\n                    . We show that when the matroid\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{\\mathcal {M}}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>M<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is represented by an independence oracle, then for any computable function\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{f}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>f<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , no algorithm can solve\n                    <jats:sc>Independent Stable Set<\/jats:sc>\n                    using\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{f(k)} \\varvec{\\cdot } \\varvec{n}^{\\varvec{o(k)}}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>f<\/mml:mi>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:mi>k<\/mml:mi>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mo>\u00b7<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mi>n<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mrow>\n                                <mml:mi>o<\/mml:mi>\n                                <mml:mo>(<\/mml:mo>\n                                <mml:mi>k<\/mml:mi>\n                                <mml:mo>)<\/mml:mo>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    calls to the oracle. On the other hand, when the graph\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{G}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>G<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is of degeneracy\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{d}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>d<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , then the problem is solvable in time\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{\\mathcal {O}}\\varvec{((d+1)}^{\\varvec{k}} \\varvec{\\cdot } \\varvec{n)}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>O<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mo>(<\/mml:mo>\n                                <mml:mo>(<\/mml:mo>\n                                <mml:mi>d<\/mml:mi>\n                                <mml:mo>+<\/mml:mo>\n                                <mml:mn>1<\/mml:mn>\n                                <mml:mo>)<\/mml:mo>\n                              <\/mml:mrow>\n                              <mml:mrow>\n                                <mml:mi>k<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mrow>\n                              <mml:mo>\u00b7<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>n<\/mml:mi>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , and hence is\n                    <jats:bold>FPT<\/jats:bold>\n                    parameterized by\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{d} \\varvec{+} \\varvec{k}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>d<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mo>+<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>k<\/mml:mi>\n                            <\/mml:mrow>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . Moreover, when the degeneracy\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{d}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>d<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is a constant (which is not a part of the input), the problem admits a kernel polynomial in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{k}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>k<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . More precisely, we prove that for every integer\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{d}\\varvec{\\ge } \\varvec{0}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>d<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mo>\u2265<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mn>0<\/mml:mn>\n                            <\/mml:mrow>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , the problem admits a kernelization algorithm that in time\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{n}^{\\varvec{\\mathcal {O}(d)}}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:msup>\n                            <mml:mrow>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>O<\/mml:mi>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:mi>d<\/mml:mi>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:msup>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    outputs an equivalent framework with a graph on\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{dk}^{\\varvec{\\mathcal {O}(d)}}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:msup>\n                            <mml:mrow>\n                              <mml:mi>dk<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>O<\/mml:mi>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:mi>d<\/mml:mi>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:msup>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    vertices. A lower bound complements this when\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{d}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>d<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is part of the input:\n                    <jats:sc>Independent Stable Set<\/jats:sc>\n                    does not admit a polynomial kernel when parameterized by\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{k} \\varvec{+} \\varvec{d}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>k<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mo>+<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>d<\/mml:mi>\n                            <\/mml:mrow>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    unless\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{{{\\,\\textrm{NP}\\,}}} \\varvec{\\subseteq } \\varvec{{{\\,\\textrm{coNP}\\,}}}\\varvec{\/}  {\\textbf {poly}}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mrow>\n                              <mml:mrow>\n                                <mml:mspace\/>\n                                <mml:mtext>NP<\/mml:mtext>\n                                <mml:mspace\/>\n                              <\/mml:mrow>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mo>\u2286<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mrow>\n                                <mml:mspace\/>\n                                <mml:mtext>coNP<\/mml:mtext>\n                                <mml:mspace\/>\n                              <\/mml:mrow>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mo>\/<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mi>poly<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . This lower bound holds even when\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{\\mathcal {M}}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>M<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is a partition matroid. Another set of results concerns the scenario when the graph\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{G}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>G<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is chordal. In this case, our computational lower bound excludes an\n                    <jats:bold>FPT<\/jats:bold>\n                    algorithm when the input matroid is given by its independence oracle. However, we demonstrate that\n                    <jats:sc>Independent Stable Set<\/jats:sc>\n                    can be solved in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{2}^{\\varvec{\\mathcal {O}(k)}}\\varvec{\\cdot } \\varvec{\\Vert \\mathcal {M}\\Vert }^{\\varvec{\\mathcal {O}(1)}}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mn>2<\/mml:mn>\n                              <\/mml:mrow>\n                              <mml:mrow>\n                                <mml:mi>O<\/mml:mi>\n                                <mml:mo>(<\/mml:mo>\n                                <mml:mi>k<\/mml:mi>\n                                <mml:mo>)<\/mml:mo>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mrow>\n                              <mml:mo>\u00b7<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mo>\u2016<\/mml:mo>\n                                <mml:mi>M<\/mml:mi>\n                                <mml:mo>\u2016<\/mml:mo>\n                              <\/mml:mrow>\n                              <mml:mrow>\n                                <mml:mi>O<\/mml:mi>\n                                <mml:mo>(<\/mml:mo>\n                                <mml:mn>1<\/mml:mn>\n                                <mml:mo>)<\/mml:mo>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    time when\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{\\mathcal {M}}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>M<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is a linear matroid given by its representation. In the same setting,\n                    <jats:sc>Independent Stable Set<\/jats:sc>\n                    does not have a polynomial kernel when parameterized by\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{k}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>k<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    unless\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{{{\\,\\textrm{NP}\\,}}} \\varvec{\\subseteq } \\varvec{{{\\,\\textrm{coNP}\\,}}}\\varvec{\/}  {\\textbf {poly}}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mrow>\n                              <mml:mrow>\n                                <mml:mspace\/>\n                                <mml:mtext>NP<\/mml:mtext>\n                                <mml:mspace\/>\n                              <\/mml:mrow>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mo>\u2286<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mrow>\n                                <mml:mspace\/>\n                                <mml:mtext>coNP<\/mml:mtext>\n                                <mml:mspace\/>\n                              <\/mml:mrow>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mo>\/<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mi>poly<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    .\n                  <\/jats:p>","DOI":"10.1007\/s00224-026-10277-8","type":"journal-article","created":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T03:16:31Z","timestamp":1778296591000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Stability in Graphs with Matroid Constraints"],"prefix":"10.1007","volume":"70","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tuukka","family":"Korhonen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,5,9]]},"reference":[{"issue":"3","key":"10277_CR1","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/s00493-007-2086-y","volume":"27","author":"R Aharoni","year":"2007","unstructured":"Aharoni, R., Berger, E., Ziv, R.: Independent systems of representatives in weighted graphs. Combinatorica 27(3), 253\u2013267 (2007)","journal-title":"Combinatorica"},{"key":"10277_CR2","doi-asserted-by":"publisher","unstructured":"Aharoni, R., Berger, E., Chudnovsky, M., Howard, D.M., Seymour, P.D.: Large rainbow matchings in general graphs. Eur. J. Comb. 79, 222\u2013227 (2019). https:\/\/doi.org\/10.1016\/j.ejc.2019.01.012","DOI":"10.1016\/j.ejc.2019.01.012"},{"issue":"3","key":"10277_CR3","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1002\/jgt.22989","volume":"104","author":"R Aharoni","year":"2023","unstructured":"Aharoni, R., Briggs, J., Kim, J., Kim, M.: Rainbow independent sets in certain classes of graphs. J. Graph Theory 104(3), 557\u2013584 (2023)","journal-title":"J. Graph Theory"},{"key":"10277_CR4","doi-asserted-by":"publisher","unstructured":"Alman, J., Williams, V.V.: A refined laser method and faster matrix multiplication. In: Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pp. 522\u2013539. SIAM (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.32","DOI":"10.1137\/1.9781611976465.32"},{"issue":"1","key":"10277_CR5","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discret. Math. 28(1), 277\u2013305 (2014). https:\/\/doi.org\/10.1137\/120880240","journal-title":"SIAM J. Discret. Math."},{"key":"10277_CR6","doi-asserted-by":"publisher","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Treewidth and minimum fill-in: Grouping the minimal separators. SIAM J. Comput. 31(1), 212\u2013232 (2001). https:\/\/doi.org\/10.1137\/S0097539799359683","DOI":"10.1137\/S0097539799359683"},{"key":"10277_CR7","doi-asserted-by":"publisher","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Listing all potential maximal cliques of a graph. Theor. Comput. Sci. 276(1\u20132), 17\u201332 (2002). https:\/\/doi.org\/10.1016\/S0304-3975(01)00007-X","DOI":"10.1016\/S0304-3975(01)00007-X"},{"key":"10277_CR8","doi-asserted-by":"publisher","unstructured":"Broersma, H., Kloks, T., Kratsch, D., M\u00fcller, H.: Independent sets in asteroidal triple-free graphs. SIAM J. Discret. Math. 12(2), 276\u2013287 (1999). https:\/\/doi.org\/10.1137\/S0895480197326346","DOI":"10.1137\/S0895480197326346"},{"key":"10277_CR9","doi-asserted-by":"publisher","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D.: D\u00e1niel Marx. Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, Marcin Pilipczuk (2015). ISBN 978-3-319-21274-6. https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"issue":"3","key":"10277_CR10","doi-asserted-by":"publisher","first-page":"43:1","DOI":"10.1145\/3108239","volume":"13","author":"M Cygan","year":"2017","unstructured":"Cygan, M., Grandoni, F., Hermelin, D.: Tight kernel bounds for problems on graphs with small degeneracy. ACM Trans. Algo. 13(3), 43:1-43:22 (2017). https:\/\/doi.org\/10.1145\/3108239","journal-title":"ACM Trans. Algo."},{"key":"10277_CR11","unstructured":"Diestel, R.: Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer (2012). ISBN 978-3-642-14278-9"},{"key":"10277_CR12","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer (2013). ISBN 978-1-4471-5558-4. https:\/\/doi.org\/10.1007\/978-1-4471-5559-1","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"10277_CR13","doi-asserted-by":"publisher","unstructured":"Drisko, A.A.: Transversals in row-latin rectangles. J. Combinator. Theory, Ser. A 84(2), 181\u2013195 (1998). ISSN 0097-3165. https:\/\/doi.org\/10.1006\/jcta.1998.2894. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0097316598928941","DOI":"10.1006\/jcta.1998.2894"},{"issue":"4","key":"10277_CR14","doi-asserted-by":"publisher","first-page":"29:1","DOI":"10.1145\/2886094","volume":"63","author":"FV Fomin","year":"2016","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4), 29:1-29:60 (2016). https:\/\/doi.org\/10.1145\/2886094","journal-title":"J. ACM"},{"key":"10277_CR15","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: theory of parameterized preprocessing. Cambridge University Press (2019)","DOI":"10.1017\/9781107415157"},{"issue":"1","key":"10277_CR16","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1137\/24M1632759","volume":"39","author":"FV Fomin","year":"2025","unstructured":"Fomin, F.V., Golovach, P.A., Korhonen, T., Stamoulis, G.: Computing paths of large rank in planar frameworks deterministically. SIAM J. Discret. Math. 39(1), 92\u2013118 (2025). https:\/\/doi.org\/10.1137\/24M1632759","journal-title":"SIAM J. Discret. Math."},{"key":"10277_CR17","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979). ISBN 0-7167-1044-7"},{"key":"10277_CR18","doi-asserted-by":"publisher","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Combinatorial Theory Ser. B 16, 47\u201356 (1974). ISSN 0095-8956. https:\/\/doi.org\/10.1016\/0095-8956(74)90094-x","DOI":"10.1016\/0095-8956(74)90094-x"},{"key":"10277_CR19","doi-asserted-by":"publisher","unstructured":"Graf, A., Haxell, P.: Finding independent transversals efficiently. Comb. Probab. Comput. 29(5), 780\u2013806 (2020). https:\/\/doi.org\/10.1017\/S0963548320000127","DOI":"10.1017\/S0963548320000127"},{"issue":"1","key":"10277_CR20","doi-asserted-by":"publisher","first-page":"1:1","DOI":"10.1145\/3474057","volume":"18","author":"A Graf","year":"2022","unstructured":"Graf, A., Harris, D.G., Haxell, P.: Algorithms for weighted independent transversals and strong colouring. ACM Trans. Algorithms 18(1), 1:1-1:16 (2022). https:\/\/doi.org\/10.1145\/3474057","journal-title":"ACM Trans. Algorithms"},{"key":"10277_CR21","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric algorithms and combinatorial optimization, volume\u00a02. Springer Sci. Bus. Media (2012)"},{"key":"10277_CR22","doi-asserted-by":"publisher","unstructured":"Gupta, S., Roy, S., Saurabh, S., Zehavi, M.: Parameterized algorithms and kernels for rainbow matching. Algorithmica 81(4), 1684\u20131698 (2019). https:\/\/doi.org\/10.1007\/s00453-018-0497-3","DOI":"10.1007\/s00453-018-0497-3"},{"key":"10277_CR23","doi-asserted-by":"publisher","unstructured":"Gupta, S., Roy, S., Saurabh, S., Zehavi, M.: Quadratic vertex kernel for rainbow matching. Algorithmica 82(4), 881\u2013897 (2020). https:\/\/doi.org\/10.1007\/s00453-019-00618-0","DOI":"10.1007\/s00453-019-00618-0"},{"key":"10277_CR24","doi-asserted-by":"publisher","unstructured":"Habib, M., McConnell, R.M., Paul, C., Viennot, L.: Lex-bfs and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theor. Comput. Sci. 234(1\u20132), 59\u201384 (2000). https:\/\/doi.org\/10.1016\/S0304-3975(97)00241-7","DOI":"10.1016\/S0304-3975(97)00241-7"},{"issue":"9","key":"10277_CR25","doi-asserted-by":"publisher","first-page":"777","DOI":"10.4169\/amer.math.monthly.118.09.777","volume":"118","author":"P Haxell","year":"2011","unstructured":"Haxell, P.: On forming committees. Am. Math. Mon. 118(9), 777\u2013788 (2011)","journal-title":"Am. Math. Mon."},{"key":"10277_CR26","doi-asserted-by":"publisher","unstructured":"Itai, A., Rodeh, M., Tanimoto, S.L.: Some matching problems for bipartite graphs. J. ACM 25(4), 517\u2013525 (1978). https:\/\/doi.org\/10.1145\/322092.322093","DOI":"10.1145\/322092.322093"},{"key":"10277_CR27","doi-asserted-by":"publisher","unstructured":"Jensen, P.M., Korte, B.: Complexity of matroid property algorithms. SIAM J. Comput. 11(1), 184\u2013190 (1982). https:\/\/doi.org\/10.1137\/0211014","DOI":"10.1137\/0211014"},{"key":"10277_CR28","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.dam.2021.04.007","volume":"312","author":"J Kim","year":"2022","unstructured":"Kim, J., Kim, M., Kwon, O.: Rainbow independent sets on dense graph classes. Discret. Appl. Math. 312, 45\u201351 (2022)","journal-title":"Discret. Appl. Math."},{"key":"10277_CR29","doi-asserted-by":"publisher","unstructured":"Kloks, T.: Treewidth, Computations and Approximations, volume 842 of Lecture Notes in Computer Science. Springer (1994). ISBN 3-540-58356-4. https:\/\/doi.org\/10.1007\/BFb0045375","DOI":"10.1007\/BFb0045375"},{"key":"10277_CR30","doi-asserted-by":"publisher","unstructured":"Le, V.B., Pfender, F.: Complexity results for rainbow matchings. Theor. Comput. Sci. 524, 27\u201333 (2014). https:\/\/doi.org\/10.1016\/j.tcs.2013.12.013","DOI":"10.1016\/j.tcs.2013.12.013"},{"issue":"2","key":"10277_CR31","doi-asserted-by":"publisher","first-page":"14:1","DOI":"10.1145\/3170444","volume":"14","author":"D Lokshtanov","year":"2018","unstructured":"Lokshtanov, D., Misra, P., Panolan, F., Saurabh, S.: Deterministic truncation of linear matroids. ACM Trans. Algorithms 14(2), 14:1-14:20 (2018). https:\/\/doi.org\/10.1145\/3170444","journal-title":"ACM Trans. Algorithms"},{"key":"10277_CR32","unstructured":"Lov\u00e1sz, L.: Flats in matroids and geometric graphs. In: Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Royal Holloway Coll., Egham, 1977), pp. 45\u201386 (1977)"},{"key":"10277_CR33","doi-asserted-by":"publisher","unstructured":"Lov\u00e1sz, L.: Graphs and geometry, volume\u00a065 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI (2019). ISBN 978-1-4704-5087-8. https:\/\/doi.org\/10.1090\/coll\/065","DOI":"10.1090\/coll\/065"},{"key":"10277_CR34","doi-asserted-by":"publisher","first-page":"106388","DOI":"10.1016\/J.IPL.2023.106388","volume":"182","author":"P Manurangsi","year":"2023","unstructured":"Manurangsi, P., Segal-Halevi, E., Suksompong, W.: On maximum bipartite matching with separation. Inf. Process. Lett. 182, 106388 (2023). https:\/\/doi.org\/10.1016\/J.IPL.2023.106388","journal-title":"Inf. Process. Lett."},{"key":"10277_CR35","doi-asserted-by":"publisher","unstructured":"Marx, D.: A parameterized view on matroid optimization problems. Theor. Comput. Sci. 410(44), 4471\u20134479 (2009). https:\/\/doi.org\/10.1016\/j.tcs.2009.07.027","DOI":"10.1016\/j.tcs.2009.07.027"},{"key":"10277_CR36","doi-asserted-by":"publisher","unstructured":"Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30(3), 417\u2013427 (1983). https:\/\/doi.org\/10.1145\/2402.322385","DOI":"10.1145\/2402.322385"},{"issue":"3","key":"10277_CR37","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GJ Minty","year":"1980","unstructured":"Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory Ser. B 28(3), 284\u2013304 (1980). https:\/\/doi.org\/10.1016\/0095-8956(80)90074-X","journal-title":"J. Comb. Theory Ser. B"},{"key":"10277_CR38","doi-asserted-by":"publisher","unstructured":"Oxley, J.: Matroid theory, volume\u00a021 of Oxford Graduate Texts in Mathematics. Oxford University Press, Oxford, second edition (2011). ISBN 978-0-19-960339-8. https:\/\/doi.org\/10.1093\/acprof:oso\/9780198566946.001.0001","DOI":"10.1093\/acprof:oso\/9780198566946.001.0001"},{"issue":"2","key":"10277_CR39","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"DJ Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266\u2013283 (1976). https:\/\/doi.org\/10.1137\/0205021","journal-title":"SIAM J. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10277-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-026-10277-8","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10277-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T03:16:37Z","timestamp":1778296597000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-026-10277-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,9]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["10277"],"URL":"https:\/\/doi.org\/10.1007\/s00224-026-10277-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,9]]},"assertion":[{"value":"15 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 April 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 May 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Saket Saurabh is a member the editorial board of Theory of Computing Systems. Otherwise, the authors have no relevant financial or non-financial interests to disclose","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"33"}}