Pith. sign in

REVIEW 3 major objections 7 minor 48 references

Parameterized Algorithms for Maximum Cut with Connectivity Constraints

T0 review · 3 major / 7 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that Connected Maximum Cut and Maximum Minimal Cut are NP-complete even on planar bipartite graphs and on split graphs, and gives fixed-parameter tractable algorithms for treewidth, twin-cover number, and solution size.

desk verdict A useful, mostly well-executed parameterized-complexity paper that is not referee-ready as written: the planar-bipartite NP-hardness proof has a counting gap in the only-if direction, and the solution-size FPT theorem rests on a two-sentence sketch of the k-prism lemma. read the letter →

arxiv 1908.03389 v1 pith:LO5LQRN5 submitted 2019-08-09 cs.DS

Hiroshi Eto , Tesshu Hanaka , Yasuaki Kobayashi , Yusuke Kobayashi This is my paper · ORCID
classification cs.DS MSC 05C8568Q17
keywords maximumcutconnectedminimalparameterizedcomplexityNP-hardnesstreewidthtwin-covernumberclique-width
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies two variants of Maximum Cut in which the sides of the cut must themselves be connected: Connected Maximum Cut requires one side to induce a connected subgraph, and Maximum Minimal Cut requires both sides to be connected, which is equivalent to the cut set being inclusion-minimal. The paper's central result is that both problems remain NP-complete even on planar bipartite graphs and on split graphs, despite the fact that ordinary Maximum Cut is solvable in polynomial time on planar graphs and on bipartite graphs. On the algorithmic side, the paper proves that both problems are fixed-parameter tractable when parameterized by treewidth, by twin-cover number, and by the size of the solution, and gives an XP algorithm when parameterized by clique-width. The results draw a precise boundary: the connectivity requirement turns two of the most tractable classes for Maximum Cut into intractable ones, yet the structural parameters that make other hard graph problems manageable still control these variants.

What carries the argument

The central mechanism is dynamic programming on a tree decomposition whose states record, for each bag, a partition of the vertices on each side of the cut into connectivity blocks, so that merging blocks joined by an edge preserves the connectivity information needed to test the one-sided or two-sided condition. Two accelerators are applied to this dynamic program: a rank-based reduction that keeps only $2^{O(tw)}$ representative weighted partitions, and the randomized Cut & Count method, which counts consistent cuts modulo two so that connectedness is detected by parity and isolated by the Isolation Lemma. For the solution-size parameter, the load-bearing structural theorem is that a graph either has treewidth $O(k^2)$ or contains a $k$-prism minor, two $k$-cycles joined by a matching; the paper asserts that the prism minor case forces a minimal cut of size at least $k$, which supplies the large-cut branch of the win-win argument.

What would settle it

Construct a graph containing a $k$-prism minor, for example the prism itself with arbitrary gadgets attached, and compute its maximum minimal cut; if any such graph has maximum minimal cut size below $k$, the large-cut branch of the $O^{*}(2^{O(k^2)})$ algorithm collapses, and inspecting the branch-set partition induced by the two cycles would show where the sketched argument fails.

Watch

Extended reading notes

Core claim

On a connected graph, a cut is minimal if and only if both sides induce connected subgraphs, so Maximum Minimal Cut asks for a large cut whose two sides are both connected, while Connected Maximum Cut asks for a large cut with one connected side. The paper proves that both problems are NP-complete on planar bipartite graphs and on split graphs, so the polynomial-time algorithms for Maximum Cut on planar and bipartite graphs do not survive the addition of the connectivity constraint even when these two tractable classes are combined. For parameters, the paper establishes fixed-parameter algorithms: $O^{*}(3^{tw})$ randomized and $O^{*}((1+2^{\omega+1})^{tw})$ deterministic for Connected Maximum Cut, $O^{*}(4^{tw})$ randomized and $O^{*}(2^{(\omega+2)tw})$ deterministic for Maximum Minimal Cut parameterized by treewidth; $O^{*}(2^{2^{tc}+tc})$ and $O^{*}(2^{tc}3^{2^{tc}})$ algorithms parameterized by twin-cover number; and $O^{*}(2^{O(k^2)})$ algorithms parameterized by solution size, with a randomized $O^{*}(9^k)$ and a deterministic $O^{*}(38.2^k)$ algorithm for Connected Maximum Cut. It also gives $n^{O(w)}$ algorithms when parameterized by clique-width and shows that neither problem admits a polynomial kernel parameterized by solution size unless NP $\subseteq$ coNP/poly.

Load-bearing premise

The algorithm parameterized by solution size assumes that every graph containing a $k$-prism minor, two $k$-cycles connected by a matching, has a minimal cut with at least $k$ edges, an assertion the paper backs with a two-sentence sketch rather than a detailed proof.

Editorial extensions

If this is right

  • Since both problems are NP-complete on planar bipartite graphs, no polynomial-time algorithm for either variant on planar or bipartite graphs can exist unless P = NP, even though ordinary Maximum Cut is polynomial on both classes.
  • The treewidth algorithms make both problems tractable on graphs of bounded treewidth, and the $O^{*}(3^{tw})$ and $O^{*}(4^{tw})$ randomized bounds cannot give false positives, matching the practical behavior of the Cut & Count technique.
  • The twin-cover FPT algorithms extend tractability to graphs whose non-twin adjacencies are covered by a small vertex set, so the parameterized behavior mirrors that of Maximum Cut itself on this parameter.
  • The solution-size algorithms run in $O^{*}(2^{O(k^2)})$ for both problems and in $O^{*}(9^k)$ randomized time for Connected Maximum Cut, meaning instances with a small optimum cut can be solved even when the graph is large, and the deterministic $O^{*}(38.2^k)$ bound removes randomness for Connected Maximum Cut.
  • Neither problem has a polynomial kernel parameterized by solution size unless NP $\subseteq$ coNP/poly, so the fixed-parameter algorithms cannot be compressed into small equivalent instances by standard kernelization.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the $k$-prism premise is verified, the same win-win strategy likely applies to other cut problems in which a large prism minor forces a large feasible cut; if the premise fails, the solution-size algorithms still work on bounded-treewidth graphs but lose their large-cut branch.
  • Since Maximum Cut is already hard for the clique-width parameter and the paper's clique-width algorithms are only XP, it is likely that both connectivity-constrained variants inherit hardness for clique-width as well, though the paper does not show this.
  • The disjoint-union composition behind the no-kernel result suggests that adding a second parameter such as treewidth or vertex-cover size might restore kernelizability and is a natural next target.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 7 minor

Summary. The paper studies two variants of Maximum Cut with connectivity constraints: Connected Maximum Cut (CMC), where one side of the cut must induce a connected subgraph, and Maximum Minimal Cut (MMC), where the cutset must be inclusion-minimal (equivalently, both sides must be connected in a connected graph). The main claimed contributions are: (i) NP-completeness of CMC on planar bipartite graphs (Theorem 7) and on split graphs (Theorem 9); (ii) NP-completeness of MMC on planar bipartite subcubic graphs (Theorem 8) and on split graphs (Theorem 10); (iii) FPT algorithms parameterized by treewidth, including deterministic O*(tw^{O(tw)}) algorithms, rank-based single-exponential algorithms (Theorems 32--33), and Monte-Carlo O*(3^{tw}) and O*(4^{tw}) algorithms via Cut & Count (Theorems 36--37); (iv) XP algorithms parameterized by clique-width (Theorem 42); (v) FPT algorithms parameterized by twin-cover number (Theorems 43--44); and (vi) FPT algorithms parameterized by solution size k, namely O*(2^{O(k^2)}) for both problems (Theorem 46), an O*(9^k) randomized algorithm and an O*(38.2^k) deterministic algorithm for CMC (Theorems 47--48), and no-polynomial-kernel results (Theorem 49). The paper also positions these results relative to the known polynomial-time solvability of plain Maximum Cut on planar and bipartite graphs.

Significance. If the results are correct after revision, the paper makes a solid contribution to the parameterized complexity of connectivity-constrained cut problems. The planar-bipartite NP-completeness results are genuinely striking, since plain Maximum Cut is polynomial on both planar graphs and bipartite graphs, and the split-graph hardness complements known results for Maximum Cut. The FPT algorithms for treewidth, twin-cover, and solution size are nontrivial and improve on the prior O*(2^{2^{O(k)}}) bound for CMC. The paper gives explicit running times, a useful summary table, and reductions from well-chosen source problems. However, two load-bearing proof gaps--the inequality in the (⇐) direction of Theorem 7 and the unproved k-prism lemma behind Theorem 46--must be repaired, and the correctness of the main treewidth DP is omitted. These issues do not appear fatal to the overall research program, but they are central enough to preclude acceptance in the current form.

major comments (3)
  1. [Section 3.1, Theorem 7 (⇐ direction)] The displayed inequality '|δ(S)| ≤ m√K + 3m + 2nK + (K + 4)(n−1) + nK^2' is not valid in the scenario being considered. When neither literal vertex of a variable x_i lies in S, all helper vertices h_i^k and their pendant vertices must lie in V\S (otherwise G[S] would contain an isolated vertex), so the nK^2 helper--pendant edges are internal to V\S and contribute zero to δ(S). Adding the nK^2 term makes the upper bound larger than the target threshold for every K, since the difference between the threshold and this bound is −nK − 2n + 2, which is negative for all n ≥ 1. The claimed contradiction therefore does not follow as written. The argument is repairable by deleting the nK^2 term from the upper bound, but the proof must be corrected.
  2. [Section 4.4, Theorem 46] The 'otherwise' branch of the algorithm is not established. The statement 'we take k middle edges corresponding to K2 in the k-prism minor and add some edges to make these edges form a cutset of some minimal cut of G' does not constitute a proof, because a cut of G is a partition of V(G), not an edge set that can be augmented arbitrarily. The proof does not specify how the two cycles of the k-prism minor are extended to a partition of all of V(G) such that both sides induce connected subgraphs and at least k rung edges are cut; vertices outside the branch sets may need to be assigned in a way that preserves connectivity on both sides. Since this k-prism lemma is the sole justification for the otherwise branch of the O*(2^{O(k^2)}) algorithms for both CMC and MMC, the lemma must be proved rigorously or replaced by another argument. The claim is plausible and can likely be proved by taking connected branch sets for the two cycles, assigning all remaining vertices via spanning trees of the contracted graph while maintaining connectivity, and counting one rung edge per i; however, this argument is absent from the manuscript.
  3. [Section 4.1.1, Theorems 12 and 13] The treewidth dynamic programming for Maximum Minimal Cut (and Connected Maximum Cut) is stated without a correctness proof. The sentence 'The correctness of the formulas are similar to ones for other connectivity problems, and hence we omit the proof here' is not sufficient for a self-contained journal paper, particularly because the DP tracks partitions on both sides of the cut and the forget and join operations interact with the requirement that both sides of the final cut are connected. These algorithms are also used as subroutines in the solution-size FPT algorithms of Theorem 46, so a rigorous correctness proof (or a precise reference to a proof for this exact DP) should be supplied.
minor comments (7)
  1. [Section 2, Definition 34] The consistency condition 'V1\V2 = ∅' should presumably read 'V1 ∩ V2 = ∅'; in addition, the assertion that a connected graph with k components has 2^{k−1} consistent cuts implicitly fixes a vertex in V1, and this should be stated explicitly.
  2. [Section 3.2, Theorem 10 proof] The proof text says 'we show that G has a cut of size at least k if and only if G′ has a connected cut of size at least k n^3'; since the problem being reduced to is Maximum Minimal Cut, this should read 'minimal cut' rather than 'connected cut'.
  3. [Section 4.1.1, Definition 11 and recurrences] The same symbols S_i and T_i are used both for subsets of a bag and for partitions of those subsets, making formulas such as mci(S_i,T_i,S_i,T_i) hard to parse; using different alphabets (e.g., script letters) for partitions would improve readability.
  4. [Section 4.1.1, forget node paragraph] The sentence 'This means that there is no path between v and s in G[S] of any partial solution at any ancestor node k of i. Therefore, v is contained in a block of size at least two in node j.' is confusingly phrased and appears to state the opposite of the intended meaning; it should say that a singleton block at a forget node can never connect to s later and is therefore discarded, which is why the recurrence merges v into an existing block.
  5. [Section 4.2, Observation 2] The phrase 'with at least twin-classes' should read 'with at least two twin-classes'.
  6. [Section 4.2, Lemma 41 proof] In the converse direction, 'the cut edges between two twin-classes of Lv is counted by mc(b,tb)' should presumably read 'between two twin-classes of Lb'.
  7. [Section 4.3, Theorem 44 proof] The sentence 'we further guess each type of cliques in G[V\X] has an intersection with only S, with only V\S, or with both S and V\S' should be rephrased for grammatical clarity, e.g., 'we guess, for each type of cliques, whether the type intersects only S, only V\S, or both'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all central results reduce to external benchmarks, standard reductions, and independent algorithmic machinery.

full rationale

The paper's derivation chain is self-contained against external benchmarks. The NP-hardness results reduce from Planar Monotone 3-SAT (Theorem 7), Maximum Minimal Cut on planar cubic graphs (Theorem 8), Exact 3-Cover (Theorem 9), and Maximum Cut (Theorem 10); each reduction constructs an explicit target graph and proves both directions by counting cut edges, with no parameter fitted from the target quantity. The treewidth algorithms are proven by dynamic-programming recurrences over nice tree decompositions, and the faster variants use the external rank-based reduce algorithm [3], the Cut & Count framework [17], and the Isolation Lemma [38]. The clique-width XP algorithms rely on the external module-width relation [43] and prove the recurrence directly in Lemma 41. The twin-cover algorithms enumerate subsets of a minimum twin-cover computed by [24] and maximize cut sizes independently per clique, so nothing is defined in terms of the claimed output. The solution-size FPT result invokes the external brambles-prisms-grids theorem of Birmelé et al. [2] and the external treewidth approximation of Bodlaender et al. [5]; the only possible weakness is that the short proof that a k-prism minor yields a minimal cut of size at least k is underdeveloped, but this is a correctness/rigor gap, not a circular reduction: the premise is an external graph-minor theorem, not an assumption of the target result, and the missing argument could be supplied by a branch-set construction independent of the algorithm's own values. The paper's only self-citation is [33] (Hanaka et al. on Maximum Minimal Separator) in the related-work list; it is not load-bearing for any theorem. There is also a minor accounting issue in the (if-and-only-if) direction of Theorem 7, where the displayed bound appears to count helper-pendant edges that are internal to V\S in the case considered; again this is a repair-able counting error rather than a circular definition. No equation in the paper reduces by construction to a fitted input, no prediction is a renamed fit, and no load-bearing premise is imported from the authors' own prior work. Accordingly, the circularity score is 0.

Assumptions & free parameters 2 free parameters · 11 assumptions · 0 invented entities

The proofs rest on standard NP-completeness source problems and cited algorithmic machinery. No step invokes an unstated premise that is unique to this paper; the reductions and recurrences are argued directly. The large constants K and M in the reduction gadgets are existential choices, not fitted parameters.

free parameters (2)
  • K = > m^2, sufficiently large
    Gadget scale in the planar-bipartite reduction for Connected Maximum Cut (Theorem 7); chosen existentially to make the cut-size inequalities strict. Not a data fit.
  • M = sufficiently large, e.g. M=3n+1
    Gadget scale in the split-graph reduction for Connected Maximum Cut (Theorem 9); chosen to force dummy vertices into the cut. Not a data fit.
assumptions (11)
  • standard math Planar Monotone 3-SAT is NP-complete (de Berg and Khosravi [18]).
    Source problem for the planar-bipartite reduction in Theorem 7.
  • standard math Exact 3-cover is NP-complete.
    Source problem for the split-graph reduction in Theorem 9; the multiplicity condition is obtained by duplicating sets.
  • standard math Maximum Cut is NP-complete.
    Source problem for the split-graph reduction in Theorem 10.
  • standard math For connected G, a cut is minimal iff both sides induce connected subgraphs.
    Equates minimal cuts with two-sided connected cuts throughout, cited to Diestel [20].
  • standard math Isolation Lemma: random weights make a unique minimum-weight solution with high probability.
    Used in the Cut & Count algorithms (Theorems 36 and 37); cited to Mulmuley et al. [38].
  • standard math The reduce algorithm returns a representative set of weighted partitions of size ≤2^{n-1} in the stated running time.
    Used for rank-based speedups in Theorems 32 and 33; cited to Bodlaender et al. [3].
  • standard math If G has no k-prism minor, then tw(G)=O(k^2).
    Contrapositive used in Theorem 46's 'otherwise' branch; cited to Birmele et al. [2].
  • standard math Treewidth can be approximated within a constant factor in O*(2^{O(k)}) time, outputting a decomposition of width O(k^2) or a witness of large treewidth.
    Used in Theorem 46 to decide the branch; cited to Bodlaender et al. [5].
  • standard math Module-width and clique-width are linearly related (mw(G) ≤ cw(G) ≤ 2mw(G)), and a decomposition tree can be computed from a w-expression.
    Basis for the clique-width XP algorithm; cited to Rao [43] and Bui-Xuan et al. [10].
  • standard math Every graph has either a spanning tree with at least k leaves or a path decomposition of width at most 2k.
    Win/Win step for Theorems 47 and 48; cited to Fellows et al. [22].
  • standard math OR-compositional parameterized problems admit no polynomial kernel unless NP⊆coNP/poly.
    Used in Theorem 49; cited to Bodlaender et al. [4].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Parameterized Algorithms for Maximum Cut with Connectivity Constraints." pith.science (2026). https://pith.science/paper/LO5LQRN5

@misc{pith2026190803389,
  author       = {Pith},
  title        = {Pith review of: Parameterized Algorithms for Maximum Cut with Connectivity Constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LO5LQRN5}},
  note         = {Machine review of arXiv:1908.03389}
}
read the original abstract

We study two variants of \textsc{Maximum Cut}, which we call \textsc{Connected Maximum Cut} and \textsc{Maximum Minimal Cut}, in this paper. In these problems, given an unweighted graph, the goal is to compute a maximum cut satisfying some connectivity requirements. Both problems are known to be NP-complete even on planar graphs whereas \textsc{Maximum Cut} on planar graphs is solvable in polynomial time. We first show that these problems are NP-complete even on planar bipartite graphs and split graphs. Then we give parameterized algorithms using graph parameters such as clique-width, tree-width, and twin-cover number. Finally, we obtain FPT algorithms with respect to the solution size.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

48 extracted references · 45 canonical work pages

  1. [1]

    Bazgan, L

    C. Bazgan, L. Brankovic, K. Casel, H. Fernau, K. Jansen, K.-M. Klein, M. Lampis, M. Liedloff, J. Monnot, and V. T. Paschos. The many facets of upper domination. Theoretical Computer Science , 717:2--25, 2018

    2018

  2. [2]

    Birmel \'e , J

    E. Birmel \'e , J. A. Bondy, and B. A. Reed. Brambles, Prisms and Grids , pages 37--44. Birkh \"a user Basel, Basel, 2007

    work page 2007

  3. [3]

    H. L. Bodlaender, M. Cygan, S. Kratsch, and J. Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Information and Computation , 243:86--111, 2015

    work page 2015

  4. [4]

    H. L. Bodlaender, R. G. Downey, M. R. Fellows, and D. Hermelin. On problems without polynomial kernels. Journal of Computer and System Sciences , 75(8):423--434, 2009

    work page 2009

  5. [5]

    H. L. Bodlaender, P. G. Drange, M. S. Dregi, F. V. Fomin, D. Lokshtanov, and M. Pilipczuk . A c^k n 5-approximation algorithm for treewidth. SIAM Journal on Computing , 45(2):317--378, 2016

    work page 2016

  6. [6]

    H. L. Bodlaender, J. R. Gilbert, H. Hafsteinsson, and T. Kloks. Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. Journal of Algorithms , 18(2):238--255, 1995

    work page 1995

  7. [7]

    H. L. Bodlaender and K. Jansen. On the complexity of the maximum cut problem. Nordic Journal of Computing , 7(1):14--31, 2000

    work page 2000

  8. [8]

    Boria, F

    N. Boria, F. D. Croce, and V. T. Paschos. On the max min vertex cover problem. Discrete Applied Mathematics , 196:62--71, 2015

    work page 2015

Show all 48 references
  1. [9]

    Boyacı, T

    A. Boyacı, T. Ekim, and M. Shalom. A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs. Information Processing Letters , 121:29--33, 2017

    2017

  2. [10]

    Bui-Xuan, O

    B.-M. Bui-Xuan, O. Suchý, J. A. Telle, and M. Vatshelle. Feedback vertex set on graphs of low clique-width. European Journal of Combinatorics , 34(3):666--679, 2013

    2013

  3. [11]

    Carvajal, M

    R. Carvajal, M. Constantino, M. Goycoolea, J. P. Vielma, and A. Weintraub. Imposing connectivity constraints in forest planning models. Operations Research , 61(4):824--836, 2013

    2013

  4. [12]

    Chaourar

    B. Chaourar. A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs. Advances in Operations Research , pages 1267108:1--1267108:4, 2017

    2017

  5. [13]

    Chaourar

    B. Chaourar. Connected max cut is polynomial for graphs without K _5 e as a minor. CoRR , abs/1903.12641, 2019

    1903 arXiv

  6. [14]

    Courcelle and S

    B. Courcelle and S. Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics , 101(1):77--114, 2000

    2000

  7. [15]

    M. Cygan. Deterministic parameterized connected vertex cover. In SWAT 2012 , pages 95--106, 2012

    2012

  8. [16]

    Cygan, F

    M. Cygan, F. V. Fomin, . Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms . Springer International Publishing, 2015

    2015

  9. [17]

    Cygan, J

    M. Cygan, J. Nederlof, M. Pilipczuk, M. Pilipczuk, J. M. M. van Rooij, and J. O. Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In FOCS 2011 , pages 150--159, 2011

    2011

  10. [18]

    de Berg and A

    M. de Berg and A. Khosravi. Finding perfect auto-partitions is NP -hard. In EuroCG 2009 , pages 255--258., 2009

    2009

  11. [19]

    M. Demange. A note on the approximation of a minimum-weight maximal independent set. Computational Optimization and Applications , 14(1):157--169, 1999

    1999

  12. [20]

    R. Diestel. Graph Theory, 4th Edition , volume 173 of Graduate texts in mathematics . Springer, 2012

    2012

  13. [21]

    Díaz and M

    J. Díaz and M. Kamiński. Max-cut and max-bisection are NP -hard on unit disk graphs. Theoretical Computer Science , 377(1):271--276, 2007

    2007

  14. [22]

    M. R. Fellows, D. Lokshtanov, N. Misra, M. Mnich, F. Rosamond, and S. Saurabh. The complexity ecology of parameters: An illustration using bounded max leaf number. Theory of Computing Systems , 45(4):822--848, 2009

    2009

  15. [23]

    F. V. Fomin, P. Golovach, D. Lokshtanov, and S. Saurabh. Almost optimal lower bounds for problems parameterized by clique-width. SIAM Journal on Computing , 43(5):1541--1563, 2014

    2014

  16. [24]

    R. Ganian. Improving Vertex Cover as a Graph Parameter . Discrete Mathematics and Theoretical Computer Science , 17(2):77--100, 2015

    2015

  17. [25]

    M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman & Co., New York, NY, USA, 1979

    1979

  18. [26]

    M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM , 42(6):1115--1145, 1995

    1995

  19. [27]

    Grimm, T

    V. Grimm, T. Kleinert, F. Liers, M. Schmidt, and G. Zöttl. Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches. Optimization Methods and Software , 34(2):406--436, 2019

    2019

  20. [28]

    Guha and S

    S. Guha and S. Khuller. Approximation algorithms for connected dominating sets. Algorithmica , 20(4):374--387, 1998

    1998

  21. [29]

    Guruswami

    V. Guruswami. Maximum cut on line and total graphs. Discrete Applied Mathematics , 92(2):217--221, 1999

    1999

  22. [30]

    F. Hadlock. Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing , 4(3):221--225, 1975

    1975

  23. [31]

    D. J. Haglin and S. M. Venkatesan . Approximation and intractability results for the maximum cut problem and its variants. IEEE Transactions on Computers , 40(1):110--113, 1991

    1991

  24. [32]

    M. T. Hajiaghayi, G. Kortsarz, R. MacDavid, M. Purohit, and K. Sarpatwar. Approximation algorithms for connected maximum cut and related problems. In ESA 2015 , pages 693--704, 2015

    2015

  25. [33]

    Hanaka, H

    T. Hanaka, H. L. Bodlaender, T. C. van der Zanden, and H. Ono. On the maximum weight minimal separator. In TAMC 2017 , pages 304--318, 2017

    2017

  26. [34]

    Hliněný and S

    P. Hliněný and S. Oum. Finding branch-decompositions and rank-decompositions. SIAM Journal on Computing , 38(3):1012--1032, 2008

    2008

  27. [35]

    R. M. Karp. Reducibility among Combinatorial Problems , pages 85--103. Springer US, Boston, MA, 1972

    1972

  28. [36]

    Khoshkhah, M

    K. Khoshkhah, M. K. Ghadikolaei, J. Monnot, and F. Sikora. Weighted upper edge cover: Complexity and approximability. In WALCOM 2019 , pages 235--247, 2019

    2019

  29. [37]

    Mahajan and V

    M. Mahajan and V. Raman. Parameterizing above guaranteed values: Maxsat and maxcut. Journal of Algorithms , 31(2):335--354, 1999

    1999

  30. [38]

    Mulmuley, U

    K. Mulmuley, U. V. Vazirani, and V.V. Vazirani. Matching is as easy as matrix inversion. Combinatorica , 7(1):105--113, 1987

    1987

  31. [39]

    G. I. Orlova and Y. G. Dorfman. Finding the maximal cut in a graph. Engineering Cyvernetics , 10(3):502--506, 1972

    1972

  32. [40]

    S. Oum. Approximating rank-width and clique-width quickly. ACM Transactions on Algorithms , 5(1):10:1--10:20, 2008

    2008

  33. [41]

    Oum and P

    S. Oum and P. Seymour. Approximating clique-width and branch-width. Journal of Combinatorial Theory, Series B , 96(4):514--528, 2006

    2006

  34. [42]

    Raman and S

    V. Raman and S. Saurabh. Improved fixed parameter tractable algorithms for two “edge” problems: MAXCUT and MAXDAG . Information Processing Letters , 104(2):65--72, 2007

    2007

  35. [43]

    M. Rao. Clique-width of graphs defined by one-vertex extensions. Discrete Mathematics , 308(24):6157--6165, 2008

    2008

  36. [44]

    Robertson and P

    N. Robertson and P. D. Seymour. Graph minors. V. excluding a planar graph. Journal of Combinatorial Theory, Series B , 41(1):92--114, 1986

    1986

  37. [45]

    Saurabh and M

    S. Saurabh and M. Zehavi. Parameterized Complexity of Multi-Node Hubs . In IPEC 2018 , volume 115, pages 8:1--8:14, 2019

    2018

  38. [46]

    Vicente , V

    S. Vicente , V. Kolmogorov , and C. Rother . Graph cut based image segmentation with connectivity priors. In CVPR 2008 , pages 1--8, 2008

    2008

  39. [47]

    Yannakakis and F

    M. Yannakakis and F. Gavril. Edge dominating sets in graphs. SIAM Journal on Applied Mathematics , 38(3):364--372, 1980

    1980

  40. [48]

    M. Zehavi. Maximum minimal vertex cover parameterized by vertex cover. SIAM Journal on Discrete Mathematics , 31(4):2440--2456, 2017

    2017

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.