Even, Itai, and Shamir (1976) proved simple two‐commodity integral flow is NP‐complete both in the directed and undirected cases. In particular, the directed case was shown to be NP‐complete even if ...one demand is unitary, which was improved by Fortune, Hopcroft and Wyllie (1980) who proved the problem is still NP‐complete if both demands are unitary. The undirected case, on the other hand, was proved by Robertson and Seymour (1995) to be polynomial‐time solvable if both demands are constant. Nevertheless, the complexity of the undirected case with exactly one constant demand has remained unknown. We close this 40‐year complexity gap, by showing the undirected case is NP‐complete even if exactly one demand is unitary. As a by product, we obtain the NP‐completeness of determining whether a graph contains 1 + d pairwise vertex‐disjoint paths, such that one path is between a given pair of vertices and d paths are between a second given pair of vertices. Additionally, we investigate the complexity of another related network design problem called strict terminal connection.
Given a class A of graphs and a decision problem π belonging to NP, we say that a full complexity dichotomy of A was obtained if one describes a partition of A into subclasses such that π is ...classified as polynomial or NP-complete when restricted to each subclass. The concept of full complexity dichotomy is particularly interesting for the investigation of NP-complete problems: as we partition a class A into NP-complete subclasses and polynomial subclasses, it becomes clearer why the problem is NP-complete in A. The class C of graphs that do not contain a cycle with a unique chord was studied by Trotignon and Vušković who proved a structure theorem which led to solving the vertex-colouring problem in polynomial time. In the present survey, we apply the structure theorem to study the complexity of edge-colouring and total-colouring, and show that even for graph classes with strong structure and powerful decompositions, the edge-colouring problem may be difficult. We discuss several surprising complexity dichotomies found in subclasses of C, and the concepts of separating problem proposed by David S. Johnson and the dual concept of separating class.
MaxCut on permutation graphs is NP‐complete Figueiredo, Celina M. H.; Melo, Alexsander A.; Oliveira, Fabiano S. ...
Journal of graph theory,
September 2023, 2023-09-00, 20230901, Volume:
104, Issue:
1
Journal Article
Peer reviewed
Open access
The decision problem MaxC
ut is known to be NP‐complete since the seventies, but only recently its restriction to interval graphs has been announced to be hard by Adhikary, Bose, Mukherjee, and Roy. ...Building on their proof, in this paper we prove that the M
axC
ut problem is NP‐complete on permutation graphs. This settles a long‐standing open problem that appeared in the 1985 column of the Ongoing Guide to NP‐completeness by David S. Johnson, and is the first NP‐hardness entry for permutation graphs in such column.
Let Pk denote an induced path on k vertices. For k≥5, we show that the Pk-free sandwich problem, partitioned probe problem, and unpartitioned probe problem are NP-complete. For k≤4, it is known that ...the Pk-free sandwich problem, partitioned probe problem, and unpartitioned probe problem are in P.
Computing the zig-zag number of directed graphs Dourado, Mitre C.; de Figueiredo, Celina M.H.; de Melo, Alexsander A. ...
Discrete Applied Mathematics,
05/2022, Volume:
312
Journal Article
Peer reviewed
The notion of zig-zag number was introduced as an attempt to provide a unified algorithmic framework for directed graphs. Nevertheless, little was known about the complexity of computing this ...directed graph invariant. We prove that deciding whether a directed graph has zig-zag number at most k is in NP for each fixed k≥0. Although for most of the natural decision problems this is an almost trivial result, settling k-zig-zag number in NP is surprisingly difficult. In addition, we prove that 2-zig-zag number is already an NP-hard problem.
We consider the graph sandwich problem and introduce almost monotone properties, for which the sandwich problem can be reduced to the recognition problem. We show that the property of containing a ...graph in
C
as an induced subgraph is almost monotone if
C
is the set of thetas, the set of pyramids, or the set of prisms and thetas. We show that the property of containing a hole of length
≡
j
mod
n
is almost monotone if and only if
j
≡
2
mod
n
or
n
≤
2
. Moreover, we show that the imperfect graph sandwich problem, also known as the Berge trigraph recognition problem, can be solved in polynomial time. We also study the complexity of several graph decompositions related to perfect graphs, namely clique cutset, (full) star cutset, homogeneous set, homogeneous pair, and 1-join, with respect to the partitioned and unpartitioned probe problems. We show that the clique cutset and full star cutset unpartitioned probe problems are
NP
-hard. We show that for these five decompositions, the partitioned probe problem is in
P
, and the homogeneous set, 1-join, 1-join in the complement, and full star cutset in the complement unpartitioned probe problems can be solved in polynomial time as well.
Timber game as a counting problem Furtado, Ana; Dantas, Simone; de Figueiredo, Celina M.H. ...
Discrete Applied Mathematics,
05/2019, Volume:
261
Journal Article
Peer reviewed
Open access
Timber is a two player game played on a directed graph, with a domino on each arc. The direction of an arc indicates the direction its domino can be toppled. Once a domino is toppled, it creates a ...chain reaction toppling all dominoes along that direction, and the player who topples the last domino wins. A P-position is an orientation of the edges of the graph where the second player can always force a win. A connected graph with a cycle has no P-position, thus Timber is a game studied in trees. We prove that a tree has a P-position if and only if the number of edges is even, which generalizes the existing characterization for paths and improves the performance of the existing algorithm to decide if an oriented tree with an odd number of arcs is a P-position. We contribute to the open problem of determining the number of P-positions of a tree. We compute the number of P-positions of three caterpillar infinite subclasses. Finally, we present a lower bound to the number of P-positions of an arbitrary caterpillar.
Genome rearrangements are events where large blocks of DNA exchange places during evolution. The analysis of these events is a promising tool for understanding evolutionary genomics. Many pairwise ...rearrangement distances have been proposed, based on finding the minimum number of rearrangement events to transform one genome into the other, using some predefined operation. When more than two genomes are considered, we have the more challenging problem of rearrangement-based phylogeny reconstruction. One important problem is the Closest Genome Problem (CGP), that aims to find, for a given distance notion, a genome that minimizes the maximum distance to any other, which can be seen as finding a genome in the center of all others. The Hamming Closest String Problem (Hamming-CSP) was already studied and settled to be NP-complete. In this paper, we show that the CGP is NP-complete for well-known genome rearrangement distances, such as the single-cut-or-join, the breakpoint and the block interchange.
Revising Johnson’s table for the 21st century de Figueiredo, Celina M.H.; de Melo, Alexsander A.; Sasaki, Diana ...
Discrete Applied Mathematics,
12/2022, Volume:
323
Journal Article
Peer reviewed
Open access
What does it mean today to study a problem from a computational point of view? We focus on parameterized complexity and on Column 16 “Graph Restrictions and Their Effect” of D.S. Johnson’s Ongoing ...guide, where several puzzles were proposed in a summary table with 30 graph classes as rows and 11 problems as columns. Several of the 330 entries remain unclassified into Polynomial or NP-complete after 35 years. We provide a full dichotomy for the Steiner Tree column by proving that the problem is NP-complete when restricted to Undirected Path graphs. We revise Johnson’s summary table according to the granularity provided by the parameterized complexity for NP-complete problems.
A graph G=(V,E) is Cprobe if V can be partitioned into two sets, probes P and non-probes N, where N is independent and new edges may be added between non-probes such that the resulting graph is in ...the graph class C. We say that (N,P) is a Cprobe partition for G. The Cunpartitioned probe problem consists of an input graph G and the question: Is G a C probe graph? A (k,ℓ)-partition of a graph G is a partition of its vertex set into at most k independent sets and ℓ cliques. A graph is (k,ℓ) if it has a (k,ℓ)-partition. We prove the full complexity dichotomy into NP-complete and polynomial for (k,ℓ)unpartitioned probe problems: they are NP-complete if k+ℓ≥3, and polynomial otherwise. This gives the first examples of graph classes C that can be recognized in polynomial time but whose probe graph classes are NP-complete.
•We prove the full complexity dichotomy into NP-complete and polynomial for (k,ℓ)unpartitioned probe problems.•The established full complexity dichotomy answers negatively the SPGC conjecture of Le and Ridder, published in WG 2007.•The established full complexity dichotomy answers a question of Chang, Hung and Rossmanith, published in DAM 2013.
PDF
