23
$\begingroup$

everybody knows there exist many decision problems which are NP-hard on general graphs, but I'm interested in problems that are even NP-hard when the underlying graph is a path. So, can you help me to collect such problems?

I've already found a related question about NP-hard problems on trees.

Improve this question
$\endgroup$
2
  • 21
    $\begingroup$ If you see that question you should also carefully read the accepted answer: "Take any NP-hard problem related to supersequences, superstrings, substrings, etc. Then re-interpret a string as a labelled path graph. " $\endgroup$
    – Saeed
    Commented Feb 4, 2014 at 10:25
  • 2
    $\begingroup$ Just a note: if the paths are not labeled, they are obviously highly compressible and the compact representation is a reasonable choice ($\log n$ bits to represent a path of $n$ nodes) ... so you can also "convert" hard problems that don't use unary encoding; e.g. subset sum: given $n$ unlabeled paths of length $a_1,...,a_n$, does there exist a subset of them that can be joined to form a path of length $b$? $\endgroup$
    – Marzio De Biasi
    Commented Feb 5, 2014 at 11:30

8 Answers 8

Reset to default
25
$\begingroup$

A rainbow matching in an edge-colored graph is a matching whose edges have distinct colors. The problem is: given an edge-colored graph $G$ and an integer $k$, does $G$ have a rainbow matching with at least $k$ edges? This is known as rainbow matching problem, and its NP-complete even for properly edge-colored paths. The authors even note that prior to this result, no unweighted graph problem is known to be NP-hard for simple paths to the best of their knowledge.

See Le, Van Bang, and Florian Pfender. "Complexity results for rainbow matchings." Theoretical Computer Science (2013), or the arXiv version.

Improve this answer
$\endgroup$
8
$\begingroup$

Here are some simple observations.

  • An uncolored path graph basically encodes an integer, so you can take any NP-hard problem involving unary-encoded integers and reinterpret it as a path graph problem. If you allow multiple integers encoded in unary (= a disjoint union of path graphs), then you can use some strongly NP-complete problems like 3-Partition.

  • A colored path graph encodes a word on a fixed alphabet, so again you can take a NP-hard problem on words. An example that I'm aware of is the Disjoint Factors problem introduced in Bodlaender, Thomassé and Yeo.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ That's basically @Saeed's comment.. $\endgroup$
    – R B
    Commented Feb 4, 2014 at 15:16
  • $\begingroup$ Right, then feel free to downvote my reply. As for NP-hard problems on trees, I can mention the well-known Bandwidth problem; it was actually shown to be hard for the W-hierarchy in a research report by Bodlaender, which I couldn't find online. $\endgroup$
    – Super0
    Commented Feb 4, 2014 at 15:27
6
$\begingroup$

MinCC Graph Motif is NP-hard when the graph is a path (even APX-hard). Given a graph with colors on the vertices and a set of colors, find a subgraph matching the set of colors and minimizing the number of connected comp. See Complexity issues in vertex-colored graph pattern matching, JDA 2011.

Improve this answer
$\endgroup$
5
$\begingroup$

Given a path with $n$ nodes and weighted edges $1 \leq \text{weight}(u,v) < n$, find if the nodes can be labeled using numbers in $[1..n]$ (avoiding duplicate labels) in such a way that the absolute difference of the labels of two adjacent nodes is equal to the weight of the edge:

$$| \text{lab}(u) - \text{lab}(v)| = \text{weight}(u,v)$$

This is equivalent to the Permutation Reconstruction from Differences problem which is NPC (one of my "unofficial" results :-).

Improve this answer
$\endgroup$
4
$\begingroup$

The Rainbow Dominating Set (RDS) remains NP-hard on paths. Given a vertex-colored graph, a RDS is a DS where each color of the graph appears at least once.

Tropical dominating sets in vertex-coloured graphs, JDA'18

Improve this answer
$\endgroup$
3
$\begingroup$

A trivial answer which is close to some of what appears above but, I think, distinct.

Fix any polynomial-time computable coding $f\colon\mathbb{N}^3\to\mathbb{N}$ of triples $\langle k,m,w\rangle$ as natural numbers. The set of values $f(k,m,w)$ such that the $m$th nondeterministic Turing machine accepts its $w$th input in at most $n^{\log k}$ steps (where $n$ is the length of that input) is NP-complete. ($\log k$ so that we're effectively coding $k$ in unary.) That set of values can be represented as a set of paths.

Improve this answer
$\endgroup$
3
$\begingroup$

The Unsplittable Flow Problem (UFP) remains NP-hard on a path. Indeed, UFP is NP-hard even on a single edge, as it is equivalent to the Knapsack problem.

Improve this answer
$\endgroup$
2
$\begingroup$

Dominating Set and Independent Dominating Set are NP-hard on paths if there is also in the input a "conflict graph", where an edge in this graph is a pair of vertices which cannot be both in the solution.

Cornet, Alexis; Laforest, Christian, Domination problems with no conflicts, Discrete Appl. Math. 244, 78-88 (2018). ZBL1387.05181.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.