Matching Cut in Graphs with Large Minimum Degree Article Swipe

PDF

Chi‐Yeh Chen , Sun‐Yuan Hsieh , Hoang-Oanh Le , Van Bang Lê , Sheng-Lung Peng ·

YOU? · · 2020 · Open Access · · DOI: https://doi.org/10.1007/s00453-020-00782-8

In a graph, a matching cut is an edge cut that is a matching. M atching C ut is the problem of deciding whether or not a given graph has a matching cut, which is known to be $${\mathsf {NP}}$$ -complete. While M atching C ut is trivial for graphs with minimum degree at most one, it is $${\mathsf {NP}}$$ -complete on graphs with minimum degree two. In this paper, we show that, for any given constant $$c>1$$ , M atching C ut is $${\mathsf {NP}}$$ -complete in the class of graphs with minimum degree c and this restriction of M atching C ut has no subexponential-time algorithm in the number of vertices unless the Exponential-Time Hypothesis fails. We also show that, for any given constant $$\epsilon >0$$ , M atching C ut remains $${\mathsf {NP}}$$ -complete in the class of n -vertex (bipartite) graphs with unbounded minimum degree $$\delta >n^{1-\epsilon }$$ . We give an exact branching algorithm to solve M atching C ut for graphs with minimum degree $$\delta \ge 3$$ in $$O^*(\lambda ^n)$$ time, where $$\lambda$$ is the positive root of the polynomial $$x^{\delta +1}-x^{\delta }-1$$ . Despite the hardness results, this is a very fast exact exponential-time algorithm for M atching C ut on graphs with large minimum degree; for instance, the running time is $$O^*(1.0099^n)$$ on graphs with minimum degree $$\delta \ge 469$$ . Complementing our hardness results, we show that, for any two fixed constants $$1< c <4$$ and $$c^{\prime }\ge 0$$ , M atching C ut is solvable in polynomial time for graphs with large minimum degree $$\delta \ge \frac{1}{c}n-c^{\prime }$$ .

Related Topics

Concepts

Combinatorics Matching (statistics) Degree (music) Algorithm Graph Mathematics Statistics Physics Acoustics

Metadata

Type: article
Language: en
Landing Page: https://doi.org/10.1007/s00453-020-00782-8
PDF: https://link.springer.com/content/pdf/10.1007/s00453-020-00782-8.pdf
OA Status: hybrid
Cited By: 18
References: 23
Related Works: 10
OpenAlex ID: https://openalex.org/W3110459966

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W3110459966

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.1007/s00453-020-00782-8

Digital Object Identifier
Title: Matching Cut in Graphs with Large Minimum Degree

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2020

Year of publication
Publication date: 2020-11-23

Full publication date if available
Authors: Chi‐Yeh Chen, Sun‐Yuan Hsieh, Hoang-Oanh Le, Van Bang Lê, Sheng-Lung Peng

List of authors in order
Landing page: https://doi.org/10.1007/s00453-020-00782-8

Publisher landing page
PDF URL: https://link.springer.com/content/pdf/10.1007/s00453-020-00782-8.pdf

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: hybrid

Open access status per OpenAlex
OA URL: https://link.springer.com/content/pdf/10.1007/s00453-020-00782-8.pdf

Direct OA link when available
Concepts: Combinatorics, Matching (statistics), Degree (music), Algorithm, Graph, Mathematics, Statistics, Physics, Acoustics

Top concepts (fields/topics) attached by OpenAlex
Cited by: 18

Total citation count in OpenAlex
Citations by year (recent): 2025: 5, 2024: 2, 2023: 5, 2022: 3, 2021: 3

Per-year citation counts (last 5 years)
References (count): 23

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W3110459966
doi	https://doi.org/10.1007/s00453-020-00782-8
ids.doi	https://doi.org/10.1007/s00453-020-00782-8
ids.mag	3110459966
ids.openalex	https://openalex.org/W3110459966
fwci	1.61796917
type	article
title	Matching Cut in Graphs with Large Minimum Degree
biblio.issue	5
biblio.volume	83
biblio.last_page	1255
biblio.first_page	1238
topics[0].id	https://openalex.org/T10374
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9998999834060669
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1703
topics[0].subfield.display_name	Computational Theory and Mathematics
topics[0].display_name	Advanced Graph Theory Research
topics[1].id	https://openalex.org/T10720
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9994999766349792
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1703
topics[1].subfield.display_name	Computational Theory and Mathematics
topics[1].display_name	Complexity and Algorithms in Graphs
topics[2].id	https://openalex.org/T12288
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9965999722480774
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1705
topics[2].subfield.display_name	Computer Networks and Communications
topics[2].display_name	Optimization and Search Problems
funders[0].id	https://openalex.org/F4320327736
funders[0].ror	https://ror.org/03zdwsf69
funders[0].display_name	Universität Rostock
is_xpac	False
apc_list.value	2290
apc_list.currency	EUR
apc_list.value_usd	2890
apc_paid.value	2290
apc_paid.currency	EUR
apc_paid.value_usd	2890
concepts[0].id	https://openalex.org/C114614502
concepts[0].level	1
concepts[0].score	0.5416072607040405
concepts[0].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[0].display_name	Combinatorics
concepts[1].id	https://openalex.org/C165064840
concepts[1].level	2
concepts[1].score	0.49383360147476196
concepts[1].wikidata	https://www.wikidata.org/wiki/Q1321061
concepts[1].display_name	Matching (statistics)
concepts[2].id	https://openalex.org/C2775997480
concepts[2].level	2
concepts[2].score	0.4871382415294647
concepts[2].wikidata	https://www.wikidata.org/wiki/Q586277
concepts[2].display_name	Degree (music)
concepts[3].id	https://openalex.org/C11413529
concepts[3].level	1
concepts[3].score	0.4770307242870331
concepts[3].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[3].display_name	Algorithm
concepts[4].id	https://openalex.org/C132525143
concepts[4].level	2
concepts[4].score	0.4392138421535492
concepts[4].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[4].display_name	Graph
concepts[5].id	https://openalex.org/C33923547
concepts[5].level	0
concepts[5].score	0.43462860584259033
concepts[5].wikidata	https://www.wikidata.org/wiki/Q395
concepts[5].display_name	Mathematics
concepts[6].id	https://openalex.org/C105795698
concepts[6].level	1
concepts[6].score	0.22226396203041077
concepts[6].wikidata	https://www.wikidata.org/wiki/Q12483
concepts[6].display_name	Statistics
concepts[7].id	https://openalex.org/C121332964
concepts[7].level	0
concepts[7].score	0.2103378176689148
concepts[7].wikidata	https://www.wikidata.org/wiki/Q413
concepts[7].display_name	Physics
concepts[8].id	https://openalex.org/C24890656
concepts[8].level	1
concepts[8].score	0.0
concepts[8].wikidata	https://www.wikidata.org/wiki/Q82811
concepts[8].display_name	Acoustics
keywords[0].id	https://openalex.org/keywords/combinatorics
keywords[0].score	0.5416072607040405
keywords[0].display_name	Combinatorics
keywords[1].id	https://openalex.org/keywords/matching
keywords[1].score	0.49383360147476196
keywords[1].display_name	Matching (statistics)
keywords[2].id	https://openalex.org/keywords/degree
keywords[2].score	0.4871382415294647
keywords[2].display_name	Degree (music)
keywords[3].id	https://openalex.org/keywords/algorithm
keywords[3].score	0.4770307242870331
keywords[3].display_name	Algorithm
keywords[4].id	https://openalex.org/keywords/graph
keywords[4].score	0.4392138421535492
keywords[4].display_name	Graph
keywords[5].id	https://openalex.org/keywords/mathematics
keywords[5].score	0.43462860584259033
keywords[5].display_name	Mathematics
keywords[6].id	https://openalex.org/keywords/statistics
keywords[6].score	0.22226396203041077
keywords[6].display_name	Statistics
keywords[7].id	https://openalex.org/keywords/physics
keywords[7].score	0.2103378176689148
keywords[7].display_name	Physics
language	en
locations[0].id	doi:10.1007/s00453-020-00782-8
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S89324355
locations[0].source.issn	0178-4617, 1432-0541
locations[0].source.type	journal
locations[0].source.is_oa	False
locations[0].source.issn_l	0178-4617
locations[0].source.is_core	True
locations[0].source.is_in_doaj	False
locations[0].source.display_name	Algorithmica
locations[0].source.host_organization	https://openalex.org/P4310319900
locations[0].source.host_organization_name	Springer Science+Business Media
locations[0].source.host_organization_lineage	https://openalex.org/P4310319900, https://openalex.org/P4310319965
locations[0].source.host_organization_lineage_names	Springer Science+Business Media, Springer Nature
locations[0].license	cc-by
locations[0].pdf_url	https://link.springer.com/content/pdf/10.1007/s00453-020-00782-8.pdf
locations[0].version	publishedVersion
locations[0].raw_type	journal-article
locations[0].license_id	https://openalex.org/licenses/cc-by
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	Algorithmica
locations[0].landing_page_url	https://doi.org/10.1007/s00453-020-00782-8
indexed_in	crossref
authorships[0].author.id	https://openalex.org/A5027480824
authorships[0].author.orcid	https://orcid.org/0000-0001-9664-8538
authorships[0].author.display_name	Chi‐Yeh Chen
authorships[0].countries	TW
authorships[0].affiliations[0].institution_ids	https://openalex.org/I91807558
authorships[0].affiliations[0].raw_affiliation_string	Department of Computer Science and Information Engineering, National Cheng Kung University, No. 1, University Road, Tainan, 70101, Taiwan
authorships[0].institutions[0].id	https://openalex.org/I91807558
authorships[0].institutions[0].ror	https://ror.org/01b8kcc49
authorships[0].institutions[0].type	education
authorships[0].institutions[0].lineage	https://openalex.org/I91807558
authorships[0].institutions[0].country_code	TW
authorships[0].institutions[0].display_name	National Cheng Kung University
authorships[0].author_position	first
authorships[0].raw_author_name	Chi-Yeh Chen
authorships[0].is_corresponding	False
authorships[0].raw_affiliation_strings	Department of Computer Science and Information Engineering, National Cheng Kung University, No. 1, University Road, Tainan, 70101, Taiwan
authorships[1].author.id	https://openalex.org/A5103047340
authorships[1].author.orcid	https://orcid.org/0000-0003-4746-3179
authorships[1].author.display_name	Sun‐Yuan Hsieh
authorships[1].countries	TW
authorships[1].affiliations[0].institution_ids	https://openalex.org/I91807558
authorships[1].affiliations[0].raw_affiliation_string	Department of Computer Science and Information Engineering, National Cheng Kung University, No. 1, University Road, Tainan, 70101, Taiwan
authorships[1].institutions[0].id	https://openalex.org/I91807558
authorships[1].institutions[0].ror	https://ror.org/01b8kcc49
authorships[1].institutions[0].type	education
authorships[1].institutions[0].lineage	https://openalex.org/I91807558
authorships[1].institutions[0].country_code	TW
authorships[1].institutions[0].display_name	National Cheng Kung University
authorships[1].author_position	middle
authorships[1].raw_author_name	Sun-Yuan Hsieh
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	Department of Computer Science and Information Engineering, National Cheng Kung University, No. 1, University Road, Tainan, 70101, Taiwan
authorships[2].author.id	https://openalex.org/A5109481492
authorships[2].author.orcid
authorships[2].author.display_name	Hoang-Oanh Le
authorships[2].affiliations[0].raw_affiliation_string	Berlin, Germany
authorships[2].author_position	middle
authorships[2].raw_author_name	Hoang-Oanh Le
authorships[2].is_corresponding	False
authorships[2].raw_affiliation_strings	Berlin, Germany
authorships[3].author.id	https://openalex.org/A5072055012
authorships[3].author.orcid	https://orcid.org/0000-0002-3303-8326
authorships[3].author.display_name	Van Bang Lê
authorships[3].countries	DE
authorships[3].affiliations[0].institution_ids	https://openalex.org/I4665924
authorships[3].affiliations[0].raw_affiliation_string	Institut für Informatik, Universität Rostock, Rostock, Germany
authorships[3].institutions[0].id	https://openalex.org/I4665924
authorships[3].institutions[0].ror	https://ror.org/03zdwsf69
authorships[3].institutions[0].type	education
authorships[3].institutions[0].lineage	https://openalex.org/I4665924
authorships[3].institutions[0].country_code	DE
authorships[3].institutions[0].display_name	University of Rostock
authorships[3].author_position	middle
authorships[3].raw_author_name	Van Bang Le
authorships[3].is_corresponding	True
authorships[3].raw_affiliation_strings	Institut für Informatik, Universität Rostock, Rostock, Germany
authorships[4].author.id	https://openalex.org/A5110628769
authorships[4].author.orcid
authorships[4].author.display_name	Sheng-Lung Peng
authorships[4].countries	TW
authorships[4].affiliations[0].institution_ids	https://openalex.org/I43566213
authorships[4].affiliations[0].raw_affiliation_string	Department of Creative Technologies and Product Design, National Taipei University of Business, Taipei, Taiwan
authorships[4].institutions[0].id	https://openalex.org/I43566213
authorships[4].institutions[0].ror	https://ror.org/029hrv109
authorships[4].institutions[0].type	education
authorships[4].institutions[0].lineage	https://openalex.org/I43566213
authorships[4].institutions[0].country_code	TW
authorships[4].institutions[0].display_name	National Taipei University of Business
authorships[4].author_position	last
authorships[4].raw_author_name	Sheng-Lung Peng
authorships[4].is_corresponding	False
authorships[4].raw_affiliation_strings	Department of Creative Technologies and Product Design, National Taipei University of Business, Taipei, Taiwan
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://link.springer.com/content/pdf/10.1007/s00453-020-00782-8.pdf
open_access.oa_status	hybrid
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Matching Cut in Graphs with Large Minimum Degree
has_fulltext	True
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
primary_topic.id	https://openalex.org/T10374
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9998999834060669
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1703
primary_topic.subfield.display_name	Computational Theory and Mathematics
primary_topic.display_name	Advanced Graph Theory Research
related_works	https://openalex.org/W2051487156, https://openalex.org/W2073681303, https://openalex.org/W3161230432, https://openalex.org/W1487201914, https://openalex.org/W4367190712, https://openalex.org/W2544423928, https://openalex.org/W280458463, https://openalex.org/W1170131723, https://openalex.org/W4301429470, https://openalex.org/W2168900540
cited_by_count	18
counts_by_year[0].year	2025
counts_by_year[0].cited_by_count	5
counts_by_year[1].year	2024
counts_by_year[1].cited_by_count	2
counts_by_year[2].year	2023
counts_by_year[2].cited_by_count	5
counts_by_year[3].year	2022
counts_by_year[3].cited_by_count	3
counts_by_year[4].year	2021
counts_by_year[4].cited_by_count	3
locations_count	1
best_oa_location.id	doi:10.1007/s00453-020-00782-8
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S89324355
best_oa_location.source.issn	0178-4617, 1432-0541
best_oa_location.source.type	journal
best_oa_location.source.is_oa	False
best_oa_location.source.issn_l	0178-4617
best_oa_location.source.is_core	True
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	Algorithmica
best_oa_location.source.host_organization	https://openalex.org/P4310319900
best_oa_location.source.host_organization_name	Springer Science+Business Media
best_oa_location.source.host_organization_lineage	https://openalex.org/P4310319900, https://openalex.org/P4310319965
best_oa_location.source.host_organization_lineage_names	Springer Science+Business Media, Springer Nature
best_oa_location.license	cc-by
best_oa_location.pdf_url	https://link.springer.com/content/pdf/10.1007/s00453-020-00782-8.pdf
best_oa_location.version	publishedVersion
best_oa_location.raw_type	journal-article
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	Algorithmica
best_oa_location.landing_page_url	https://doi.org/10.1007/s00453-020-00782-8
primary_location.id	doi:10.1007/s00453-020-00782-8
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S89324355
primary_location.source.issn	0178-4617, 1432-0541
primary_location.source.type	journal
primary_location.source.is_oa	False
primary_location.source.issn_l	0178-4617
primary_location.source.is_core	True
primary_location.source.is_in_doaj	False
primary_location.source.display_name	Algorithmica
primary_location.source.host_organization	https://openalex.org/P4310319900
primary_location.source.host_organization_name	Springer Science+Business Media
primary_location.source.host_organization_lineage	https://openalex.org/P4310319900, https://openalex.org/P4310319965
primary_location.source.host_organization_lineage_names	Springer Science+Business Media, Springer Nature
primary_location.license	cc-by
primary_location.pdf_url	https://link.springer.com/content/pdf/10.1007/s00453-020-00782-8.pdf
primary_location.version	publishedVersion
primary_location.raw_type	journal-article
primary_location.license_id	https://openalex.org/licenses/cc-by
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	Algorithmica
primary_location.landing_page_url	https://doi.org/10.1007/s00453-020-00782-8
publication_date	2020-11-23
publication_year	2020
referenced_works	https://openalex.org/W2173904855, https://openalex.org/W2770541954, https://openalex.org/W2738197751, https://openalex.org/W1997541985, https://openalex.org/W2082548475, https://openalex.org/W1986824573, https://openalex.org/W2998050277, https://openalex.org/W2153737011, https://openalex.org/W2963218931, https://openalex.org/W1985572324, https://openalex.org/W1995725694, https://openalex.org/W2998596251, https://openalex.org/W2190210389, https://openalex.org/W2798321768, https://openalex.org/W2087872235, https://openalex.org/W2046680668, https://openalex.org/W1924888395, https://openalex.org/W2017867718, https://openalex.org/W2069561762, https://openalex.org/W2944716799, https://openalex.org/W2015963099, https://openalex.org/W2059671029, https://openalex.org/W2151607372
referenced_works_count	23
abstract_inverted_index.,	95, 157, 393
abstract_inverted_index..	200, 286, 352, 430
abstract_inverted_index.C	17, 49, 98, 123, 160, 211, 302, 396
abstract_inverted_index.M	15, 47, 96, 121, 158, 209, 300, 394
abstract_inverted_index.a	2, 4, 13, 27, 31, 293
abstract_inverted_index.c	116, 366
abstract_inverted_index.n	174
abstract_inverted_index.In	1, 76
abstract_inverted_index.We	139, 201
abstract_inverted_index.an	8, 203
abstract_inverted_index.at	58
abstract_inverted_index.be	38
abstract_inverted_index.in	108, 129, 170, 229, 400
abstract_inverted_index.is	7, 12, 19, 35, 51, 62, 100, 256, 292, 315, 398
abstract_inverted_index.it	61
abstract_inverted_index.no	126
abstract_inverted_index.of	22, 111, 120, 132, 173, 260
abstract_inverted_index.on	70, 304, 336
abstract_inverted_index.or	25
abstract_inverted_index.to	37, 207
abstract_inverted_index.ut	18, 50, 99, 124, 161, 212, 303, 397
abstract_inverted_index.we	79, 357
abstract_inverted_index.0$$	381
abstract_inverted_index.3$$	220
abstract_inverted_index.\ge	219, 342, 410
abstract_inverted_index.and	117, 378
abstract_inverted_index.any	83, 144, 361
abstract_inverted_index.cut	6, 10
abstract_inverted_index.for	53, 82, 143, 213, 299, 310, 360, 403
abstract_inverted_index.has	30, 125
abstract_inverted_index.not	26
abstract_inverted_index.our	354
abstract_inverted_index.the	20, 109, 130, 135, 171, 257, 261, 288, 312
abstract_inverted_index.two	362
abstract_inverted_index.}$$	184, 412
abstract_inverted_index.also	140
abstract_inverted_index.cut,	33
abstract_inverted_index.edge	9
abstract_inverted_index.fast	295
abstract_inverted_index.give	202
abstract_inverted_index.most	59
abstract_inverted_index.one,	60
abstract_inverted_index.root	259
abstract_inverted_index.show	80, 141, 358
abstract_inverted_index.that	11
abstract_inverted_index.this	77, 118, 291
abstract_inverted_index.time	314, 402
abstract_inverted_index.two.	75
abstract_inverted_index.very	294
abstract_inverted_index.with	55, 72, 113, 178, 215, 306, 338, 405
abstract_inverted_index.}\ge	380
abstract_inverted_index.469$$	343
abstract_inverted_index.While	46
abstract_inverted_index.^n)$$	231
abstract_inverted_index.class	110, 172
abstract_inverted_index.exact	204, 296
abstract_inverted_index.fixed	363
abstract_inverted_index.given	28, 84, 145
abstract_inverted_index.graph	29
abstract_inverted_index.known	36
abstract_inverted_index.large	307, 406
abstract_inverted_index.solve	208
abstract_inverted_index.that,	81, 142, 359
abstract_inverted_index.time,	249
abstract_inverted_index.where	250
abstract_inverted_index.which	34
abstract_inverted_index.}-1$$	265
abstract_inverted_index.degree	57, 74, 115, 181, 217, 340, 408
abstract_inverted_index.fails.	138
abstract_inverted_index.graph,	3
abstract_inverted_index.graphs	54, 71, 112, 177, 214, 305, 337, 404
abstract_inverted_index.number	131
abstract_inverted_index.paper,	78
abstract_inverted_index.unless	134
abstract_inverted_index.$$1<	365
abstract_inverted_index.>0$$	148
abstract_inverted_index.<4$$	367
abstract_inverted_index.-vertex	175
abstract_inverted_index.Despite	287
abstract_inverted_index.atching	16, 48, 97, 122, 159, 210, 301, 395
abstract_inverted_index.degree;	309
abstract_inverted_index.minimum	56, 73, 114, 180, 216, 308, 339, 407
abstract_inverted_index.problem	21
abstract_inverted_index.remains	162
abstract_inverted_index.running	313
abstract_inverted_index.trivial	52
abstract_inverted_index.whether	24
abstract_inverted_index.{NP}}$$	40, 64, 102, 164
abstract_inverted_index.$$\delta	182, 218, 341, 409
abstract_inverted_index.Abstract	0
abstract_inverted_index.constant	85, 146
abstract_inverted_index.deciding	23
abstract_inverted_index.hardness	289, 355
abstract_inverted_index.matching	5, 32
abstract_inverted_index.positive	258
abstract_inverted_index.results,	290, 356
abstract_inverted_index.solvable	399
abstract_inverted_index.vertices	133
abstract_inverted_index.-complete	69, 107, 169
abstract_inverted_index.<mml:math	41, 65, 87, 103, 149, 165, 185, 221, 232, 252, 266, 317, 344, 368, 382, 413
abstract_inverted_index.algorithm	128, 206, 298
abstract_inverted_index.branching	205
abstract_inverted_index.constants	364
abstract_inverted_index.instance,	311
abstract_inverted_index.matching.	14
abstract_inverted_index.unbounded	179
abstract_inverted_index.$$\epsilon	147
abstract_inverted_index.$$c>1$$	86
abstract_inverted_index.$${\mathsf	39, 63, 101, 163
abstract_inverted_index.-complete.	45
abstract_inverted_index.<mml:mrow>	89, 151, 187, 192, 223, 234, 239, 268, 271, 319, 324, 346, 370, 384, 415
abstract_inverted_index.<mml:msup>	190, 235, 241, 269, 278, 320, 328, 385, 424
abstract_inverted_index.Hypothesis	137
abstract_inverted_index.polynomial	262, 401
abstract_inverted_index.$$\lambda$$	251
abstract_inverted_index.$$c^{\prime	379
abstract_inverted_index.$$x^{\delta	263
abstract_inverted_index.(bipartite)	176
abstract_inverted_index.</mml:math>	44, 68, 94, 106, 156, 168, 199, 228, 248, 255, 285, 335, 351, 377, 392, 429
abstract_inverted_index.</mml:mrow>	93, 155, 196, 198, 227, 246, 247, 275, 284, 333, 334, 350, 376, 391, 428
abstract_inverted_index.</mml:msup>	197, 238, 244, 276, 281, 323, 331, 388, 427
abstract_inverted_index.<mml:mfrac>	418
abstract_inverted_index.restriction	119
abstract_inverted_index.</mml:mfrac>	421
abstract_inverted_index.$$O^*(\lambda	230
abstract_inverted_index.+1}-x^{\delta	264
abstract_inverted_index.Complementing	353
abstract_inverted_index.Exponential-Time	136
abstract_inverted_index.exponential-time	297
abstract_inverted_index.$$O^*(1.0099^n)$$	316
abstract_inverted_index.>n^{1-\epsilon	183
abstract_inverted_index.<mml:mi>O</mml:mi>	236, 321
abstract_inverted_index.<mml:mi>c</mml:mi>	90, 373, 386, 420, 425
abstract_inverted_index.<mml:mi>n</mml:mi>	191, 243, 330, 422
abstract_inverted_index.<mml:mi>x</mml:mi>	270, 279
abstract_inverted_index.<mml:mn>0</mml:mn>	154, 390
abstract_inverted_index.<mml:mn>1</mml:mn>	92, 193, 274, 283, 326, 371, 419
abstract_inverted_index.<mml:mn>3</mml:mn>	226
abstract_inverted_index.<mml:mn>4</mml:mn>	375
abstract_inverted_index.<mml:mo>(</mml:mo>	240, 325
abstract_inverted_index.<mml:mo>)</mml:mo>	245, 332
abstract_inverted_index.<mml:mo>+</mml:mo>	273
abstract_inverted_index.<mml:mo>-</mml:mo>	194, 277, 282, 423
abstract_inverted_index.<mml:mo>.</mml:mo>	327
abstract_inverted_index.<mml:mi>NP</mml:mi>	43, 67, 105, 167
abstract_inverted_index.<mml:mi>δ</mml:mi>	188, 224, 272, 280, 347, 416
abstract_inverted_index.<mml:mi>λ</mml:mi>	242, 254
abstract_inverted_index.<mml:mi>ϵ</mml:mi>	152, 195
abstract_inverted_index.subexponential-time	127
abstract_inverted_index.<mml:mn>469</mml:mn>	349
abstract_inverted_index.<mml:mo>′</mml:mo>	387, 426
abstract_inverted_index.<mml:mo>∗</mml:mo>	237, 322
abstract_inverted_index.<mml:mo>≥</mml:mo>	225, 348, 389, 417
abstract_inverted_index.<mml:mn>0099</mml:mn>	329
abstract_inverted_index.<mml:mo>></mml:mo>	91, 153, 189
abstract_inverted_index.<mml:mo><</mml:mo>	372, 374
abstract_inverted_index.\frac{1}{c}n-c^{\prime	411
abstract_inverted_index.xmlns:mml="http://www.w3.org/1998/Math/MathML">	42, 66, 88, 104, 150, 166, 186, 222, 233, 253, 267, 318, 345, 369, 383, 414
cited_by_percentile_year.max	98
cited_by_percentile_year.min	94
corresponding_author_ids	https://openalex.org/A5072055012
countries_distinct_count	2
institutions_distinct_count	5
corresponding_institution_ids	https://openalex.org/I4665924
citation_normalized_percentile.value	0.87680205
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False