<p>A <em>rainbow matching</em> 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 <em>rainbow matching problem</em>, and its <strong>NP</strong>-complete even for properly edge-colored paths. The authors even note that prior to this result, no unweighted graph problem is known to be <strong>NP</strong>-hard for simple paths to the best of their knowledge.</p>

<p>See <a href="http://www.sciencedirect.com/science/article/pii/S0304397513009250">Le, Van Bang, and Florian Pfender. "Complexity results for rainbow matchings." Theoretical Computer Science (2013)</a>, or <a href="http://arxiv.org/pdf/1312.7253.pdf">the arXiv version</a>.</p>

CC BY-SA 3.0
2014-02-04T10:13:09.377Z
2014-02-04T10:18:10.073Z
2014-02-04T10:18:10.073Z
Juho
<p>Here are some simple observations.</p>

<ul>
<li><p>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.</p></li>
<li><p>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 <a href="http://www.sciencedirect.com/science/article/pii/S0304397511003483">Bodlaender, Thomassé and Yeo</a>.</p></li>
</ul>

CC BY-SA 3.0
2014-02-04T15:16:43.097Z
That's basically @Saeed's comment..
R B
CC BY-SA 3.0
2014-02-04T15:27:54.367Z
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.
Super0
CC BY-SA 3.0
2014-02-04T14:49:25.110Z
2014-02-04T14:49:25.110Z
Super0
<p>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.</p>

CC BY-SA 3.0
2014-02-06T10:35:06.297Z
2014-02-06T10:35:06.297Z
Olf
<p>Given a path with $n$ nodes and weighted edges $1 \leq \text{weight}(u,v) &lt; 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:</p>

<p>$$| \text{lab}(u) - \text{lab}(v)| = \text{weight}(u,v)$$</p>

<p>This is equivalent to the <a href="http://www.nearly42.org/cstheory/the-crazy-frog-puzzle-and-permutation-reconstruction-from-differences/" rel="nofollow">Permutation Reconstruction  from Differences problem</a> which is NPC (one of my "unofficial" results :-).</p>

CC BY-SA 3.0
2014-02-05T11:55:59.317Z
2014-02-05T12:01:08.133Z
2014-02-05T12:01:08.133Z
Marzio De Biasi
<p>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.</p>

<p><a href="https://www.sciencedirect.com/science/article/pii/S1570866718300595" rel="nofollow noreferrer">Tropical dominating sets in vertex-coloured graphs</a>, JDA'18</p>

CC BY-SA 4.0
2019-03-18T14:44:11.960Z
2019-03-18T14:44:11.960Z
Olf
<p>A trivial answer which is close to some of what appears above but, I think, distinct.</p>

<p>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 <strong>NP</strong>-complete.  ($\log k$ so that we're effectively coding $k$ in unary.) That set of values can be represented as a set of paths.</p>

CC BY-SA 3.0
2014-02-05T10:35:41.557Z
2014-02-05T10:35:41.557Z
David Richerby
<p>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.</p>

CC BY-SA 3.0
2014-02-06T10:57:36.910Z
2014-02-06T10:57:36.910Z
Arindam Pal
<p>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.</p>

<p><em>Cornet, Alexis; Laforest, Christian</em>, <a href="http://dx.doi.org/10.1016/j.dam.2018.03.018" rel="nofollow noreferrer"><strong>Domination problems with no conflicts</strong></a>, Discrete Appl. Math. 244, 78-88 (2018). <a href="https://zbmath.org/?q=an:1387.05181" rel="nofollow noreferrer">ZBL1387.05181</a>.</p>

CC BY-SA 4.0
2019-10-14T13:17:57.500Z
2019-10-14T13:17:57.500Z
Olf
<p>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?</p>

<p>I've already found a related question about <a href="https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees?rq=1">NP-hard problems on trees</a>.</p>

CC BY-SA 3.0
2014-02-04T10:25:42.963Z
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. "
Saeed
CC BY-SA 3.0
2014-02-05T11:30:12.950Z
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$?
Marzio De Biasi
<graph-theory><np-hardness>
NP-hard problems on paths
Benjamin
# NP-hard problems on paths

(Asked by: username_0 on 2014-02-04)

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](https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees?rq=1).

**Tags:** graph-theory, np-hardness

> **Comments:**
> **username_1**: 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. "  
> **username_2**: 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$?  

---

## 8 answers

### Answer by username_3 on 2014-02-04. Score: 25

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)](http://www.sciencedirect.com/science/article/pii/S0304397513009250), or [the arXiv version](http://arxiv.org/pdf/1312.7253.pdf).


---

### Answer by username_4 on 2014-02-04. Score: 8

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](http://www.sciencedirect.com/science/article/pii/S0304397511003483).

> **Comments:**
> **username_5**: That's basically @username_1's comment..  
> **username_4**: 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.  

---

### Answer by username_6 on 2014-02-06. Score: 6

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.


---

### Answer by username_2 on 2014-02-05. Score: 5

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](http://www.nearly42.org/cstheory/the-crazy-frog-puzzle-and-permutation-reconstruction-from-differences/) which is NPC (one of my "unofficial" results :-).


---

### Answer by username_6 on 2019-03-18. Score: 4

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](https://www.sciencedirect.com/science/article/pii/S1570866718300595), JDA'18


---

### Answer by username_7 on 2014-02-05. Score: 3

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.


---

### Answer by username_8 on 2014-02-06. Score: 3

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.


---

### Answer by username_6 on 2019-10-14. Score: 2

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**](http://dx.doi.org/10.1016/j.dam.2018.03.018), Discrete Appl. Math. 244, 78-88 (2018). [ZBL1387.05181](https://zbmath.org/?q=an:1387.05181).


---

